C++冒泡算法解析

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　冒泡排序（Bubble Sort）

定义：它是一种计算机科学领域的较简单经典的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

时间复杂度：最优：O(N²)，最坏：O(N²)，平均：O(N²)。

空间复杂度：最优：O(1)，最坏：O(1)，平均：O(1)。

算法稳定性：稳定

算法过程示意图：

下面是初版代码逻辑：

 1 #include <iostream>
 2 #include <random>
 3 
 4 
 5 constexpr const int ARRAY_LENGTH = 10;
 6 
 7 int getRandomVal(int nMin, int nMax) {
 8     if (nMin == nMax) {
 9         return nMin;
10     }
11 
12     if (nMin > nMax) {
13         return std::rand() % (nMin - nMax) + nMax;
14     } else {
15         return std::rand() % (nMax - nMin) + nMin;
16     }
17 }
18 
19 bool getRandomArray(int *pArray, int nSize) {
20     if (nullptr == pArray || 0 >= nSize) {
21         return false;
22     }
23 
24     for (int nIndex = 0; nIndex < nSize; nIndex++) {
25         *pArray = getRandomVal(1, 50);
26         ++pArray;
27     }
28 
29     return true;
30 }
31 
32 bool bubbleSort(int *pArray, int nSize) {
33     if (nullptr == pArray || 0 >= nSize) {
34         return false;
35     }
36 
37     if (nSize < 2) {
38         return true;
39     }
40 
41     for (int nIndex = 0; nIndex < nSize; nIndex++) {
42         for (int nCount = 0; nCount < nSize - nIndex - 1; nCount++) {
43             if (pArray[nCount] > pArray[nCount + 1]) {
44                 int nTempVal       = pArray[nCount];
45                 pArray[nCount]     = pArray[nCount + 1];
46                 pArray[nCount + 1] = nTempVal;
47             }
48         } 
49     }
50 
51     return true;
52 }
53 
54 void printArray(int *pArray, int nSize) {
55     if (nullptr == pArray || 0 >= nSize) {
56         std::cout << "array error!" << std::endl;
57         return;
58     }
59 
60     for (int nIndex = 0; nIndex < nSize; nIndex++) {
61         std::cout << " " << pArray[nIndex];
62     }
63 
64     std::cout << std::endl;
65 }
66 
67 int main() {
68     int szArray[ARRAY_LENGTH] = { 0 };
69 
70     if (!getRandomArray(szArray, ARRAY_LENGTH)) {
71         return 0;
72     }
73 
74     if (!bubbleSort(szArray, ARRAY_LENGTH)) {
75         return 0;
76     }
77 
78     printArray(szArray, ARRAY_LENGTH);
79     std::cin.get();
80 
81     return 0;
82 }

上述版本虽然实现冒泡排序，但是从实现代码可以分析一下，如果当前随机数组为：2 1 3 4 5 6 7 8 9 10，按照从小到大排序，其实只需要进行一次排序其实就已经排序完成了，但是上述版本其实依然会执行所有步骤。所以可以对这个代码进行优化，优化如下：

下面只展示排序函数优化实现：

 1 bool bubbleSort(int *pArray, int nSize) {
 2     if (nullptr == pArray || 0 >= nSize) {
 3         return false;
 4     }
 5  
 6     if (nSize < 2) {
 7         return true;
 8     }
 9 
10     bool bSortOver = true;
11 
12     for (int nIndex = 0; nIndex < nSize; nIndex++) {
13         for (int nCount = 0; nCount < nSize - nIndex - 1; nCount++) {
14             if (pArray[nCount] > pArray[nCount + 1]) {
15                 int nTempVal       = pArray[nCount];
16                 pArray[nCount]     = pArray[nCount + 1];
17                 pArray[nCount + 1] = nTempVal;
18                 bSortOver = false;
19             }
20         }
21 
22         if (bSortOver) {
23             break;
24         }
25 
26         bSortOver = true;
27     }
28 
29     return true;
30 }

上述实现思想：在每次排序的时候如果发现后续没有进行一次交换操作，说明当前数组为已经有序，可以不继续操作排序判断，跳出即可。节省时间，提升效率。

原文链接: https://www.cnblogs.com/silentwei/p/13300766.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/365819

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

C++冒泡算法解析

相关推荐