# 通常的冒泡排序 假設按照升序排序。 排序思想： 第一趟排序：首先將第一個元素和第二個元素比較，若第一個元素大于第二個元素，交換它們，然后比較第二個元素和第三個元素，……，知道第n-1個元素和第n個元素比較， 第一趟排序將最大的元素放在了最后一位（第n位）； 第二趟排序：對前n-1個元素元素執行同樣操作，其結果是將第二大的元素放在了數組第n - 1的位置上。 第i趟排序：依次比較前n - i + 1個元素，將這n - i + 1個元素中最大的元素放到第n - i + 1位上。 設數組大小為n；比較相鄰的兩個數，如果第一個大于第二個，則交換兩個數據；這樣，第一個排序后，比較了n-1次，最大的數在數組末尾。然后n = n- 1，在n不為0情況下繼續排序，否則排序完成。 ~~~ void bubble_sort1(int a[], int size) { int i; for (i = 0; i < size; ++i) { int j; for (j = 1; j < size - i; ++j) { if (a[j - 1] > a[j]) { int temp = a[j - 1]; a[j - 1] = a[j]; a[j] = temp; } } } } ~~~ # 改進版本 設置一個標記flag，如果某次排序發生了交換flag為真；否則flag為假，排序結束。排序結束的標志是某趟排序沒有發生交換。那么排序所需要的趟數k范圍是1 <= k < n。若初始序列為有序的，則只需要一趟排序，在排序過程中進行n -1 次的關鍵字的比較，且不需要移動元素。若初始序列為逆序的，則需要n - 1趟排序，共需要n(n - 1) / 2次比較，并作等數量級的元素移動。 ~~~ void bubble_sort2(int a[], int size) { int k; bool flag; k = size; flag = true; while (flag) { flag = false; int j; for (j = 1; j < k; j++) { int temp; if (a[j - 1] > a[j]) { temp = a[j - 1]; a[j - 1] = a[j]; a[j] = temp; flag = true; } } k--; } } int main() { int a[] = {9,4,2,6,1, 1, 1}; cout << sizeof(a) / sizeof(int) << endl; bubble_sort1(a, sizeof(a) / sizeof(int)); //bubble_sort1(a, sizeof(a) / sizeof(int)); int i; for (i = 0; i < sizeof(a) / sizeof(int); ++i) cout << a[i] << " "; cout << endl; return 0; } ~~~ 該排序算法用到了交換兩個數的函數。參考[這里](http://blog.csdn.net/u013074465/article/details/44342629)查看面試題“不借助其他變量，交換兩個數”。