各種排序算法總結

轉載：http://blog.csdn.net/warringah1/article/details/8951220

明天就要去參加阿里巴巴的實習生筆試了，雖然沒想著能進去，但是態度還是要端正的，也沒什么可以準備的，復習復習排序吧。

1 插入排序

void?InsertSort(int?a[],?int?n)

{

??????for?(int?i=1;?i<n; ++i) {

????????????int?key?=?a[i];

????????????int?j?=?i?- 1;

????????????while(j>=0 &&?a[j]>key) {

??????????????????a[j+1] =?a[j];

????????????????? --j;

??????????? }

????????????a[j+1] =?key;

????? }

}

插入排序是穩定的排序，平均和最壞時間復雜度是O(n^2)。最好的時間復雜度是O(n)，對應于全部排好序的情況。

2 冒泡排序

void?BubbleSort(int?a[],?int?n)

{

??????for?(int?i=1;?i<n; ++i) {

????????????for(int?j=0;?j<n-i; ++j) {

??????????????????if(a[j]>a[j+1]) {

???????????????????????inttemp?=?a[j];

???????????????????????a[j] =?a[j+1];

???????????????????????a[j+1] =?temp;

????????????????? }

??????????? }

????? }

}

冒泡排序是穩定的排序，平均和最壞時間復雜度是O(n^2)。

3 選擇排序

每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最后，直到全部待排序的數據元素排完。選擇排序是不穩定的排序方法。

void?SelectSort(int?a[],?int?n)

{

??????for?(int?i=0;?i<n-1; ++i) {

????????????for(int?j=i+1;?j<n; ++j) {

??????????????????if(a[i]>a[j]) {

???????????????????????inttemp?=?a[i];

???????????????????????a[i] =?a[j];

???????????????????????a[j] =?temp;

????????????????? }

??????????? }

????? }

}

選擇排序是不穩定的，因為，在一趟選擇，如果當前元素比一個元素小，而該小的元素又出現在一個和當前元素相等的元素后面，那么交換后穩定性就被破壞了。舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那么原序列中2個5的相對前后順序就被破壞了平均和最壞時間復雜度是O(n^2)。

4 希爾排序（縮小增量排序）

該方法的基本思想是：先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。

void?ShellSort(int?a[],?int?n)

{

??????for?(int?gap=n/2;?gap>0;?gap/=2) {

????????????for(int?i=0;?i<gap; ++i) {

??????????????????for(int?j=i+gap;?j<n;?j+=gap) {

???????????????????????if(a[j]<a[j-gap]) {

?????????????????????????????int?temp?=?a[j];

?????????????????????????????int?k?=?j-gap;

?????????????????????????????while?(k>=0&&a[k]>temp) {

???????????????????????????????????a[k+gap] =?a[k];

?????????????????????? ????????????k?-=?gap;

???????????????????????????? }

?????????????????????????????a[k+gap] =?temp;

?????????????????????? }

????????????????? }

??????????? }

????? }

}

void?ShellSortImproved(int?a[],?int?n)

{

??????for?(int?gap=n/2;?gap>0;?gap/=2) {

????????????for(int?j=gap;?j<n; ++j) {

??????????????????if(a[j]<a[j-gap]) {

???????????????????????inttemp?=?a[j];

???????????????????????intk?=?j?-?gap;

???????????????????????while(k>=0 &&?a[k]>temp) {

?????????????????????????????a[k+gap] =?a[k];

?????????????????????????????k?-=?gap;

?????????????????????? }

???????????????????????a[k+gap] =?temp;

????????????????? }

??????????? }

????? }

}

希爾排序是不穩定的。由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩定性就會被打亂，所以shell排序是不穩定的。使用希爾增量時，最壞運行時間是O(n^2)，使用Hibbard增量時，最壞運行時間是O(n^3/2)。

5. 堆排序

void?MaxHeapify1(int?a[],?int?n,?int?i)

{

??????int?l?=?LEFT(i);

??????int?r?=?RIGHT(i);

??????int?largest;

??????if?(l<n&&?a[l]>a[i])

????????????largest=?l;

??????else

????????????largest=?i;

??????if?(r<n&&?a[r]>a[largest])

????????????largest=?r;

??????if?(largest!=i) {

????????????swap(a[i],?a[largest]);

????????????MaxHeapify1(a,?n,?largest);

????? }?else

????????????return;

}

void?MaxHeapify2(int?a[],?int?n,?int?i)

{

??????int?c,??largest;

??????while?(1){

????????????c=?LEFT(i);

????????????if?(c>=n)

??????????????????break;

????????????if?(a[i]<a[c])

??????????????????largest=?c;

????????????else

??????????????????largest=?i;

????????????if?(c+1<n) {

??????????????????if(a[largest]<a[c+1])

???????????????????????largest=?c?+ 1;

??????????? }

????????????if?(largest!=i) {

??????????????????swap(a[i],?a[largest]);

??????????????????i=?largest;

??????????? }?else

??????????????????break;

????? }

}

void?HeapSort(int?a[],?int?n)

{

??????for?(int?i=n/2-1;?i>=0;--i)

????????????MaxHeapify1(a,?n,?i);

??????for?(int?i=n-1;?i>0; --i) {

????????????swap(a[i],?a[0]);

????????????MaxHeapify1(a,?i, 0);

????? }

}

堆排序是原地排序，但是不是穩定排序。時間復雜度O(nlogn)。

6 歸并排序

void?Merge(int?a[],?int?p,?int?q,?int?r)

{

??????int?n1?=?q?-?p?+ 1;

??????int?n2?=?r?- (q+1) +1;

??????int?*L?=?new?int[n1+1];

??????int?*R?=?new?int[n2+1];

??????for?(int?i=0;?i<n1; ++i)

????????????L[i] =?a[p+i];

??????for?(int?i=0;?i<n2; ++i)

????????????R[i] =?a[q+1+i];

??????L[n1] =?INT_MAX;//哨兵

??????R[n2] =?INT_MAX;

??????int?i?= 0,?j?= 0;

??????for?(int?k=p;?k<=r; ++k) {

????????????if?(L[i]<=R[j])

??????????????????a[k] =?L[i++];

????????????else

??????????????????a[k] =?R[j++];

????? }

??????delete[]?L;

??????delete[]?R;

}

void?MergeSort(int?a[],?int?p,?int?r)

{

??????if?(p<r) {;

????????????int?q?= ((r-p)>>1) +?p;

????????????MergeSort(a,?p,?q);

????????????MergeSort(a,?q+1,?r);

????????????Merge(a,?p,?q,?r);

????? }

}

合并過程中我們可以保證如果兩個當前元素相等時，我們把處在前面的序列的元素保存在結果序列的前面，這樣就保證了穩定性。所以，歸并排序也是穩定的排序算法。時間復雜度是O(nlogn)。可以在空間復雜度O(1)的條件下實現歸并排序。

7. 快速排序

被快速排序所使用的空間，依照使用的版本而定。使用原地（in-place）分區的快速排序版本，在任何遞歸調用前，僅會使用固定的額外空間。然而，如果需要產生O(log n)嵌套遞歸調用，它需要在他們每一個存儲一個固定數量的信息。因為最好的情況最多需要O(log n)次的嵌套遞歸調用，所以它需要O(log n)的空間。最壞情況下需要O(n)次嵌套遞歸調用，因此需要O(n)的空間。

void?Median3(int?a[],?int?p,?int?r)

{

??????int?median?=?p?+ ((r-p)>>1);

??????if?(a[p]>a[median])

????????????swap(a[p],?a[median]);

??????if?(a[p]>a[r])

????????????swap(a[p],?a[r]);

??????if?(a[median]>a[r])

????????????swap(a[median],?a[r]);

??????swap(a[median],?a[r]);

}

int?Partition1(int?a[],?int?p,?int?r)