本文給出了八大排序算法的簡單思路介紹以及代碼實現(xiàn)（僅核心代碼,程序中出現(xiàn)的drive函數(shù)為排序驅(qū)動程序）。

1. 插入排序

1）將一個元素插入到已經(jīng)排好序的有序表中，從而使得有序表的個數(shù)+1。 算法從第二個元素開始。將一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列。

2） 從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置以使得其變成有序的序列。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。）

void insertSort(int* a, int n)

{

int i, j, temp;

for( i = 1; i < n;="" i++="">

{

temp = a[i];

for( j = i - 1; j >= 0 && temp < a[j];="" j--="">

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

a[j + 1] = temp;

}

}

2. 冒泡排序

冒泡排序（Bubble Sort）也是一種簡單直觀的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。也就是說在要排序的一組數(shù)中，對當前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對相鄰的兩個數(shù)依次進行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時，就將它們互換。

void bubbleSort(int* a, int size)

{

int i, j, temp;

for( i = 0; i < size="" -="" 1;="" i++="">

{

for( j = 0; j < size="" -="" i="" -="" 1;="" j++="">

{

if( a[j + 1] < a[j]="">

{

temp = a[j];

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

a[j + 1] = temp;

}

}

}

}

3.選擇排序

1）首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置

2）再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。

3）重復(fù)第二步，直到所有元素均排序完畢。

void selectionSort(int* a, int size)

{

int min_index, min_value, i, j, temp;

for( i = 0; i < size="" -="" 1;="" i++="">

{

min_index = i;

min_value = a[i];

for( j = i + 1; j < size;="" j++="">

{

if( min_value > a[j] )

{

min_value = a[j];

min_index = j;

}

}

if( i != min_index )

{

temp = a[i];

a[i] = a[min_index];

a[min_index] = temp;

}

}

}

4.快速排序

快速排序是在實踐中最快的已知的排序算法，他的平均運行時間是O（NlogN），該算法之所以非常的快是因為非常精煉和高度優(yōu)化的內(nèi)部循環(huán)。它的最壞的情形的性能是O(N^2)，但是只要稍加努力就可以改變這個情況。 像歸并算法一樣，快速排序算法也是一種分治的遞歸算法，將數(shù)組S排序的基本算法是由以下簡單的4步組成：

1. 如果S中的元素個數(shù)為0， 1， 則返回

2. 取S中的任一元素v， 稱之為樞紐元（pivot）。

3. 將其余的元素分成兩個不相交的集合，S1和S2。

4. 返回quickSort（S1）， 繼隨v， 繼而quickSort(S2)

快速排序更快的原因在于第3步分割成兩組實際上是在適當?shù)奈恢眠M行并且非常的有效， 它的高效性彌補了將一個大問題分為兩個可能大小不等的子問題的缺陷。實現(xiàn)2和3步有許多的方法，這里介紹的方法是大量的分析和經(jīng)驗研究的結(jié)果。

1， 選擇樞紐元。無論選擇哪里元素作為樞紐元都可以完成排序工作，但是有些選擇明顯是更優(yōu)的。

１）一種錯誤的方法：

將第一個元素作為pivot， 如果輸入的待排序的data是無序的，則這么做是可以的接受的，但是如果輸入是預(yù)排序， 那么這樣做就會產(chǎn)生一個劣質(zhì)的分割。

２）一種安全的做法：

一種安全的方針是隨機的選取pivot， 一般來說這種策略是非常安全的，但是另一方面值得指出的是， 隨機數(shù)的生成是非常昂貴的， 根本減少不了算法的其他方面的運行時間。

３）三數(shù)中值分割法：

pivot的最好的選擇是待排序數(shù)組的中值，不幸的是，這是很難算出的。這樣的中值的估計量可以通過隨機選取3個元素并且使用它們的中值為作為pivot而得到。一般的做法是使用左端，右端和中間位置上的3個元素得到。

算法過程的簡單描述： 首先使用上述的三數(shù)中值分割法產(chǎn)生樞紐元， 將該樞紐元與最后一個元素互換位置（脫離待排序的序列）。然后使得iptr指向第一個元素， jptr指向倒數(shù)第二個元素。比較data[i]與pivot，若data[i]pivot，說明此時的data[i]位置不對，data[i]屬于大元素，應(yīng)該在右邊部分， 故互換data[i]與data[j]。此時data[j]找到了自己的正確的位置， j--。若data[j]>pviot, 則繼續(xù)往左走，直到data[j] 改進的算法過程的描述：主要的區(qū)別在于，每一輪交換之前，首先iptr從左向右掃描屬于大元素(屬于左部分)的項，找到之后不馬上交換，而是jptr從右向左掃描屬于小元素(屬于右邊部分)的項，然后交換。

int median3(int start, int end)

{

int center = (start + end) / 2;

if( data[start] > data[center] )

swap(start, center);

if( data[start] > data[end] )

swap(start, end);

if( data[center] > data[end] )

swap(center, end);

swap(center, end - 1);

return data[center];

}

void quickSort(int* a, int start, int end)

{

int iptr, jptr;

iptr = start;

jptr = end - 1;

int pivot = median3(start, end);

if( 8 <= end="" -="" start="">

{

for( ; ; )

{

while( a[++iptr] < pivot="">

while( a[--jptr] > pivot );

if( iptr < jptr="">

swap(iptr, jptr);

else

break;

}

swap(iptr, end - 1);

quickSort(a, start, iptr - 1);

quickSort(a, iptr + 1, end);

}

else

insertSort(a, start, end);

}

void insertSort(int* a, int start, int end)

{

int i, j, temp;

for( i = 1; i < end;="" i++="">

{

temp = a[i];

for( j = i - 1; j >= 0 && a[j] > temp; j-- )

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

a[j + 1] = temp;

}

}

void swap(int i, int j)

{

int temp;

temp = data[i];

data[i] = data[j];

data[j] = temp;

}

void drive(int* a, int number)

{

int i;

quickSort(data, 0, number - 1);

}

5.歸并排序

歸并排序以O(shè)(NlogN)最壞情況運行時間運行，這個算法的基本操作是合并兩個已經(jīng)排序好的表， 因此， 歸并排序是很好描述的，如果N = 1， 那么只有一個元素需要排序， 答案是顯然的，否則， 遞歸的將前半部分數(shù)據(jù)和后半部分數(shù)據(jù)進行歸并排序，將排序得到的兩部分的數(shù)據(jù)使用合并算法合在一起。該算法是經(jīng)典的分治策略。

void mergeSort(int* a, int* temp, int start, int end)

{

int center;

if( start < end="">

{

center = (start + end) / 2;

mergeSort(a, temp, start, center);

mergeSort(a, temp, center + 1, end);

merge(a, temp, start, center, end);

}

}

void merge(int* a, int* temp, int left, int center, int right)

{

int Aptr, Bptr, Cptr;

Aptr = Cptr = left;

Bptr = center + 1;

int i;

while( Aptr <= center="" &&="" bptr=""><= right="">

if( a[Aptr] < a[bptr]="">

temp[Cptr++] = a[Aptr++];

else

temp[Cptr++] = a[Bptr++];

while( Aptr <= center="">

temp[Cptr++] = a[Aptr++];

while( Bptr <= right="">

temp[Cptr++] = a[Bptr++];

for( i = left; i <= right;="" i++="">

data[i] = temp[i];

}

void drive(int number)

{

int* temp;

int i;

if( !(temp = (int*)malloc(sizeof(int) * number)))

{

printf('temp malloc error');

exit(0);

}

mergeSort(data, temp, 0, number - 1);

}

6.希爾排序

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本，但希爾排序是非穩(wěn)定排序算法。希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進方法的：

1.插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時， 效率高，即可以達到線性排序的效率。

2.但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位

希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

算法步驟：

1）選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；

2）按增量序列個數(shù)k，對序列進行k 趟排序；

3）每趟排序，根據(jù)對應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列，分

別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處

理，表長度即為整個序列的長度。

void shellInsertSort(int* a, int size)

{

int i, j, increment, temp;

for( increment = size / 2; increment > 0; increment /= 2 )

{

for( i = increment; i < size;="" i++="">

{

temp = a[i];

for( j = i - increment; j >= 0; j -= increment )

{

if( temp < a[j]="">

a[j + increment] = a[j];

else

break;

}

a[j + increment] = temp;

}

}

}

7.堆排序

堆排序是基于數(shù)據(jù)結(jié)構(gòu)大頂堆。

1、建立一個大頂堆：在數(shù)組中從的size/2 - 1開始進行調(diào)整。使之成為大頂堆。

2、開始進行堆排序：將根元素和當前堆的最后一個元素（因為當前的堆是在不斷的縮小的）互換， 這樣，大頂堆的結(jié)構(gòu)遭到了破壞，使用調(diào)整函數(shù)進行調(diào)整。持續(xù)這個過程直到堆中只剩下一個元素。此時，該數(shù)組排序完成。

void adjustDown(int* a, int i, int size)

{

int temp, child;

for( temp = a[i]; leftchild(i) < size;="" )="">

//就是要為temp找到合適的位置

{

child = leftchild(i);

if( child != size - 1 && a[child] < a[child="" +="" 1]="">

child++; //獲得應(yīng)該上調(diào)的孩子的位置

if( temp < a[child]="">

a[i] = a[child]; //如果temp小于其中的一個孩子則上調(diào)

else

break; //如果temp比兩個孩子都大，調(diào)整完畢， 大頂堆的結(jié)構(gòu)恢復(fù)

i = child; //開始調(diào)整以“大”孩子為根的大頂堆

}

a[i] = temp;

}

void heapSort(int* a, int size)

{

int i;

for( i = size / 2 - 1; i >= 0; i-- )

adjustDown(a, i, size);

for( i = size - 1; i > 0; i-- )

{

swap(a, 0, i);

adjustDown(a, 0, i);

}

}

void swap(int* a, int i, int j)

{

int temp;

temp = a[i];

a[i] = a[j];

a[j] = temp;

}