冒泡排序是排序算法的一種，思路清晰，代碼簡潔，常被用在大學生計算機課程中。
“冒泡”這個名字的由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端，故名。
這里以從小到大排序為例進行講解。
基本思想及舉例說明
冒泡排序的基本思想就是不斷比較相鄰的兩個數，讓較大的元素不斷地往后移。經過一輪比較，就選出最大的數；經過第2輪比較，就選出次大的數，以此類推。
下面以對 3 2 4 1 進行冒泡排序說明。
第一輪 排序過程
3 2 4 1 （最初）
2 3 4 2 （比較3和2，交換）
2 3 4 1 （比較3和4，不交換）
2 3 1 4 （比較4和1，交換）
第一輪結束，最大的數4已經在最后面，因此第二輪排序只需要對前面三個數進行再比較。
第二輪 排序過程
2 3 1 4 （第一輪排序結果）
2 3 1 4 （比較2和3，不交換）
2 1 3 4 （比較3和1，交換
第二輪結束，第二大的數已經排在倒數第二個位置，所以第三輪只需要比較前兩個元素。
第三輪 排序過程
2 1 3 4 （第二輪排序結果）
1 2 3 4 （比較2和1，交換）
至此，排序結束。
算法總結及實現
對于具有N個元素的數組R[n]，進行最多N-1輪比較；
第一輪，逐個比較（R[1], R[2]）, （R[2], R[3]）, （R[3], R[4]）, ……. （R[N-1], R[N]） ; 最大的元素會被移動到R[N]上。
第二輪，逐個比較（R[1], R[2]）, （R[2], R[3]）, （R[3], R[4]）, ……. （R[N-2], R[N-1]）；第二大元素會被移動到R[N-1]上。
。。。。
以此類推，直到整個數組從小到大排序。
下面給出了冒泡排序的一般實現和優化實現。一般實現是教科書里常見的實現方法，無論數組是否排序好了，都會進行N-1輪比較； 而優化實現，在數組已經排序好的情況下，會提前退出比較，減小了算法的時間復雜度。
#include<stdio.h>#include<stdlib.h>#define N 8void bubble_sort(int a[],int n);//一般實現void bubble_sort(int a[],int n)//n為數組a的元素個數{ //一定進行N-1輪比較 for(int i=0; i<n-1; i++) { //每一輪比較前n-1-i個，即已排序好的最后i個不用比較 for(int j=0; j<n-1-i; j++) { if(a[j] > a[j+1]) { int temp = a[j]; a[j] = a[j+1]; a[j+1]=temp; } } }}//優化實現void bubble_sort_better(int a[],int n)//n為數組a的元素個數{ //最多進行N-1輪比較 for(int i=0; i<n-1; i++) { bool isSorted = true; //每一輪比較前n-1-i個，即已排序好的最后i個不用比較 for(int j=0; j<n-1-i; j++) { if(a[j] > a[j+1]) { isSorted = false; int temp = a[j]; a[j] = a[j+1]; a[j+1]=temp; } } if(isSorted) break; //如果沒有發生交換，說明數組已經排序好了 }}int main(){ int num[N] = {89, 38, 11, 78, 96, 44, 19, 25}; bubble_sort(num, N); //或者使用bubble_sort_better(num, N); for(int i=0; i<N; i++) printf("%d ", num[i]); printf("/n"); system("pause"); return 0;}新聞熱點
疑難解答
圖片精選
