|
這節(jié)，我們介紹基數(shù)排序和歸并排序。 一、基數(shù)排序 基數(shù)排序(Radix Sort)的設(shè)計(jì)思想與前面介紹的各種排序方法完全不同。前面介紹的排序方法主要是通過關(guān)鍵碼的比較和記錄的移動(dòng)這兩種操作來實(shí)現(xiàn)排序的，而基數(shù)排序不需要進(jìn)行關(guān)鍵碼的比較和記錄的移動(dòng)。基數(shù)排序是一種借助于多關(guān)鍵碼排序的思想，是將單關(guān)鍵碼按基數(shù)分成多關(guān)鍵碼進(jìn)行排序的方法，是一種分配排序。 下面用一個(gè)具體的例子來說明多關(guān)鍵碼排序的思想。 其中，k1稱為最主位關(guān)鍵碼，kd稱為最次位關(guān)鍵碼。 多關(guān)鍵碼排序方法按照從最主位關(guān)鍵碼到最次位關(guān)鍵碼或從最次位關(guān)鍵碼到最主位關(guān)鍵碼的順序進(jìn)行排序，分為兩種排序方法： 基數(shù)的源代碼如下：  //基數(shù)排序的方法 public int[] RadixSort(int[] ArrayToSort, int digit,int len) { // 從低位到高位的方法 for (int k = 1; k <= digit; k++) { // 臨時(shí)的數(shù)組存儲(chǔ)里面的十進(jìn)制的排序的結(jié)果 int[] tmpArray = new int[ArrayToSort.Length]; //臨時(shí)的數(shù)組存儲(chǔ)計(jì)數(shù)的結(jié)果 int[] tmpCountingSortArray = new int[len]; //基數(shù)的數(shù)組1 如圖所示：
基數(shù)排序是穩(wěn)定的排序，時(shí)間的復(fù)雜度是O(n2). 二、歸并排序 歸并排序(merge Sort)主要是二路歸并排序。二路歸并排序的基本思想是：將兩個(gè)有序表合并為一個(gè)有序表。 對(duì)于n個(gè)記錄的順序表，將這n個(gè)記錄看作葉子結(jié)點(diǎn)，若將兩兩歸并生成的子表看作它們的父結(jié)點(diǎn)， 則歸并過程對(duì)應(yīng)于由葉子結(jié)點(diǎn)向根結(jié)點(diǎn)生成一棵二叉樹的過程。所以，歸并趟數(shù)約等于二叉樹的高度減1，即log2n，每趟歸并排序記錄關(guān)鍵碼比較的次數(shù)都約為n/2，記錄移動(dòng)的次數(shù)為2n（臨時(shí)順序表的記錄復(fù)制到原順序表中記錄的移動(dòng)次數(shù)為n） 。 因此， 二路歸并排序的時(shí)間復(fù)雜度為O （nlog2n） 。
一趟二路歸并排序算法的實(shí)現(xiàn)如下所示， 算法中記錄的比較代表記錄關(guān)鍵碼的比較，順序表中只存放了記錄的關(guān)鍵碼，相應(yīng)的源代碼如下： public void Merge(SeqList<int> sqList, int len) { int m = 0； //臨時(shí)順序表的起始位置 int l1 = 0; //第1個(gè)有序表的起始位置 int h1； //第1個(gè)有序表的結(jié)束位置 int l2； //第2個(gè)有序表的起始位置 int h2; //第2個(gè)有序表的結(jié)束位置 int i = 0; int j = 0; //臨時(shí)表，用于臨時(shí)將兩個(gè)有序表合并為一個(gè)有序表 SeqList<int> tmp = new SeqList<int>(sqList.GetLength()); //歸并處理 while (l1 + len < sqList.GetLength()) { l2 = l1 + len; //第2個(gè)有序表的起始位置 h1 = l2 - 1; //第1個(gè)有序表的結(jié)束位置 //第2個(gè)有序表的結(jié)束位置 h2 = (l2 + len - 1 < sqList.GetLength()) ? l2 + len - 1 : sqList.Last; j = l2; i = l1; //兩個(gè)有序表中的記錄沒有排序完 while ((i<=h1) && (j<=h2)) { //第1個(gè)有序表記錄的關(guān)鍵碼小于第2個(gè)有序表記錄的關(guān)鍵碼 if (sqList[i] <= sqList[j]) { tmp[m++] = sqList[i++]; } //第2個(gè)有序表記錄的關(guān)鍵碼小于第1個(gè)有序表記錄的關(guān)鍵碼 else { tmp[m++] = sqList[j++]; } } //第1個(gè)有序表中還有記錄沒有排序完 while (i <= h1) { tmp[m++] = sqList[i++]; } //第2個(gè)有序表中還有記錄沒有排序完 while (j <= h2) { tmp[m++] = sqList[j++]; } l1 = h2 + 1; } i = l1; //原順序表中還有記錄沒有排序完 while (i < sqList.GetLength()) { tmp[m++] = sqList[i++]; } //臨時(shí)順序表中的記錄復(fù)制到原順序表，使原順序表中的記錄有序 for (i = 0; i < sqList.GetLength(); ++i) { sqList[i] = tmp[i]; } } 二路歸并排序算法的實(shí)現(xiàn)如下： public void MergeSort(SeqList<int> sqList) { int k = 1; //歸并增量 while (k < sqList.GetLength()) { Merge(sqList, k); k *= 2; } } 對(duì)于n個(gè)記錄的順序表，將這n個(gè)記錄看作葉子結(jié)點(diǎn)，若將兩兩歸并生成的子表看作它們的父結(jié)點(diǎn)， 則歸并過程對(duì)應(yīng)于由葉子結(jié)點(diǎn)向根結(jié)點(diǎn)生成一棵二叉樹的過程。所以，歸并趟數(shù)約等于二叉樹的高度減1，即log2n，每趟歸并排序記錄關(guān)鍵碼比較的次數(shù)都約為n/2，記錄移動(dòng)的次數(shù)為2n（臨時(shí)順序表的記錄復(fù)制到原順序表中記錄的移動(dòng)次數(shù)為n） 。 因此， 二路歸并排序的時(shí)間復(fù)雜度為O （nlog2n）。而二路歸并排序使用了n個(gè)臨時(shí)內(nèi)存單元存放記錄，所以，二路歸并排序算法的空間復(fù)雜度為O（n） 。 C#數(shù)據(jù)結(jié)構(gòu)，就此結(jié)束了，這是我的一點(diǎn)總結(jié)。
|
|
|
