冒泡排序(Bubble sort) gaunthan Posted on Aug 7 2016 ? Sorting ? ? Algorithm ? > **冒泡排序**(Bubble sort)是排序算法的一种,它是蛮力思想的一个体现。 ## 思想 重复地走访要排序的数列,一次比较相邻的两个元素,如果它们的顺序不符合要求就交换它们的位置。$n$个数需要$n-1$趟排序,每一趟排序使得最大数冒出(升序)或最小数冒出(降序)。 为什么是$n-1$趟呢?因为最后一个数已经没有数需要和它比较了,因此最后一个数的这一趟比较可以省去。 ## 示意 你可以通过查看下面的动态图来获得直观的感受:  ## 实现 传统冒泡排序的实现如下: ```c //升序方式 void BubbleSort(int a[], int n) { int i, j; for(i = 0; i < n - 1; ++i) { for(j = 0; j < n - 1 - i; ++j) { if(a[j] > a[j + 1]) Swap(a + j, a + j + 1); } } } ``` ## 改进 ### 设比较标志法 普通的冒泡排序,即使原数列已经有序,仍然会进行$n-1$趟排序。可以加入一标志性变量,用于标志某一趟排序过程中是否有数据交换。如果进行某一趟排序时并没有进行数据交换,则说明数据已经按要求排列好,可立即结束排序,避免不必要的比较过程。如对序列`3 1 4 5 6`进行排序时,只进行2趟算法就结束了(第二趟没有发生交换使得排序提前结束)。注意,当输入序列是逆序的,该算法和传统冒泡排序进行了一样多次比较。 实现代码如下: ```c void FlagedBubbleSort(int a[], int n) { int i, j, swaped; for(i = 0; i < n - 1; ++i) { swaped = 0; for(j = 0; j < n - 1 - i; ++j) { if(a[j] > a[j + 1]) { Swap(a + j, a + j + 1); swaped = 1; } } // 该趟没有执行过交换操作,序列已有序,因此可提前结束 if(!swaped) break; } } ``` ### 剔除法 假设某一位置pos后的元素都已排序,而pos前的元素未排序完,那么上述算法仍然会扫描pos位置后的元素。因此,可设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置后的元素均已排序完,故在进行下一趟排序时只要扫描到pos位置即可。可形象地认为pos位置后的 n-pos+1 个元素都被从待排序列中剔除了。 实现代码如下: ```c void RejectBubbleSort(int a[], int n) { int i, high, rpos; high = n - 1; while(high > 0) { rpos = 0; for(i = 0; i < high; ++i) if(a[i] > a[i + 1]) { rpos = i; //记录交换位置 Swap(a + i, a + i + 1); } high = rpos; //下一趟应该扫描到达的位置 } } ``` ### 双向剔除法 上面的**剔除法**只能处理某一方向上的已排序子序列,使用双向的扫描可进一步优化冒泡排序。 实现代码如下: ```c void DoubleBubbleSort(int a[], int n) { int i, j; int low = 0, high = n - 1; int lpos, rpos; while(low < high) { rpos = low; for(i = low; i < high; ++i) //正向冒泡 if(a[i] > a[i + 1]) { Swap(a + i, a + i + 1); rpos = i; } high = rpos; lpos = high; for(j = high; j > low; --j) //反向冒泡 if(a[j] < a[j - 1]) { Swap(a + j, a + j - 1); lpos = j; } low = lpos; } } ``` ## References - MarkAllenWeiss, 韦斯. 数据结构与算法分析:C语言描述[M]. 机械工业出版社, 2010. - ThomasH.Cormen. 算法导论[M]. 机械工业出版社, 2013. 赏 Wechat Pay Alipay 基数排序(Radix sort) 快速排序(Quicksort)