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