|
1、算法外排序分類 2、冒泡排序 冒泡排序（Bubble Sort）屬于交換排序，它的原理是：循環(huán)兩兩比較相鄰的記錄，如果反序則交換，直到?jīng)]有反序的記錄為止。 實現(xiàn)算法： /** * 冒泡排序優(yōu)化后的算法 * 設(shè)置一個標(biāo)記來標(biāo)志一趟比較是否發(fā)生交換 * 如果沒有發(fā)生交換，則數(shù)組已經(jīng)有序 */ void bubbleSort(SqList *L){ int i,j; int flag = true; // flag 用來作為標(biāo)記 for (i = 1; i < L->length && flag; i++) { // 若flag為true 則說明數(shù)據(jù)交換過，否則沒交換過(數(shù)組已經(jīng)有序) 則停止循環(huán) 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; // 如果有數(shù)據(jù)交換 flag為true } } } } 3、簡單選擇排序 簡單選擇排序法(Simple Selection Sort)是通過 原理是：每一次從無序數(shù)據(jù)組的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在無序數(shù)組的開始位置，隨著無序數(shù)組元素減少，有序組元素增加，直到全部待排序的數(shù)據(jù)元素完全排完。 /** * 簡單選擇排序算法 */ void selectSort(SqList *L){ int i, j, min; for (i = 1; i < L->length; i++) { min = i; // 將當(dāng)前下標(biāo)定義為最小值下標(biāo) 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)的是將一個記錄插入到已經(jīng)排好序的有序表中，從而得到一個新的、記錄增1的有序表。 原理：將一個記錄插入到一個已經(jīng)排序好的表中，得到一個記錄增加1的有序表。并且它把當(dāng)前元素大的記錄都往后移動，用以騰出“自己”該插入的位置。當(dāng)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]; // 設(shè)置哨兵 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、希爾排序 希爾排序是對直接插入排序的改進排序算法。希爾排序又叫縮小增量排序。 原理：希爾排序是把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時，整個文件恰被分成一組，算法便終止。屬于不穩(wěn)定排序算法。 /** * 希爾排序算法 */ 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 時停止循環(huán) } 6、堆排序 堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆積是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點。 算法過程描述 1、將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆，此堆為初始的無序區(qū)； 2、將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n]； 3、由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對當(dāng)前無序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個元素交換，得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過程直到有序區(qū)的元素個數(shù)為n-1，則整個排序過程完成。 堆排序是一種不穩(wěn)定的排序方法。 /** * 已知 L->r[s..m] 中記錄的關(guān)鍵字除L->r[s]之外均滿足堆的定義 * 該函數(shù)調(diào)整L->r[s] 的關(guān)鍵字，使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) { // 沿關(guān)鍵字較大的孩子結(jié)點向下篩選 這里循環(huán)的條件j從 2*s 開始是因為利用了二叉樹的性質(zhì)5：由于這顆是完全二叉樹，當(dāng)前節(jié)點序號是 s ，其左孩子的序號一定是 2s， 右孩子的序號一定是 2s+1，它們的孩子當(dāng)然也是以 2 的位數(shù)序號增加，因此 j 變量才這樣循環(huán)。 if (j < m && L->r[j] < L->r[j+1]) // 1. j < m 說明它不是最后一個節(jié)點 2. L->r[j] < L->r[j+1]) 說明左孩子小于右孩子 j++; // j 為關(guān)鍵字中較大的記錄的下標(biāo) if (temp >= L->r[j]) break; // rc應(yīng)插入在位置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構(gòu)建成一個大頂堆 HeadAdjust(L, i, L->length); for (i = L->length; i > 1; i--) { swap(L, 1, i); // 將堆頂記錄和當(dāng)前未經(jīng)排序子序列的最后一個記錄交換 HeadAdjust(L, 1, i-1); // 將L->r[1..i-1]重新調(diào)整為大頂堆 } } 7、歸并排序 歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。 實現(xiàn)原理（遞歸實現(xiàn)）： 1、將序列平均分成兩部分 2、分別對這兩部分用遞歸來歸并 3、將這兩部分歸并到一起 算法示例 #p.歸并排序(遞歸實現(xiàn)) /** * 將有序的 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]復(fù)制到TR } if (j <= n) { for (l=0; l <= n-j; l++) TR[k+l] = SR[j+l]; // 將剩余的SR[j..n]復(fù)制到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); } 歸并排序是一種比較占內(nèi)存，但是效率高且穩(wěn)定的算法。 8、快速排序 實現(xiàn)原理： 選取一個關(guān)鍵字，放到一個位置，使得它的左邊的值都比它小，右邊的值都比它大，這個關(guān)鍵字叫做樞軸（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、排序算法總結(jié) 10.1 內(nèi)部排序 1、排序的記錄數(shù)量較少是，可以考慮插入排序和簡短選擇排序。如果記錄本身信息量較大時，建議選用選擇排序。 2、如果待排序記錄按關(guān)鍵字基本有序，適合采用冒泡排序或直接插入排序 3、若 排序記錄較大，可以選擇快速排序、堆排序或歸并排序。目前快速排序被認(rèn)為最好的排序方法。 10.2 外部排序 外部排序就是針對大型文件的排序。常用的外部排序方法是歸并排序。 個人博客網(wǎng)站：https:// |
|
|
