亚洲视频二区_亚洲欧洲日本天天堂在线观看_日韩一区二区在线观看_中文字幕不卡一区

排序的相關(guān)概念

排序的分類

• 根據(jù)在排序過程中帶排序的記錄是否全部被放置在內(nèi)存中，排序分為：
• 內(nèi)排序
• 外排序

1.內(nèi)排序

內(nèi)排序是在排序整個(gè)過程中，帶排序的所有記錄全部放置在內(nèi)存中。

影響內(nèi)排序的主要因素

• 時(shí)間性能。
• (主要受比較和移動(dòng)兩種操作的影響）
• 輔助空間。
• 算法的復(fù)雜性。

內(nèi)排序的分類

根據(jù)排序過程中借助的主要操作，內(nèi)排序分為：

• 插入排序
• 交換排序
• 選擇排序
• 歸并排序

2.外排序

外排序是由于排序的記錄個(gè)數(shù)太多，不能同時(shí)放置在內(nèi)存中，整個(gè)排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能進(jìn)行。

按照算法的復(fù)雜度分類

• 簡單算法：
• 冒泡排序、簡單選擇排序、直接插入排序。
• 復(fù)雜排序：
• 希爾排序、堆排序、歸并排序、快速排序。

 

---

 

一、冒泡排序算法

因?yàn)樵诿芭菖判蛑幸玫?strong>順序表結(jié)構(gòu)和數(shù)組兩元素的交換，先把這些寫成函數(shù)

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define TRUE 1
#define FALSE 0
typedef struct {
 
 int r[MAXSIZE + 1];
 int length;
}SqList;
void swap(SqList *L, int i, int j){
 int temp = L->r[i];
 L->r[i] = L->r[j];
 L->r[j] = temp;
}

1.1 冒泡排序的初級版實(shí)現(xiàn)

冒泡排序（Bubble Sort）是一種交換排序，它的基本思想是：兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換，直到?jīng)]有反序的記錄為止。

•  

void BubblSort0(SqList *L){
 int i,j;
 
 for (i = 1; i < L->length; i++)
 for (j = i+1; j <= L->length; j++)
 if (L->r[i] > L->r[j])
 swap(L, i, j);
}

對于這段代碼，是最簡單的冒泡，其實(shí)就是最簡單的交換排序而已。它的思路就是讓每一個(gè)關(guān)鍵字，都和它后面的每一個(gè)關(guān)鍵字比較，如果大則交換，這樣第一位置的關(guān)鍵字在第一次循環(huán)后一定變成最小值。

假設(shè)我們待排序的關(guān)鍵字序列是{9，1，5，8，3，7，4，6，2}

• 當(dāng)i = 1時(shí)，9與1交換后，在第一位置的1與后面的關(guān)鍵字比較都小，因此它就只最小值。
• 當(dāng)i = 2時(shí)，第二位置先后由9換成5，換成3，換成2，完成了第二小的數(shù)字交換。
• 后面數(shù)字依次比較和交換，得到最終結(jié)果。

 

 

 

1.2 冒泡排序的實(shí)現(xiàn)

對于上面的算法，代碼雖然簡單易懂，但是效率非常低。可以改進(jìn)成接下來的代碼

•  

void BubbleSort(SqList *L){
 int i,j;
 for (i = 1; i < L->length; i++)
 for (j = L->length - 1; j >= i; j--)
 if (L->r[j] > L->r[j+1])
 swap(L, j, j+1);
}

代碼解釋

假設(shè)我們待排序的關(guān)鍵字序列是{9，1，5，8，3，7，4，6，2}

• 當(dāng)i = 1時(shí)，變量j由8反向循環(huán)到1，逐個(gè)比較，將較小值交換到前面，直到最后找到最小值放置在了第1的位置。
• 當(dāng)i = 1、 j = 8時(shí)，6 > 2 ，因此交換了它們的位置，j = 7時(shí)，4 > 2， 所以交換......直到j(luò) = 2時(shí)，因?yàn)?1 < 2， 所以不交換。
• j = 1 時(shí)，9 > 1，交換，最終得到最小值1放置第一的位置。
• 在不斷循環(huán)的過程中，除了將關(guān)鍵字1放到第一的位置，還將關(guān)鍵字2從第九位置提到了第三的位置，顯然比前面的算法有進(jìn)步。
• 當(dāng)i = 2時(shí)，變量j由8反向循環(huán)到2，逐個(gè)比較，在將關(guān)鍵字2交換到第二位置的同時(shí)，也將關(guān)鍵字4和3有所提升。

1.3 冒泡排序的優(yōu)化

• 在排序的過程中，增加一個(gè)標(biāo)記變量flag來記錄位置是否發(fā)生了變化
• 如果沒有發(fā)生交換，說明數(shù)組已經(jīng)有序了。
•  

void BubbleSort1(SqList *L){
 int i,j;
 
 int flag = TRUE;
 for (i = 1; i < L->length && flag; i++) {
 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;
 }
 }
 }
}

測試

#define N 9
int main(int argc, const char * argv[]) {
 
 int i;
 int d[N] = {9,1,5,8,3,7,4,6,2};
 
 SqList l0;
 for (i = 0; i < N; i++)
 l0.r[i+1] = d[i];
 l0.length = N;
 
 printf("排序前：
");
 for (i = 0; i < l0.length; i++) {
 printf("%d ", l0.r[i+1]);
 }
 printf("
");
 
 printf("1.0 初級冒泡排序結(jié)果:
");
 BubblSort0(&l0);
 for (i = 0; i < l0.length; i++) {
 printf("%d ", l0.r[i+1]);
 }
 printf("
");
 
 printf("1.1 冒泡排序結(jié)果:
");
 BubbleSort(&l0);
 for (i = 0; i < l0.length; i++) {
 printf("%d ", l0.r[i+1]);
 }
 printf("
");
 printf("1.2 優(yōu)化后冒泡排序結(jié)果:
");
 BubbleSort1(&l0);
 for (i = 0; i < l0.length; i++) {
 printf("%d ", l0.r[i+1]);
 }
 printf("
");
 return 0;
}

測試結(jié)果

 

 

---

 

二、簡單選擇排序

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

簡單選擇排序法的工作原理是：每一次從無序組的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，存放在無序組的起始位置，無序組元素減少，有序組元素增加，直到全部待排序的數(shù)據(jù)元素排完。

•  

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) 
 swap(L, i, min);
 }
}

代碼說明

• 簡單選擇排序相對簡單，交換移動(dòng)數(shù)據(jù)的次數(shù)相當(dāng)少，節(jié)約時(shí)間。
• 簡單選擇排序的時(shí)間復(fù)雜度為O(n^2)。

---

 

三、直接插入排序

直接插入排序(Straight Insertion Sort)的基本操作是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而得到一個(gè)新的、記錄增1的有序表。

直接插入排序的核心思想：將一個(gè)記錄插入到一個(gè)已經(jīng)排序好的表中，以得到一個(gè)記錄增加1的有序表。并且它把當(dāng)前元素大的記錄都往后移動(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[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];
 }
 }
}

代碼說明

• 直接插入排序的時(shí)間復(fù)雜度為O(n^2)。
• 直接插入排序比冒泡和簡單選擇排序的性能要好一些。

---

 

四、希爾排序

希爾排序是對直接插入排序的改進(jìn)：

• 將原本有大量記錄數(shù)的記錄進(jìn)行分組。分割成若干個(gè)子序列；
• 對子序列分別進(jìn)行直接插入排序；
• 當(dāng)整個(gè)序列都基本有序時(shí)（注意是基本有序），再對全體記錄進(jìn)行一次直接插入排序。
• 所謂的基本有序，就是小的關(guān)鍵字基本在前，大的基本在后面，不大不小的基本在中間，如{9,1,5,8,3,7,5,6,2}，變成{2,1,3,6,4,7,8,9}這樣就是基本有序，但是像{1,5,9,7,8,2,4,6}這樣9在第三位，2在倒數(shù)第三位就不是基本有序。
• 對于分割子序列，采取跳躍分割的策略：
• 將相距某個(gè)“增量”的記錄組成一個(gè)子序列，這樣才能保證在子序列內(nèi)分別進(jìn)行直接插入排序后得到的結(jié)果是基本有序而不是局部有序。
• 增量的選取非常關(guān)鍵，但是現(xiàn)在還是一個(gè)數(shù)學(xué)難題(迄今沒有找到一種最好的增量序列),大量研究表明，增量序列為dlta[k] = 2^(t-k+1) - 1時(shí)，可以獲得不錯(cuò)的效果。

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

•  

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[0] = 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);
}

代碼說明

• 希爾排序的時(shí)間復(fù)雜度為O(n^(3/2))，要好于直接插入排序的O(n^2);
• 增量的最后一個(gè)增量之必須等于1才行。
• 由于記錄是跳躍式的移動(dòng)，所以希爾排序不是一種穩(wěn)定的排序算法。

---

 

五、堆排序

堆的概念

堆是具有如下性質(zhì)的完全二叉樹：

• 每個(gè)結(jié)點(diǎn)的值都大于或等于其其左右孩子結(jié)點(diǎn)的值，為大頂堆。
• 或者每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值，稱為小頂堆。
• 因此根節(jié)點(diǎn)一定是堆中所有結(jié)點(diǎn)最大（小）者。
• 如圖左邊為大頂堆，右邊為小頂堆：

 

•  
• 左邊為大頂堆，右邊為小頂堆

 

堆排序算法

堆排序（Heap Sort）是利用堆（假設(shè)是大頂堆）進(jìn)行排序。

堆排序的核心思想：

• 將待排序的序列構(gòu)造成一個(gè)大頂堆。
• 此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)。
• 將根節(jié)點(diǎn)移走(其實(shí)就是將它與堆數(shù)組的末尾元素交換，此時(shí)末尾元素就是最大值)，然后將剩余的n-1個(gè)序列重新構(gòu)造成一個(gè)堆，這樣就會(huì)得到n個(gè)元素的次小值。
• 重復(fù)上訴操作，便能得到一個(gè)有序序列。

 

 

 

堆排序算法核心

• 如何由一個(gè)無序序列構(gòu)建成一個(gè)堆
• 如何在輸出堆頂元素后，調(diào)整剩余元素成一個(gè)新的堆

堆排序算法代碼實(shí)現(xiàn)

•  

void HeadAdjust(SqList *L, int s, int m){
 int temp, j;
 temp = L->r[s];
 
 for (j = 2 *s; j <= m; j *= 2) {
 
 if (j < m && L->r[j] < L->r[j+1])
 j++;
 
 if (temp >= L->r[j])
 break;
 
 L->r[s] = L->r[j];
 s = j;
 }
 
 L->r[s] = temp;
}
void HeapSort(SqList *L){
 int i;
 
 for (i = L->length / 2; i>0; i--)
 HeadAdjust(L, i, L->length);
 
 for (i = L->length; i > 1; i--) {
 swap(L, 1, i);
 HeadAdjust(L, 1, i-1);
 }
}

堆排序算法代碼說明

• 堆排序方法HeapSort中有兩個(gè)for循環(huán)：
• 第一個(gè)for循環(huán)完成將現(xiàn)在的待排序序列構(gòu)建成一個(gè)大頂堆；
• 第二個(gè)for循環(huán)完成逐漸將每個(gè)最大值的根節(jié)點(diǎn)與末尾元素交換，并且再調(diào)整其成為大頂堆。
• 第一個(gè)for循環(huán)中的i = L->length / 2,i從[9/2]=4開始，4->3->2->1的變化量。
• （這里賦值的原因是這些都是有孩子的結(jié)點(diǎn)）
• 構(gòu)建好有孩子的結(jié)點(diǎn)之后，就可以從上到下、從左到右，將每個(gè)將每個(gè)非終端結(jié)點(diǎn)（非葉子結(jié)點(diǎn)）當(dāng)做根節(jié)點(diǎn),將其和子樹調(diào)整成大頂堆。
• 函數(shù)HeadAdjust的作用是將數(shù)組構(gòu)建成一個(gè)大頂堆，在構(gòu)建的時(shí)候利用了二叉樹的性質(zhì)。
• 構(gòu)建堆的時(shí)間復(fù)雜度為O(n)，重建堆的時(shí)間復(fù)雜度為O(nlogn)，所以總體來說堆排序的時(shí)間復(fù)雜度為O(nlogn)，性能上遠(yuǎn)好于冒泡、簡單選擇、直接插入的時(shí)間復(fù)雜度。
• 在空間復(fù)雜度上，由于記錄的交換和比較是跳躍式進(jìn)行的，所以堆排序是一種不穩(wěn)定的排序方法。

---

 

六、歸并排序

歸并排序(Merging Sort)是利用歸并的思想實(shí)現(xiàn)的。2路歸并排序的核心思想如下：

• 假設(shè)初始序列有n個(gè)記錄，則可以看成是n個(gè)有序的子序列，每個(gè)子序列的長度為1，然后兩兩歸并，得到n/2個(gè)長度為2或者1的有序子序列
• 再兩兩歸并...如此重復(fù)，直至得到一個(gè)長度為n的有序序列為止。

6.1歸并排序的實(shí)現(xiàn)思路（遞歸實(shí)現(xiàn)）

• 將序列平均分成兩部分
• 分別對這兩部分用遞歸來歸并
• 將這兩部分歸并到一起

歸并排序的代碼實(shí)現(xiàn)（遞歸實(shí)現(xiàn)）

•  

#pragma - 6.歸并排序(遞歸實(shí)現(xià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++) {
 
 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];
 }
 
 if (j <= n) {
 for (l=0; l <= n-j; l++)
 TR[k+l] = SR[j+l];
 }
}
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;
 MSort(SR, TR2, s, m);
 MSort(SR, TR2, m+1, t);
 Merge(TR2, TR1, s, m, t);
 }
}
void MergeSort(SqList *L){
 MSort(L->r, L->r, 1, L->length);
}

 

歸并排序的總結(jié)（遞歸實(shí)現(xiàn)）

• 歸并排序總的時(shí)間復(fù)雜度為O(nlogn)，并且這是歸并排序算法中最好、最壞、平均的時(shí)間性能。
• 歸并排序的空間復(fù)雜度為O(n+logn)
• 歸并排序是一種比較占內(nèi)存，但是效率高且穩(wěn)定的算法。

6.2歸并排序的實(shí)現(xiàn)（迭代非遞歸實(shí)現(xiàn)）

用迭代實(shí)現(xiàn)的話，可以從最小的序列開始?xì)w并直到完成。

•  

#pragma - 7.歸并排序（迭代實(shí)現(xiàn)）
void MergePass(int SR[], int TR[], int s, int n){
 
 int i = 1;
 int j;
 
 while (i <= n-2*s+1) {
 Merge(SR, TR, i, i+s-1, i+2*s-1);
 i = i+2*s;
 }
 
 if (i < n-s+1)
 Merge(SR, TR, i, i+s-1, n);
 else
 for (j = i; j <= n; j++)
 TR[j] = SR[j];
}
void MergeSort2(SqList *L){
 
 int * TR = (int *)malloc(sizeof(L->length*sizeof(int)));
 int k = 1;
 
 while (k < L->length) {
 MergePass(L->r, TR, k, L->length);
 k = 2*k;
 
 MergePass(TR, L->r, k, L->length);
 k = 2*k;
 }
}

 

歸并的迭代實(shí)現(xiàn)總結(jié)

• 非遞歸的迭代方法，避免了遞歸時(shí)深度為log2n的棧空間，空間只是用到申請歸并臨時(shí)用的TR數(shù)組，因此空間復(fù)雜度為O(n).
• 并且相對于遞歸，在時(shí)間性能上也有一定的提升，所以使用歸并時(shí)，盡量使用非遞歸實(shí)現(xiàn)。

---

 

七、快速排序

快速排序(Quick Sort)的基本思想是：

• 通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分
• 其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小；
• 則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序的目的。

快速排序的實(shí)現(xiàn)思路

• 選取一個(gè)關(guān)鍵字，放到一個(gè)位置，使得它的左邊的值都比它小，右邊的值都比它大，這個(gè)關(guān)鍵字叫做樞軸（pivot)
• 然后分別對左邊和右邊進(jìn)行排序。

快速排序的代碼實(shí)現(xiàn)

•  

#pragma - 8.快速排序
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;
}
void QSort(SqList *L, int low, int high){
 
 int pivot;
 if (low < high) {
 pivot = Partition(L, low, high);
 QSort(L, low, pivot-1);
 QSort(L, pivot+1, high);
 }
}
void QuickSort(SqList *L){
 QSort(L, 1, L->length);
}

 

快速排序的代碼說明

• Partition函數(shù)就是將選取的pivotkey不斷交換，將比它小的換到它的左邊，比它大的交換到它的右邊，它也在交換中不斷更改自己的位置，直到完全滿足這個(gè)要求為止。
• 快速排序的時(shí)間性能取決于快速遞歸的深度，快排的時(shí)間復(fù)雜度為O(nlogn)。
• 快速排序的空間復(fù)雜度主要是遞歸造成的棧空間的使用，平均情況下空間復(fù)雜度為O(nlogn)。
• 由于關(guān)鍵字的比較和交換是跳躍進(jìn)行的，因此，快排是一種不穩(wěn)定的排序算法

快速排序的優(yōu)化

1. 優(yōu)化選取樞軸
2. 在上面的代碼中，選取樞軸的方式為：
3. pivotkey = L->r[low]，即用序列的第一個(gè)元素作為樞軸，這是理想情況下 L->r[low]是中間數(shù)。
4. 但是對于其他情況，這種固定選取第一個(gè)關(guān)鍵子作為首個(gè)樞軸的方法就不是很合理。
5. 于是可以用下面的方法優(yōu)化：

• 三數(shù)取中(median-of-three)法：
• 取三個(gè)關(guān)鍵子進(jìn)行排序，將中間數(shù)作為樞軸，一般取左端、右端和中間三個(gè)數(shù)，也可以隨機(jī)選取。
• 九數(shù)取中(median-of-nine)法：
• 先從數(shù)組中分三次取樣，每次取三個(gè)數(shù)，三個(gè)樣品各取中數(shù)，然后從這三個(gè)數(shù)當(dāng)中再取出一個(gè)中數(shù)作為樞軸

三數(shù)取中(median-of-three)法代碼：

•  

 int pivotkey;
 
 int m = low + (high - low)/2;
 
 if (L->r[low] > L->r[high])
 swap(L, low, high);
 
 if (L->r[m] > L->r[high])
 swap(L, high, m);
 if (L->r[m] > L->r[low])
 swap(L, m, low);
 
 pivotkey = L->r[low];

1. 優(yōu)化不必要的交換
2. 優(yōu)化小數(shù)組時(shí)的排序方案
3. 優(yōu)化遞歸操作

快速排序優(yōu)化后的代碼

•  

int Partition1(SqList * L, int low, int high){
 
 int pivotkey;
 
 int m = low + (high - low)/2;
 
 if (L->r[low] > L->r[high])
 swap(L, low, high);
 
 if (L->r[m] > L->r[high])
 swap(L, high, m);
 if (L->r[m] > L->r[low])
 swap(L, m, low);
 
 pivotkey = L->r[low];
 L->r[0] = pivotkey;
 
 while (low < high) {
 while (low < high && L->r[high] >= pivotkey)
 high--;
 L->r[low] = L->r[high];
 
 while (low < high && L->r[low] <= pivotkey)
 low++;
 L->r[high] = L->r[low];
 }
 
 L->r[low] = L->r[0];
 
 return low;
}
void QSort1(SqList *L, int low, int high){
 
 int pivot;
 if ((high -low) > MAX_LINEGIH_INSERT_SORT) {
 while (low < high) {
 pivot = Partition1(L, low, high);
 QSort1(L, low, pivot-1);
 
 low = pivot+1;
 }
 }else
 InsertSort(L);
}
void QuickSort1(SqList *L){
 QSort1(L, 1, L->length);
}

• 希爾排序相當(dāng)于直接插入排序的升級，同屬于插入排序類
• 堆排序相當(dāng)于簡單選擇排序的升級，同屬于選擇排序類
• 快速排序相當(dāng)于冒泡排序的升級，同屬于交換排序類
•