學習算法，怎麼可以不懂排序？但很多時候，我們習慣了用 sort 和 qsort，對於具體排序，我們也許真忘光了。我們先從O(n^2)的常用排序開始。 冒泡排序（Bubble Sort）： 說起排序就不能不說冒泡（Bubble Sort），它非常簡單，維基中這樣解釋“重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢‘浮’到數列的頂端。” 復雜度： 最差時間復雜度：O(n^2) 最優時間復雜度：O(n^2) 平均時間復雜度：O(n^2) 穩定性：穩定 我寫冒泡通常這樣寫： [cpp] void bubbleSort(int arr[],int n) { for(int i = 0;i < n;++i) { for(int j = i+1;j < n;++j) { if(arr[i] > arr[j]) { int t = arr[j]; arr[j] = arr[i]; arr[i] = t; } } } } 基本思想是從數組中拿出第一個元素，然後開始和它後面的元素比較，只要發現比它輕，就交換兩個元素，這樣，一遍過後，最輕（最小）的元素就冒到了數列的頂端。然後第二趟把第二輕的元素冒上來，依此類推，到最後數列就是有序的。一句話說，就是每一次都選出最小的數字，讓它冒出來。 冒泡還可以這樣寫： [cpp] void bubbleSort(int arr[],int n) { for(int i = 0;i < n-1;++i) { for(int j = 0;j < n-i-1;++j) { if(arr[j] > arr[j+1]) { int t = arr[j+1]; arr[j+1] = arr[j]; arr[j] = t; } } } } 這是每一次都把最大的元素沉下去。效果是等價的。 冒泡也可以優化，但畢竟是一種效率低下的算法，無法擺平均O(n^2) 的命運。 一種常見的優化就是記錄每一次遍歷的過程是否有交換值，沒有的話說明後面已經是有序的，直接跳出循環 [cpp] void bubbleSort(int arr[],int n) { for(int i = 0;i < n;++i) { bool flag = false; for(int j = i+1;j < n;++j) { if(arr[i] > arr[j]) { int t = arr[j]; arr[j] = arr[i]; arr[i] = t; flag = true; } if(!flag) break; } } } 插入排序（Insertion Sort）： 插入排序（Insertion Sort）也是一種平均O(n^2)的排序算法。“它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反復把已排序元素逐步向後挪位，為最新元素提供插入空間。”維基的這幅圖很直觀的解釋了插入排序： 算法步驟為： 1、從有序數列 { a[0] } 和無序數列 { a[1],a[2],a[3]，…，a[n-1] }開始進行排序； 2、處理第i個元素時（i=1,2,3,…,n-1），數列 { a[0],a[1],a[2]，…，a[i-1] }是已有序的，而數列{ a[i],a[i+1]，…，a[n-1] }是無序的。用a[i]與a[i-1]，a[ i-2]，…，a[0]進行比較，找出合適的位置將a[i]插入； 3、重復第二步，共進行n-i次插入處理，數列全部有序。 復雜度： 最差時間復雜度：O(n^2) 最優時間復雜度：O(n^2) 平均時間復雜度：O(n^2) 穩定性：穩定 實現： [cpp] void insertSort(int arr[], int n) { for (int i = 1; i < n; i++) if (arr[i] < arr[i - 1]) { int j,t = arr[i]; for (j = i - 1; j >= 0 && arr[j] > t; j--) arr[j + 1] = arr[j]; arr[j + 1] = t; } } 選擇排序(Selection Sort)： 基本思想為：“首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩余未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。”類似於冒泡，也很容易理解，但它的交換次數明顯比冒泡少得多，n比較小的時候，選擇排序明顯比冒泡快。 復雜度： 最差時間復雜度：O(n^2) 最優時間復雜度：O(n^2) 平均時間復雜度：O(n^2) 穩定性：不穩定 為什麼是不穩定呢？看一個例子：對 4 5 6 4 2 3 進行選擇排序。 開始時，我們找到最小元素 2 並把它和第一個元素 4 交換，這時 序列變成 2 5 6 4 4 2 3，好像沒有問題是嗎？但是，現在，兩個 4 的位置和原來的位置相比已經改變了！所以說選擇排序時不穩定的。這點要注意，因為也許有時候會在你毫無察覺的情況下導致一些問題。 實現： [cpp] void selectionSort(int arr[], int n) { for (int i = 0; i < n; i++) { int index = i; //找出最小元素的索引 for(int j = i+1;j < n;++j) { if(arr[index] > arr[j]) index = j; } //把找到的最小元素和 arr[i] 交換 if(index != i) { int t = arr[index]; arr[index] = arr[i]; arr[i] = t; } } }
