色yeye在线视频观看_亚洲人亚洲精品成人网站_一级毛片免费播放_91精品一区二区中文字幕_一区二区三区日本视频_成人性生交大免费看

概述排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。

我們這里說說八大排序就是內(nèi)部排序。

當(dāng)n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序。快速排序：是目前基于比較的內(nèi)部排序中被認(rèn)為是好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間短;

1. 插入排序—直接插入排序(Straight Insertion Sort)

基本思想:

將一個(gè)記錄插入到已排序好的有序表中，從而得到一個(gè)新，記錄數(shù)增1的有序表。即：先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入，直至整個(gè)序列有序?yàn)橹埂?/p>

要點(diǎn)：設(shè)立哨兵，作為臨時(shí)存儲(chǔ)和判斷數(shù)組邊界之用。

直接插入排序示例：

如果碰見一個(gè)和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。

算法的實(shí)現(xiàn)：

//插入排序
void Insert_Sort(int *list,int count)
{
         int temp;/*此處充當(dāng)哨兵，不在list數(shù)組里面單獨(dú)占一個(gè)單位*/
         int i,j;
         for(i=1;i<count;i++)//為尋找插入位置不斷后移
         {
                   if(list[i]<list[i-1])
                   {
                            temp = list[i];
                            for(j=i-1;list[j]>temp&&j>=0;j--)//后移一位，然后從當(dāng)前位置開始比較，不斷前移，直到尋找到插入位置或者移動(dòng)到數(shù)組第一個(gè)元素
                            {
                                     list[j+1] = list[j];//不斷把前一個(gè)元素覆蓋后一個(gè)元素，跳出循環(huán)時(shí)，j即為插入位置，但是跳出循環(huán)后j--，所以后的插入位置為j + 1
                            }
                            list[j+1] = temp;//
                   }
         }
}

效率：

時(shí)間復(fù)雜度：O(n^2).

其他的插入排序有二分插入排序，2-路插入排序。

2. 插入排序—希爾排序(Shell`s Sort)

希爾排序是1959 年由D.L.Shell 提出來的，相對(duì)直接排序有較大的改進(jìn)。希爾排序又叫縮小增量排序。希爾排序是非穩(wěn)定排序算法。

基本思想：

希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序;隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。

操作方法：

排序過程：先取一個(gè)正整數(shù)d1<n，把所有序號(hào)相隔d1的數(shù)組元素放一組，組內(nèi)進(jìn)行直接插入排序;然后取d2<d1，重復(fù)上述分組和排序操作;直至di=1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹埂?/p>

希爾排序時(shí)效分析很難，關(guān)鍵碼的比較次數(shù)與記錄移動(dòng)次數(shù)依賴于增量因子序列d的選取，特定情況下可以準(zhǔn)確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動(dòng)次數(shù)。目前還沒有人給出選取好的增量因子序列的方法。增量因子序列可以有各種取法，有取奇數(shù)的，也有取質(zhì)數(shù)的，但需要注意：增量因子中除1 外沒有公因子，且后一個(gè)增量因子必須為1。希爾排序方法是一個(gè)不穩(wěn)定的排序方法。希爾排序時(shí)間復(fù)雜度的下界是n*log2n，因此中等大小規(guī)模表現(xiàn)良好。

3. 選擇排序—簡(jiǎn)單選擇排序(Simple Selection Sort)

基本思想：

在要排序的一組數(shù)中，選出小(或者大)的一個(gè)數(shù)與第1個(gè)位置的數(shù)交換;然后在剩下的數(shù)當(dāng)中再找小(或者大)的與第2個(gè)位置的數(shù)交換，依次類推，直到第n-1個(gè)元素(倒數(shù)第二個(gè)數(shù))和第n個(gè)元素(后一個(gè)數(shù))比較為止。

簡(jiǎn)單選擇排序的示例：

進(jìn)行比較操作的時(shí)間復(fù)雜度為O(n^2)，進(jìn)行移動(dòng)操作的時(shí)間復(fù)雜度為O(n)。簡(jiǎn)單選擇排序是不穩(wěn)定排序。

操作方法：

第一趟，從n 個(gè)記錄中找出關(guān)鍵碼小的記錄與第一個(gè)記錄交換;

第二趟，從第二個(gè)記錄開始的n-1 個(gè)記錄中再選出關(guān)鍵碼小的記錄與第二個(gè)記錄交換;

以此類推.....

第i 趟，則從第i 個(gè)記錄開始的n-i+1 個(gè)記錄中選出關(guān)鍵碼小的記錄與第i 個(gè)記錄交換，

直到整個(gè)序列按關(guān)鍵碼有序。

算法實(shí)現(xiàn)：
//選擇排序
void Select_Sort(int *list,int count)
{
         int min,i,j;
         for(i=0;i<count;i++)
         {
                   min = i;
                   for(j=i+1;j<count;j++)
                   {
                            if(list[min]>list[j])
                            {
                                     min = j;
                            }
                   }
                   if(min!=i)
                   {
                            swap(list[i],list[min]);
                   }
         }
}

簡(jiǎn)單選擇排序的改進(jìn)——二元選擇排序

簡(jiǎn)單選擇排序，每趟循環(huán)只能確定一個(gè)元素排序后的定位。我們可以考慮改進(jìn)為每趟循環(huán)確定兩個(gè)元素(當(dāng)前趟大和小記錄)的位置,從而減少排序所需的循環(huán)次數(shù)。改進(jìn)后對(duì)n個(gè)數(shù)據(jù)進(jìn)行排序，多只需進(jìn)行[n/2]趟循環(huán)即可。

4. 選擇排序—堆排序(Heap Sort)

堆排序是一種樹形選擇排序，是對(duì)直接選擇排序的有效改進(jìn)。

基本思想：

堆的定義如下：具有n個(gè)元素的序列(k1,k2,...,kn),當(dāng)且僅當(dāng)滿足

時(shí)稱之為堆。由堆的定義可以看出，堆頂元素(即第一個(gè)元素)必為小項(xiàng)(小頂堆)。

若以一維數(shù)組存儲(chǔ)一個(gè)堆，則堆對(duì)應(yīng)一棵完全二叉樹，且所有非葉結(jié)點(diǎn)的值均不大于(或不小于)其子女的值，根結(jié)點(diǎn)(堆頂元素)的值是小(或大)的。如：

(a)大頂堆序列：(96，83，27，38，11，09)

(b)小頂堆序列：(12，36，24，85，47，30，53，91)

初始時(shí)把要排序的n個(gè)數(shù)的序列看作是一棵順序存儲(chǔ)的二叉樹(一維數(shù)組存儲(chǔ)二叉樹)，調(diào)整它們的存儲(chǔ)序，使之成為一個(gè)堆，將堆頂元素輸出，得到n 個(gè)元素中小(或大)的元素，這時(shí)堆的根節(jié)點(diǎn)的數(shù)小(或者大)。然后對(duì)前面(n-1)個(gè)元素重新調(diào)整使之成為堆，輸出堆頂元素，得到n 個(gè)元素中次小(或次大)的元素。依此類推，直到只有兩個(gè)節(jié)點(diǎn)的堆，并對(duì)它們作交換，后得到有n個(gè)節(jié)點(diǎn)的有序序列。稱這個(gè)過程為堆排序。

因此，實(shí)現(xiàn)堆排序需解決兩個(gè)問題：

1. 如何將n 個(gè)待排序的數(shù)建成堆;

2. 輸出堆頂元素后，怎樣調(diào)整剩余n-1 個(gè)元素，使其成為一個(gè)新堆。

首先討論第二個(gè)問題：輸出堆頂元素后，對(duì)剩余n-1元素重新建成堆的調(diào)整過程。

調(diào)整小頂堆的方法：

1)設(shè)有m 個(gè)元素的堆，輸出堆頂元素后，剩下m-1 個(gè)元素。將堆底元素送入堆頂((后一個(gè)元素與堆頂進(jìn)行交換)，堆被破壞，其原因僅是根結(jié)點(diǎn)不滿足堆的性質(zhì)。

2)將根結(jié)點(diǎn)與左、右子樹中較小元素的進(jìn)行交換。

3)若與左子樹交換：如果左子樹堆被破壞，即左子樹的根結(jié)點(diǎn)不滿足堆的性質(zhì)，則重復(fù)方法 (2).

4)若與右子樹交換，如果右子樹堆被破壞，即右子樹的根結(jié)點(diǎn)不滿足堆的性質(zhì)。則重復(fù)方法 (2).

5)繼續(xù)對(duì)不滿足堆性質(zhì)的子樹進(jìn)行上述交換操作，直到葉子結(jié)點(diǎn)，堆被建成。

稱這個(gè)自根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的調(diào)整過程為篩選。如圖：

再討論對(duì)n 個(gè)元素初始建堆的過程。

建堆方法：對(duì)初始序列建堆的過程，就是一個(gè)反復(fù)進(jìn)行篩選的過程。

1)n 個(gè)結(jié)點(diǎn)的完全二叉樹，則后一個(gè)結(jié)點(diǎn)是第個(gè)結(jié)點(diǎn)的子樹。

2)篩選從第個(gè)結(jié)點(diǎn)為根的子樹開始，該子樹成為堆。

3)之后向前依次對(duì)各結(jié)點(diǎn)為根的子樹進(jìn)行篩選，使之成為堆，直到根結(jié)點(diǎn)。

如圖建堆初始過程：無序序列：(49，38，65，97，76，13，27，49)

算法的實(shí)現(xiàn)：

從算法描述來看，堆排序需要兩個(gè)過程，一是建立堆，二是堆頂與堆的后一個(gè)元素交換位置。所以堆排序有兩個(gè)函數(shù)組成。一是建堆的滲透函數(shù)，二是反復(fù)調(diào)用滲透函數(shù)實(shí)現(xiàn)排序的函數(shù)。
//調(diào)整為一個(gè)堆
void Heap_Adjust(int *list,int s,int m)
{
         int temp = list[s];
         for(int j=2*s+1;j<=m;j = 2*j+1)
         {
                   if(list[j]<list[j+1]&&j<m)
                   {
                            j++;
                   }
                   if(temp>list[j])
                            break;
                   list[s] = list[j];
                   s = j;
         }
         list[s] = temp;
}
 
//堆排序
void Heap_Sort(int *list,int len)
{
         //創(chuàng)建一個(gè)大頂堆
         for(int s = len/2-1;s>=0;s--)
         {
                   Heap_Adjust(list,s,len-1);
         }
 
         //排序
         for(int i = len-1;i >= 1;i--)
         {
                   swap(list[0],list[i]);
                   Heap_Adjust(list,0,i-1);
         }
}

分析:

設(shè)樹深度為k，。從根到葉的篩選，元素比較次數(shù)至多2(k-1)次，交換記錄至多k 次。所以，在建好堆后，排序過程中的篩選次數(shù)不超過下式：

而建堆時(shí)的比較次數(shù)不超過4n 次，因此堆排序壞情況下，時(shí)間復(fù)雜度也為：O(nlogn )。

由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是就地排序，輔助空間為O(1)，它是不穩(wěn)定的排序方法。

5. 交換排序—冒泡排序(Bubble Sort)

基本思想：

在要排序的一組數(shù)中，對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對(duì)相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換。

冒泡排序的示例：

算法的實(shí)現(xiàn)：
//冒泡排序
void Bubble_Sort(int *list,int count)
{
         int flag = true;
         int i = 0,j = 0;
         for(i=0;i<=count&&flag;i++)
         {
                   flag = false;
                   for(j=count -1;j>=i;j--)
                   {
                            if(list[j]<list[j-1])
                            {
                            swap(list[j],list[j-1]);
                            flag = true;
                            }
                   }
         }
}

冒泡排序算法的改進(jìn)

對(duì)冒泡排序常見的改進(jìn)方法是加入一標(biāo)志性變量exchange，用于標(biāo)志某一趟排序過程中是否有數(shù)據(jù)交換，如果進(jìn)行某一趟排序時(shí)并沒有進(jìn)行數(shù)據(jù)交換，則說明數(shù)據(jù)已經(jīng)按要求排列好，可立即結(jié)束排序，避免不必要的比較過程。本文再提供以下兩種改進(jìn)算法：

1.設(shè)置一標(biāo)志性變量pos,用于記錄每趟排序中后一次進(jìn)行交換的位置。由于pos位置之后的記錄均已交換到位,故在進(jìn)行下一趟排序時(shí)只要掃描到pos位置即可。

2.傳統(tǒng)冒泡排序中每一趟排序操作只能找到一個(gè)大值或小值,我們考慮利用在每趟排序中進(jìn)行正向和反向兩遍冒泡的方法一次可以得到兩個(gè)終值(大者和小者) , 從而使排序趟數(shù)幾乎減少了一半。

6. 交換排序—快速排序(Quick Sort)

基本思想：

一趟快速排序的算法是：

1)設(shè)置兩個(gè)變量i、j，排序開始的時(shí)候：i=0，j=N-1;

2)以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0];

3)從j開始向前搜索，即由后開始向前搜索(j--)，找到第一個(gè)小于key的值A(chǔ)[j]，將A[j]和A[i]互換;

4)從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個(gè)大于key的A[i]，將A[i]和A[j]互換;

5)重復(fù)第3、4步，直到i=j; (3,4步中，沒找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時(shí)候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進(jìn)行交換的時(shí)候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時(shí)候，此時(shí)令循環(huán)結(jié)束)。

(a)一趟排序的過程：

算法的實(shí)現(xiàn)：
//快速排序
int Partition(int *list,int low,int high)
{
         int pivotKey;
         pivotKey = list[low];
         while(low<high)
         {
                   while(low<high&&list[high]>=pivotKey)
                   {
                            high--;
                   }
                   swap(list[low],list[high]);
                   while(low<high&&list[low]<=pivotKey)
                   {
                            low++;
                   }
                   swap(list[low],list[high]);
         }
         return low;
}
 
void Qsort(int *list,int low,int high)
{
         int pivot;
         if(low<high)
         {
                   pivot =Partition(list,low,high);
                   Qsort(list,low,pivot-1);
                   Qsort(list,pivot+1,high);
         }
}
 
void Quick_Sort(int *list,int count)
{
         Qsort(list,0,count-1);
}

分析：

快速排序是通常被認(rèn)為在同數(shù)量級(jí)(O(nlog2n))的排序方法中平均性能好的。但若初始序列按關(guān)鍵碼有序或基本有序時(shí)，快排序反而蛻化為冒泡排序。為改進(jìn)之，通常以“三者取中法”來選取基準(zhǔn)記錄，即將排序區(qū)間的兩個(gè)端點(diǎn)與中點(diǎn)三個(gè)記錄關(guān)鍵碼居中的調(diào)整為支點(diǎn)記錄�？焖倥判蚴且粋�(gè)不穩(wěn)定的排序方法。

快速排序的改進(jìn)

在本改進(jìn)算法中,只對(duì)長(zhǎng)度大于k的子序列遞歸調(diào)用快速排序,讓原序列基本有序，然后再對(duì)整個(gè)基本有序序列用插入排序算法排序。實(shí)踐證明，改進(jìn)后的算法時(shí)間復(fù)雜度有所降低，且當(dāng)k取值為 8 左右時(shí),改進(jìn)算法的性能佳。

7. 歸并排序(Merge Sort)

基本思想：

歸并(Merge)排序法是將兩個(gè)(或兩個(gè)以上)有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。

歸并排序示例：

合并方法：

設(shè)r[i…n]由兩個(gè)有序子表r[i…m]和r[m+1…n]組成，兩個(gè)子表長(zhǎng)度分別為n-i +1、n-m。

1.j=m+1;k=i;i=i; //置兩個(gè)子表的起始下標(biāo)及輔助數(shù)組的起始下標(biāo)

2.若i>m 或j>n，轉(zhuǎn)⑷ //其中一個(gè)子表已合并完，比較選取結(jié)束

3.//選取r[i]和r[j]較小的存入輔助數(shù)組rf

如果r[i]<r[j]，rf[k]=r[i]; i++; k++; 轉(zhuǎn)⑵

否則，rf[k]=r[j]; j++; k++; 轉(zhuǎn)⑵

4.//將尚未處理完的子表中元素存入rf

如果i<=m，將r[i…m]存入rf[k…n] //前一子表非空

如果j<=n , 將r[j…n] 存入rf[k…n] //后一子表非空

5.合并結(jié)束。
//歸并排序
//將兩個(gè)有序數(shù)組排序
void Merge(int *list,int start,int mid,int end)
{
         const int len1 = mid -start +1;
         const int len2 = end -mid;
         const int len = end - start +1;
         int i,j,k;
 
         int * front = (int *)malloc(sizeof(int)*len1);
         int * back = (int *)malloc(sizeof(int)*len2);
 
         for(i=0;i<len1;i++)
                   front[i] = list[start+i];
         for(j=0;j<len2;j++)
                   back[j] = list[mid+j+1];
 
         for(i=0,j=0,k=start;i<len1&&j<len2&&k<end;k++)
         {
                   if(front[i]<back[j])
                   {
                            list[k] = front[i];
                            i++;
                   }
else
                   {
                            list[k] = back[j];
                            j++;
                   }
         }
         while(i<len1)
         {
                   list[k++] = front[i++];
         }
         while(j<len2)
         {
                   list[k++] = back[j++];
         }
} 
 
void MSort(int *list,int start,int end)
{
         if(start<end)
         {
                   int mid = (start+end)/2;
                   MSort(list,0,mid);
                   MSort(list,mid+1,end);
                   Merge(list,start,mid,end);
         }
}
 
void Merge_Sort(int *list,int count)
{
         MSort(list,0,count-1);
}

8. 桶排序/基數(shù)排序(Radix Sort)

說基數(shù)排序之前，我們先說桶排序：

基本思想(桶排序)：

是將陣列分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序(有可能再使用別的排序算法或是以遞回方式繼續(xù)使用桶排序進(jìn)行排序)。桶排序是鴿巢排序的一種歸納結(jié)果。當(dāng)要被排序的陣列內(nèi)的數(shù)值是均勻分配的時(shí)候，桶排序使用線性時(shí)間(Θ(n))。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。

簡(jiǎn)單來說，就是把數(shù)據(jù)分組，放在一個(gè)個(gè)的桶中，然后對(duì)每個(gè)桶里面的在進(jìn)行排序。

例如要對(duì)大小為[1..1000]范圍內(nèi)的n個(gè)整數(shù)A[1..n]排序

首先，可以把桶設(shè)為大小為10的范圍，具體而言，設(shè)集合B[1]存儲(chǔ)[1..10]的整數(shù)，集合B[2]存儲(chǔ)(10..20]的整數(shù)，……集合B[i]存儲(chǔ)((i-1)*10, i*10]的整數(shù)，i = 1,2,..100。總共有100個(gè)桶。

然后，對(duì)A[1..n]從頭到尾掃描一遍，把每個(gè)A[i]放入對(duì)應(yīng)的桶B[j]中。再對(duì)這100個(gè)桶中每個(gè)桶里的數(shù)字排序，這時(shí)可用冒泡，選擇，乃至快排，一般來說任何排序法都可以。

后，依次輸出每個(gè)桶里面的數(shù)字，且每個(gè)桶中的數(shù)字從小到大輸出，這樣就得到所有數(shù)字排好序的一個(gè)序列了。

假設(shè)有n個(gè)數(shù)字，有m個(gè)桶，如果數(shù)字是平均分布的，則每個(gè)桶里面平均有n/m個(gè)數(shù)字。如果對(duì)每個(gè)桶中的數(shù)字采用快速排序，那么整個(gè)算法的復(fù)雜度是

O(n+ m * n/m*log(n/m)) = O(n + nlogn - nlogm)

從上式看出，當(dāng)m接近n的時(shí)候，桶排序復(fù)雜度接近O(n)

當(dāng)然，以上復(fù)雜度的計(jì)算是基于輸入的n個(gè)數(shù)字是平均分布這個(gè)假設(shè)的。這個(gè)假設(shè)是很強(qiáng)的，實(shí)際應(yīng)用中效果并沒有這么好。如果所有的數(shù)字都落在同一個(gè)桶中，那就退化成一般的排序了。

前面說的幾大排序算法 ，大部分時(shí)間復(fù)雜度都是O(n2)，也有部分排序算法時(shí)間復(fù)雜度是O(nlogn)。而桶式排序卻能實(shí)現(xiàn)O(n)的時(shí)間復(fù)雜度。但桶排序的缺點(diǎn)是：

1)首先是空間復(fù)雜度比較高，需要的額外開銷大。排序有兩個(gè)數(shù)組的空間開銷，一個(gè)存放待排序數(shù)組，一個(gè)就是所謂的桶，比如待排序值是從0到m-1，那就需要m個(gè)桶，這個(gè)桶數(shù)組就要至少m個(gè)空間。

2)其次待排序的元素都要在一定的范圍內(nèi)等等。

桶式排序是一種分配排序。分配排序的特定是不需要進(jìn)行關(guān)鍵碼的比較，但前提是要知道待排序列的一些具體情況。

分配排序的基本思想：說白了就是進(jìn)行多次的桶式排序。

基數(shù)排序過程無須比較關(guān)鍵字，而是通過“分配”和“收集”過程來實(shí)現(xiàn)排序。它們的時(shí)間復(fù)雜度可達(dá)到線性階：O(n)。

實(shí)例:

撲克牌中52 張牌，可按花色和面值分成兩個(gè)字段，其大小關(guān)系為：

花色： 梅花< 方塊< 紅心< 黑心  

面值： 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

若對(duì)撲克牌按花色、面值進(jìn)行升序排序，得到如下序列：

即兩張牌，若花色不同，不論面值怎樣，花色低的那張牌小于花色高的，只有在同花色情況下，大小關(guān)系才由面值的大小確定。這就是多關(guān)鍵碼排序。

為得到排序結(jié)果，我們討論兩種排序方法。

方法1：先對(duì)花色排序，將其分為4 個(gè)組，即梅花組、方塊組、紅心組、黑心組。再對(duì)每個(gè)組分別按面值進(jìn)行排序，后，將4 個(gè)組連接起來即可。

方法2：先按13 個(gè)面值給出13 個(gè)編號(hào)組(2 號(hào)，3 號(hào)，...，A 號(hào))，將牌按面值依次放入對(duì)應(yīng)的編號(hào)組，分成13 堆。再按花色給出4 個(gè)編號(hào)組(梅花、方塊、紅心、黑心)，將2號(hào)組中牌取出分別放入對(duì)應(yīng)花色組，再將3 號(hào)組中牌取出分別放入對(duì)應(yīng)花色組，……，這樣，4 個(gè)花色組中均按面值有序，然后，將4 個(gè)花色組依次連接起來即可。

設(shè)n 個(gè)元素的待排序列包含d 個(gè)關(guān)鍵碼{k1，k2，…，kd}，則稱序列對(duì)關(guān)鍵碼{k1，k2，…，kd}有序是指：對(duì)于序列中任兩個(gè)記錄r[i]和r[j](1≤i≤j≤n)都滿足下列有序關(guān)系：

其中k1 稱為主位關(guān)鍵碼，kd 稱為次位關(guān)鍵碼 。

兩種多關(guān)鍵碼排序方法：

多關(guān)鍵碼排序按照從主位關(guān)鍵碼到次位關(guān)鍵碼或從次位到主位關(guān)鍵碼的順序逐次排序，分兩種方法：

高位優(yōu)先(Most Significant Digit first)法，簡(jiǎn)稱MSD 法：

1)先按k1 排序分組，將序列分成若干子序列，同一組序列的記錄中，關(guān)鍵碼k1 相等。

2)再對(duì)各組按k2 排序分成子組，之后，對(duì)后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按次位關(guān)鍵碼kd 對(duì)各子組排序后。

3)再將各組連接起來，便得到一個(gè)有序序列。撲克牌按花色、面值排序中介紹的方法一即是MSD 法。

低位優(yōu)先(Least Significant Digit first)法，簡(jiǎn)稱LSD 法：

1) 先從kd 開始排序，再對(duì)kd-1進(jìn)行排序，依次重復(fù)，直到按k1排序分組分成小的子序列后。

2) 后將各個(gè)子序列連接起來，便可得到一個(gè)有序的序列, 撲克牌按花色、面值排序中介紹的方法二即是LSD 法。

基于LSD方法的鏈?zhǔn)交鶖?shù)排序的基本思想

“多關(guān)鍵字排序”的思想實(shí)現(xiàn)“單關(guān)鍵字排序”。對(duì)數(shù)字型或字符型的單關(guān)鍵字，可以看作由多個(gè)數(shù)位或多個(gè)字符構(gòu)成的多關(guān)鍵字，此時(shí)可以采用“分配-收集”的方法進(jìn)行排序，這一過程稱作基數(shù)排序法，其中每個(gè)數(shù)字或字符可能的取值個(gè)數(shù)稱為基數(shù)。比如，撲克牌的花色基數(shù)為4，面值基數(shù)為13。在整理?yè)淇伺茣r(shí)，既可以先按花色整理，也可以先按面值整理。按花色整理時(shí)，先按紅、黑、方、花的順序分成4摞(分配)，再按此順序再疊放在一起(收集)，然后按面值的順序分成13摞(分配)，再按此順序疊放在一起(收集)，如此進(jìn)行二次分配和收集即可將撲克牌排列有序。

基數(shù)排序:

是按照低位先排序，然后收集;再按照高位排序，然后再收集;依次類推，直到高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的，先按低優(yōu)先級(jí)排序，再按高優(yōu)先級(jí)排序。后的次序就是高優(yōu)先級(jí)高的在前，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前。基數(shù)排序基于分別排序，分別收集，所以是穩(wěn)定的。

算法實(shí)現(xiàn)：
#define MAX 20
#define BASE 10
void Radix_Sort(int *a, int n)
{
         int i, b[MAX], m = a[0], exp = 1;
         for (i = 1; i < n; i++)
{
                   if (a[i] > m)
{
                            m = a[i];
                   }
         }
         while (m / exp > 0)
{
                   int bucket[BASE] = { 0 };
                   for (i = 0; i < n; i++)
{
                            bucket[(a[i] / exp) % BASE]++;
                   }
 
                   for (i = 1; i < BASE; i++)
{
                            bucket[i] += bucket[i - 1];
                   }
                   for (i = n - 1; i >= 0; i--)
{
                            b[--bucket[(a[i] / exp) % BASE]] = a[i];
                   }
 
                   for (i = 0; i < n; i++)
{
                            a[i] = b[i];
                   }
                   exp *= BASE;
         }
}

總結(jié):

各種排序的穩(wěn)定性，時(shí)間復(fù)雜度和空間復(fù)雜度總結(jié)：

我們比較時(shí)間復(fù)雜度函數(shù)的情況：

時(shí)間復(fù)雜度函數(shù)O(n)的增長(zhǎng)情況

所以對(duì)n較大的排序記錄。一般的選擇都是時(shí)間復(fù)雜度為O(nlog2n)的排序方法。

時(shí)間復(fù)雜度來說：

(1)平方階(O(n2))排序

各類簡(jiǎn)單排序:直接插入、直接選擇和冒泡排序;

(2)線性對(duì)數(shù)階(O(nlog2n))排序

快速排序、堆排序和歸并排序;

(3)O(n1+§))排序,§是介于0和1之間的常數(shù)。

希爾排序

(4)線性階(O(n))排序

基數(shù)排序，此外還有桶、箱排序。

說明：

當(dāng)原表有序或基本有序時(shí)，直接插入排序和冒泡排序?qū)⒋蟠鬁p少比較次數(shù)和移動(dòng)記錄的次數(shù)，時(shí)間復(fù)雜度可降至O(n);而快速排序則相反，當(dāng)原表基本有序時(shí)，將蛻化為冒泡排序，時(shí)間復(fù)雜度提高為O(n2);原表是否有序，對(duì)簡(jiǎn)單選擇排序、堆排序、歸并排序和基數(shù)排序的時(shí)間復(fù)雜度影響不大。

穩(wěn)定性：

排序算法的穩(wěn)定性:若待排序的序列中，存在多個(gè)具有相同關(guān)鍵字的記錄，經(jīng)過排序， 這些記錄的相對(duì)次序保持不變，則稱該算法是穩(wěn)定的;若經(jīng)排序后，記錄的相對(duì) 次序發(fā)生了改變，則稱該算法是不穩(wěn)定的。

穩(wěn)定性的好處：排序算法如果是穩(wěn)定的，那么從一個(gè)鍵上排序，然后再?gòu)牧硪粋�(gè)鍵上排序，第一個(gè)鍵排序的結(jié)果可以為第二個(gè)鍵排序所用�；鶖�(shù)排序就是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時(shí)是不會(huì)改變的。另外，如果排序算法穩(wěn)定，可以避免多余的比較;

穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序

不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序

選擇排序算法準(zhǔn)則：

每種排序算法都各有優(yōu)缺點(diǎn)。因此，在實(shí)用時(shí)需根據(jù)不同情況適當(dāng)選用，甚至可以將多種方法結(jié)合起來使用。

選擇排序算法的依據(jù)

影響排序的因素有很多，平均時(shí)間復(fù)雜度低的算法并不一定就是優(yōu)的。相反，有時(shí)平均時(shí)間復(fù)雜度高的算法可能更適合某些特殊情況。同時(shí)，選擇算法時(shí)還得考慮它的可讀性，以利于軟件的維護(hù)。一般而言，需要考慮的因素有以下四點(diǎn)：

1.待排序的記錄數(shù)目n的大小;

2.記錄本身數(shù)據(jù)量的大小，也就是記錄中除關(guān)鍵字外的其他信息量的大小;

3.關(guān)鍵字的結(jié)構(gòu)及其分布情況;

4.對(duì)排序穩(wěn)定性的要求。

設(shè)待排序元素的個(gè)數(shù)為n.

1)當(dāng)n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。

快速排序：是目前基于比較的內(nèi)部排序中被認(rèn)為是好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間短;

堆排序：如果內(nèi)存空間允許且要求穩(wěn)定性的，

歸并排序：它有一定數(shù)量的數(shù)據(jù)移動(dòng)，所以我們可能過與插入排序組合，先獲得一定長(zhǎng)度的序列，然后再合并，在效率上將有所提高。

2)當(dāng)n較大，內(nèi)存空間允許，且要求穩(wěn)定性 =》歸并排序

3)當(dāng)n較小，可采用直接插入或直接選擇排序。

直接插入排序：當(dāng)元素分布有序，直接插入排序?qū)⒋蟠鬁p少比較次數(shù)和移動(dòng)記錄的次數(shù)。

直接選擇排序 ：元素分布有序，如果不要求穩(wěn)定性，選擇直接選擇排序

4)一般不使用或不直接使用傳統(tǒng)的冒泡排序。

5)基數(shù)排序

它是一種穩(wěn)定的排序算法，但有一定的局限性：

1、關(guān)鍵字可分解。

2、記錄的關(guān)鍵字位數(shù)較少，如果密集更好

3、如果是數(shù)字時(shí)，好是無符號(hào)的，否則將增加相應(yīng)的映射復(fù)雜度，可先將其正負(fù)分開排序。