1、算法外排序分類

?

? ? ? ?? ? ? ?

2、冒泡排序

冒泡排序（Bubble Sort）屬于交換排序，它的原理是：循環兩兩比較相鄰的記錄，如果反序則交換，直到沒有反序的記錄為止。

實現算法：

/**

?* 冒泡排序優化后的算法

?* 設置一個標記來標志一趟比較是否發生交換

?* 如果沒有發生交換，則數組已經有序

?*/

void bubbleSort(SqList *L){

? ? int i,j;? ??

? ? int flag = true;? // flag 用來作為標記

? ? for (i = 1; i < L->length && flag; i++) {?

? // 若flag為true 則說明數據交換過，否則沒交換過(數組已經有序) 則停止循環

? ? ? ? flag = false;

? ? ? ? for (j = L->length - 1; j >= i; j--) {

? ? ? ? ? ? if (L->r[j] > L->r[j+1]) {

? ? ? ? ? ? ? ? swap(L, j, j+1);

? ? ? ? ? ? ? ? flag = true;? // 如果有數據交換 flag為true

? ? ? ? ? ? }

? ? ? ? }

? ? }

}

3、簡單選擇排序

簡單選擇排序法(Simple Selection Sort)是通過n-i次關鍵字間的比較，從n-i+1個記錄中選出關鍵字最小的記錄，并和第i(1<=i<=n)個記錄交換。

原理是：每一次從無序數據組的數據元素中選出最小（或最大）的一個元素，存放在無序數組的開始位置，隨著無序數組元素減少，有序組元素增加，直到全部待排序的數據元素完全排完。

/**

?* 簡單選擇排序算法

?*/

void selectSort(SqList *L){

? ? int i, j, min;

? ? for (i = 1; i < L->length; i++) {

? ? ? ? min = i;? ? // 將當前下標定義為最小值下標

? ? ? ? for (j = i + 1; j <= L->length; j++) {

? ? ? ? ? ? if (L->r[min] > L->r[j])

? ? ? ? ? ? ? ? min = j;

? ? ? ? }

? ? ? ??

? ? ? ? if (i != min)? // 若min不等于 i 說明找到最小值， 交換

? ? ? ? ? ? swap(L, i, min);

? ? }

}

4、直接插入排序

直接插入排序(Straight Insertion Sort)的是將一個記錄插入到已經排好序的有序表中，從而得到一個新的、記錄增1的有序表。

原理：將一個記錄插入到一個已經排序好的表中，得到一個記錄增加1的有序表。并且它把當前元素大的記錄都往后移動，用以騰出“自己”該插入的位置。當n-1趟插入完成后就是需要的有序序列。

/**

?*直接插入排序算法

?*/

void InsertSort(SqList *L){

? ? int i, j;

? ? for (i = 2; i < L->length; i++) {? ? ? ??

? ? ? ? if (L->r[i] < L->r[i-1]) { // 需要將 L->r[i] 插入有序子表? ? ? ? ? ??

? ? ? ? ? ? L->r[0] = L->r[i]; // 設置哨兵

? ? ? ? ? ? for (j = i-1; L->r[j] > L->r[0]; j++)

? ? ? ? ? ? ? ? L->r[j+1] = L->r[i]; // 記錄后移? ? ? ? ? ??

? ? ? ? ? ? L->r[j+1] = L->r[0]; // 插入到正確位置

? ? ? ? }

? ? }

}

5、希爾排序

希爾排序是對直接插入排序的改進排序算法。希爾排序又叫縮小增量排序。

原理：希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。屬于不穩定排序算法。

/**

?*? 希爾排序算法

?*/

void shellSort(SqList *L){? ??

? ? int i,j;

? ??

? ? int increment = L->length;? // 增量初始值等于排序記錄

? ??

? ? do {

? ? ? ? increment = increment /3 +1;? // 增量序列

? ? ? ??

? ? ? ? for (i = increment + 1; i < L->length; i++) {

? ? ? ? ? ??

? ? ? ? ? ? if (L->r[i] < L->r[i-increment]) {? // 需要將 L->r[i] 插入有序增量子表

? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? L->r[0] = L->r[i];? // 用哨兵暫時存放 L->r[i]

? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? for (j = i - increment; i >0 && L->r[0] < L->r[j]; j -= increment)

? ? ? ? ? ? ? ? ? ? L->r[j+increment] = L->r[j];? // 記錄后移， 查找插入位置

? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? L->r[j+increment] = L->r[0];? // 插入

? ? ? ? ? ? }

? ? ? ? }

? ? } while (increment > 1);? // 增量不大于 1 時停止循環

}

6、堆排序

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。

算法過程描述

1、將初始待排序關鍵字序列(R1,R2….Rn)構建成大頂堆，此堆為初始的無序區；

2、將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(R1,R2,……Rn-1)和新的有序區(Rn),且滿足R[1,2…n-1]<=R[n]；

3、由于交換后新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區(R1,R2,……Rn-1)調整為新堆，然后再次將R[1]與無序區最后一個元素交換，得到新的無序區(R1,R2….Rn-2)和新的有序區(Rn-1,Rn)。不斷重復此過程直到有序區的元素個數為n-1，則整個排序過程完成。

?

堆排序是一種不穩定的排序方法。

?

/**

?* 已知 L->r[s..m] 中記錄的關鍵字除L->r[s]之外均滿足堆的定義

?* 該函數調整L->r[s] 的關鍵字，使L->r[s..m]成為一個大頂堆

?*/

void HeadAdjust(SqList *L, int s, int m){

? ? int temp, j;

? ? temp = L->r[s];? ??

? ? for (j = 2 *s; j <= m; j *= 2) {? // 沿關鍵字較大的孩子結點向下篩選? 這里循環的條件j從 2*s 開始是因為利用了二叉樹的性質5：由于這顆是完全二叉樹，當前節點序號是 s ，其左孩子的序號一定是 2s， 右孩子的序號一定是 2s+1，它們的孩子當然也是以 2 的位數序號增加，因此 j 變量才這樣循環。? ? ? ??

? ? ? ? if (j < m && L->r[j] < L->r[j+1])? // 1. j < m 說明它不是最后一個節點? 2. L->r[j] < L->r[j+1]) 說明左孩子小于右孩子

? ? ? ? ? ? j++;? // j 為關鍵字中較大的記錄的下標? ? ? ??

? ? ? ? if (temp >= L->r[j])

? ? ? ? ? ? break;? // rc應插入在位置s上? ? ? ??

? ? ? ? L->r[s] = L->r[j];

? ? ? ? s = j;

? ? }? ??

? ? L->r[s] = temp;? // 插入

}

/**

?* 對順序表L進行堆排序

?*/

void HeapSort(SqList *L){

? ? int i;? ??

? ? for (i = L->length / 2; i>0; i--)? ?// 把L中的r構建成一個大頂堆

? ? ? ? HeadAdjust(L, i, L->length);? ??

? ? for (i = L->length; i > 1; i--) {

? ? ? ? swap(L, 1, i);? // 將堆頂記錄和當前未經排序子序列的最后一個記錄交換

? ? ? ? HeadAdjust(L, 1, i-1);? // 將L->r[1..i-1]重新調整為大頂堆

? ? }

}

7、歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。

實現原理（遞歸實現）：

1、將序列平均分成兩部分

2、分別對這兩部分用遞歸來歸并

3、將這兩部分歸并到一起

算法示例

#p.歸并排序(遞歸實現)

/**

?* 將有序的 SR[i..m] 和 SR[m+1..n]歸并為有序的 TR[i..n]

?*/

void Merge(int SR[], int TR[], int i, int m, int n){

? ??

? ? int j, k, l;

? ??

? ? for (j = m+1, k = i; i <= m && j <= n; k++) { // 將SR中記錄有小到大歸并入TR

? ? ? ??

? ? ? ? if (SR[i] < SR[j])

? ? ? ? ? ? TR[k] = SR[i++];

? ? ? ? else

? ? ? ? ? ? TR[k] = SR[j++];

? ? }

? ??

? ? if (i <= m) {

? ? ? ? for (l=0; l <= m-i; l++)

? ? ? ? ? ? TR[k+l] = SR[i+l];? // 將剩余的SR[i..m]復制到TR

? ? }

? ??

? ? if (j <= n) {

? ? ? ? for (l=0; l <= n-j; l++)

? ? ? ? ? ? TR[k+l] = SR[j+l]; // 將剩余的SR[j..n]復制到TR

? ? }

}

?

/**

?*將SR[s..t]歸并排序為TR1[s..t]

?*/

void MSort(int SR[], int TR1[], int s, int t){

?

? ? int m;

? ? int TR2[MAXSIZE+1];

? ??

? ? if (s == t) {

? ? ? ? TR1[s] = SR[s];

? ? }else{

? ? ? ? m = (s+t)/2; // 將SR[s..t]平分為SR[s..m]和SR[m+1..t]

? ? ? ? MSort(SR, TR2, s, m);? ?// 遞歸將SR[s..m]歸并為有序的TR2[s..m]

? ? ? ? MSort(SR, TR2, m+1, t); // 遞歸將SR[m+1..t]歸并為有序的TR2[m+1..t]

? ? ? ? Merge(TR2, TR1, s, m, t); // 將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t]

? ? }

}

?

/**

?* ?對順序表L作歸并排序

?*/

void MergeSort(SqList *L){

? ? MSort(L->r, L->r, 1, L->length);

}

歸并排序是一種比較占內存，但是效率高且穩定的算法。

?

?

8、快速排序

實現原理：

選取一個關鍵字，放到一個位置，使得它的左邊的值都比它小，右邊的值都比它大，這個關鍵字叫做樞軸（pivot)

然后分別對左邊和右邊進行排序。

#p快速排序

/**

?* 交換順序表 L 中子表的記錄，使軸記錄到位，并返回其所在位置

?* 此時在它之前的記錄均不大于它，在它之后的記錄均不小于它

?*/

int partition(SqList * L, int low, int high){? ??

? ? int pivotkey;

? ? pivotkey = L->r[low];? // 用子表的第一個記錄作為樞軸記錄? ??

? ? while (low < high) {? // 從表的兩端交替地向中間掃描

? ? ? ? while (low < high && L->r[high] >= pivotkey)

? ? ? ? ? ? high --;

? ? ? ? swap(L, low, high);? // 將比樞軸小的記錄交換到低端? ? ? ??

? ? ? ? while (low < high && L->r[low] <= pivotkey)

? ? ? ? ? ? high++;

? ? ? ? swap(L, low, high);? // 將比樞軸大的記錄交換到高端

? ? }? ??

? ? return low;? // 返回樞軸所在位置

}

?

/**

?* 對順序表 L 中的子序列 L->r[low..high] 作快速排序

?*/

void QSort(SqList *L, int low, int high){? ??

? ? int pivot;

? ? if (low < high) {

? ? ? ? pivot = Partition(L, low, high);? // 將L->r[low..high]一分為二，算出樞軸值pivot

? ? ? ? QSort(L, low, pivot-1);? // 對 低子表遞歸排序

? ? ? ? QSort(L, pivot+1, high); // 對 高子表遞歸排序

? ? }

}

/**

?* 對順序表 L 作快速排序

?*/

void QuickSort(SqList *L){

? ? QSort(L, 1, L->length);

}

?

?

9、排序算法比較

? ? ? ?? ? ? ?

10、排序算法總結

10.1 內部排序

1、排序的記錄數量較少是，可以考慮插入排序和簡短選擇排序。如果記錄本身信息量較大時，建議選用選擇排序。

2、如果待排序記錄按關鍵字基本有序，適合采用冒泡排序或直接插入排序

3、若 排序記錄較大，可以選擇快速排序、堆排序或歸并排序。目前快速排序被認為最好的排序方法。

10.2 外部排序

外部排序就是針對大型文件的排序。常用的外部排序方法是歸并排序。

?

IT技術分享社區

個人博客網站：https://programmerblog.xyz

文章推薦程序員效率：畫流程圖常用的工具程序員效率：整理常用的在線筆記軟件遠程辦公：常用的遠程協助軟件，你都知道嗎？51單片機程序下載、ISP及串口基礎知識硬件：斷路器、接觸器、繼電器基礎知識