數(shù)據(jù)結(jié)構(gòu)-八大排序

@TOC

一、前言

本章主要講解：

八大排序的基本知識及其實現(xiàn)

注：這里的八大排序指直接插入，希爾，選擇，堆排，冒泡，快排，歸并，計數(shù)

八大排序匯總圖：

二、排序概念及應(yīng)用

1、概念

排序：

所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作

穩(wěn)定性：

假設(shè)在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的(記錄的相對次序保持不變)；否則稱為不穩(wěn)定的

內(nèi)部排序：

數(shù)據(jù)元素全部放在內(nèi)存中的排序

外部排序：

數(shù)據(jù)元素太多不能同時放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序

2、排序應(yīng)用

示例：搜索電影時

三、排序算法接口展示

// 排序?qū)崿F(xiàn)的接口 // 插入排序 void InsertSort(int* a, int n); // 希爾排序 void ShellSort(int* a, int n); // 選擇排序 void SelectSort(int* a, int n); // 堆排序 void AdjustDwon(int* a, int n, int root); void HeapSort(int* a, int n); // 冒泡排序 void BubbleSort(int* a, int n) // 快速排序遞歸實現(xiàn) // 快速排序hoare版本 int PartSort1(int* a, int left, int right); // 快速排序挖坑法 int PartSort2(int* a, int left, int right); // 快速排序前后指針法 int PartSort3(int* a, int left, int right); void QuickSort(int* a, int left, int right); // 快速排序 非遞歸實現(xiàn) void QuickSortNonR(int* a, int left, int right) // 歸并排序遞歸實現(xiàn) void MergeSort(int* a, int n) // 歸并排序非遞歸實現(xiàn) void MergeSortNonR(int* a, int n) // 計數(shù)排序 void CountSort(int* a, int n)

四、插入排序

1、直接插入排序

直接插入排序是一種簡單的插入排序法

基本思想：

把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列

動圖展示：

實現(xiàn)代碼：

//直接插入排序 void InsertSort(int* a, int n) { assert(a);//傳入數(shù)組不為空指針 int i; for (i = 0; i < n - 1; i++) //注意：最后一個要插入數(shù)據(jù)的下標(biāo)為n-1，此次插入有序數(shù)列的end下標(biāo)為n-2 { int end = i;//標(biāo)記當(dāng)前有序數(shù)列的最后一個位置下標(biāo) int x = a[end + 1];//要插入的數(shù)據(jù)為有序數(shù)列的后一個位置 while (end >= 0)//進行當(dāng)前趟次的插入排列 { //升序 if (a[end] >x)//有序數(shù)列的數(shù)據(jù)比插入數(shù)據(jù)大，則往后挪動 { a[end + 1] = a[end]; end--;//向前找，進行排列數(shù)據(jù) } else//遇到不大于要插入數(shù)據(jù)，則不再往前找 { break; } } a[end + 1] = x;//將要插入數(shù)據(jù)插入到不大于該數(shù)據(jù)的后一個位置 } }

直接插入排序的特性總結(jié)：

元素集合越接近有序，直接插入排序算法的時間效率越高

時間復(fù)雜度：O(N^2)

空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法

穩(wěn)定性：穩(wěn)定

2、希爾排序

基本思想：

對于直接插入排序在面對一些特殊情況時，效率非常低（例如：將降序排成升序），而對于已經(jīng)接近排好的序列，效率非常高

希爾排序在直接排序之前，進行預(yù)排列，將某些極端數(shù)據(jù)更快的排列到數(shù)列前面，構(gòu)成一個接近排列好的序列，最后再進行一次直接插入排序

預(yù)排列的原理也是插入排列，只不過這里的將數(shù)組分成了gap組，分別對每一個小組進行插入排序

如下動圖：對于升序，當(dāng)gap從5 – 2 – 1的過程中，排在后面的數(shù)值小的數(shù)能更快排到前面，當(dāng)gap為1的時候?qū)嶋H上就是進行了一次插入排序

動圖展示：

// 希爾排序 void ShellSort(int* a, int n) { //多組預(yù)排（一鍋燉）+插排 int gap = n; while (gap > 1) { gap /= 2;//保證最后一次分組gap==1,即最后一次為直接插入排序 //gap = gap / 3 + 1;//也可以寫成這樣，除3預(yù)排的效率相比于除2的好點 for (int i = 0; i < n - gap; i++) { int end = i; int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end-=gap; } else break; } a[end + gap] = x; } } }

希爾排序的特性總結(jié)：

希爾排序是對直接插入排序的優(yōu)化

當(dāng)gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比

希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，一般來說為O(n^1.3)

穩(wěn)定性：不穩(wěn)定

五、選擇排序

1、直接選擇排序

基本思想：

每一次遍歷待排序的數(shù)據(jù)元素從中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始（或者末尾）位置，直到全部待排序的數(shù)據(jù)元素排完

動圖展示：

實現(xiàn)代碼：

// 選擇排序 void SelectSort(int* a, int n) { int begin = 0, end = n - 1;//記錄下標(biāo) while (begin < end) { int mini = begin; for (int i = begin; i <= end; i++) { //遍歷找到最小數(shù)據(jù)并記錄下標(biāo) if (a[i] < a[mini]) mini = i; } Swap(&a[begin], &a[mini]);//交換 begin++;//縮小范圍 } }

這里我們還可以對直接選擇排序做一個優(yōu)化：每次遍歷待排序數(shù)據(jù)找出最大和最小的數(shù)據(jù)，分別排列到序列起始和末尾

優(yōu)化代碼：

// 選擇排序（優(yōu)化版） void SelectSort(int* a, int n) { int begin = 0, end = n - 1; while (begin < end) { int maxi = begin, mini = begin; for (int i = begin; i <= end; i++)//遍歷找到最大最小的下標(biāo) { if (a[i] > a[maxi]) maxi = i; if (a[i] < a[mini]) mini = i; } Swap(&a[begin], &a[mini]);//交換 //當(dāng)最初始位置begin與對大數(shù)據(jù)下標(biāo)重合的情況 if (begin == maxi)//修正下標(biāo)位置 maxi = mini; Swap(&a[end], &a[maxi]); begin++;//縮小范圍 end--; } }

直接選擇排序的特性總結(jié)：

直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用

時間復(fù)雜度：O(N^2)

空間復(fù)雜度：O(1)

穩(wěn)定性：不穩(wěn)定

2、堆排序

堆排序是指利用堆（數(shù)據(jù)結(jié)構(gòu)）進行選擇數(shù)據(jù)的一種排序算法

基本思想:

原則：

先將原數(shù)組建成堆，需要注意的是排升序要建大堆，排降序建小堆

注：以大堆為例

建堆：

一個根節(jié)點與子節(jié)點數(shù)據(jù)如果不符合大堆結(jié)構(gòu)，那么則對根節(jié)點數(shù)據(jù)進行向下調(diào)整，而向下調(diào)整的前提是左右子樹也符合大堆結(jié)構(gòu),所以從堆尾數(shù)據(jù)的根節(jié)點位置開始向下調(diào)整建大堆

排序：

大堆堆頂數(shù)據(jù)一定是待排數(shù)據(jù)中最大的，將堆頂數(shù)據(jù)與堆尾數(shù)據(jù)交換,交換后將除堆尾數(shù)據(jù)看成新堆，對現(xiàn)堆頂數(shù)據(jù)進行向下調(diào)整成大堆,以此循環(huán)直至排列完畢

向下調(diào)整：

找到子節(jié)點中的較大數(shù)據(jù)節(jié)點比較，如果父節(jié)點數(shù)據(jù)比大子節(jié)點小則交換，直到不符合則停止向下交換，此時再次構(gòu)成了一個大堆結(jié)構(gòu)

具體堆排序詳解：堆排序超詳解

動圖展示：大堆排序

實現(xiàn)代碼：

void Adjustdown(int* a, int n,int parent) { int child = parent * 2 + 1; while (child < n) { //找到數(shù)據(jù)大的子結(jié)點 if (child + 1 < n && a[child + 1] > a[child]) { child++; } //父節(jié)點數(shù)據(jù)小于子節(jié)點就交換 if (a[parent] < a[child]) { Swap(&a[parent], &a[child]); //更新下標(biāo) parent = child; child = parent * 2 + 1; } else//否則向下調(diào)整完畢 break; } } // 堆排序(升序)建大堆 void HeapSort(int* a, int n) { int i; //建大堆 for (i = (n - 1 - 1) / 2; i >= 0; i--) { Adjustdown(a, n, i); } //交換調(diào)整 for (i = n - 1; i >= 0; i--) { Swap(&a[0], &a[i]);//與當(dāng)前堆尾數(shù)據(jù)交換 Adjustdown(a, i, 0);//對交換后堆頂數(shù)據(jù)進行向下調(diào)整 } }

直接選擇排序的特性總結(jié)：

堆排序使用堆來選數(shù)，效率就高了很多。

時間復(fù)雜度：O(N*logN)

空間復(fù)雜度：O(1)

穩(wěn)定性：不穩(wěn)定

六、交換排序

1、冒泡排序

基本思想：

每次遍歷待排序數(shù)組，對相鄰數(shù)據(jù)進行比較，不符合排序要求則交換

動圖展示：

實現(xiàn)代碼：

// 冒泡排序 void BubbleSort(int* a, int n) { int i, j; for (i = 0; i < n - 1; i++)//遍歷趟數(shù) { for (j = 0; j < n - 1 - i; j++)//比較次數(shù) { if (a[j] > a[j + 1])//升序 Swap(&a[j], &a[j + 1]);//交換 } } }

冒泡排序的特性總結(jié)：

冒泡排序是一種非常容易理解的排序

時間復(fù)雜度：O(N^2)

空間復(fù)雜度：O(1)

穩(wěn)定性：穩(wěn)定

2、快速排序

基本思想為：

任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列

左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值 然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止

按基準(zhǔn)值劃分左右的方式有：

1）hoare

注：基本操作過程如圖示

實現(xiàn)代碼：

// 按基準(zhǔn)劃分hoare版本 int PartSort1(int* a, int left, int right) { int mid = GetMidIndex(a, left, right);//三數(shù)取中（優(yōu)化取基準(zhǔn)值，后面會解釋） Swap(&a[mid], &a[left]);//使得中間值永遠在最左，便于決定誰先走 int key = left; while (left < right) { //Key設(shè)在左邊，先從右邊尋找小于a[key]的 while (left < right && a[right] >= a[key]) { right--; } //再從左邊尋找大于a[key]的 while (left < right && a[left] <= a[key]) { left++; } //找到后交換 Swap(&a[left], &a[right]); } //最后相遇時將key與相遇點交換 Swap(&a[key], &a[left]); return left;//返回相遇點下標(biāo) }

key的位置與左右下標(biāo)誰先走的關(guān)系：

注：對于排升序來說

一般來說在三數(shù)取中后得到中等值key，我們讓該值與待排序數(shù)組的最左邊起始位置交換，使得key永遠在最左邊，并且之后會讓右下標(biāo)先走找小于key的值，找到后再讓左下標(biāo)走找大于key的值，都找到則交換，相遇后再將key與相遇位置的值交換

右下標(biāo)先走的話，對于兩下標(biāo)相遇的的情況只有兩種：

右下標(biāo)走著走著遇到左下標(biāo)，此時左下標(biāo)的值一定是小于key的值（交換后左下標(biāo)是原來右下標(biāo)的小于key的值）

左下標(biāo)走著走著遇到右下標(biāo)，此時右下標(biāo)的值一定是小于key的是（右下標(biāo)找小于key的值）

所以這樣保證了最后下標(biāo)相遇與key交換后，key左邊區(qū)間一定小于key，右邊區(qū)間一定大于key

2）挖坑法

注：基本操作過程如圖示

實現(xiàn)代碼：

// 快速排序挖坑法 int PartSort2(int* a, int left, int right) { int mid = GetMidIndex(a, left, right); Swap(&a[mid], &a[left]);//使得中間值永遠在最左，便于決定誰先走 int key = a[left];//保存key值（基準(zhǔn)值） int pivot = left;//保存坑下標(biāo) while (left < right) { //右邊先找 while (left=key) { right--; } //填坑 a[pivot] = a[right]; pivot = right; //再從左邊找 while (left < right && a[left] <= key) { left++; } //填坑 a[pivot] = a[left]; pivot = left; } //相遇 a[pivot] = key; return pivot; }

3）前后指針法

注：基本操作過程如圖示

實現(xiàn)代碼：

// 快速排序前后指針法（推薦） int PartSort3(int* a, int left, int right) { int mid = GetMidIndex(a, left, right); Swap(&a[mid], &a[left]); //初始化前后指針 int cur = left, prev = left-1; while (cur < right) { if(a[cur]

注：推薦掌握，簡單易于操控

4）優(yōu)化

三數(shù)取中：

如果基準(zhǔn)值取到的是待排序列中的中位數(shù)，對于快排來說效率是最優(yōu)的

如果基準(zhǔn)值取到的是待排序列中的最大或最小，對于快排來說效率是最差的

為了優(yōu)化這種特殊情況，我們在取基準(zhǔn)值時會采取三數(shù)取中，即堆待排序序列的開始處，末尾處和中間處位置的數(shù)據(jù)進行比較，得到排中的數(shù)據(jù)，盡量使得快速排序的效率達到理想狀態(tài)O(N*logN)

實現(xiàn)代碼：

int GetMidIndex(int* a, int left, int right)//優(yōu)化快排(避免特殊情況造成效率降低) { int mid = right + (left - right) >> 1;//獲取中間下標(biāo)（注意避免和溢出） if (a[mid]>a[left])//返回中等數(shù)據(jù)的下標(biāo) { return a[mid] < a[right] ? mid : right; } else//a[mid]<=a[left] { return a[left] < a[right] ? left : right; } }

整體實現(xiàn)代碼：

//快排 void QuickSort(int* a, int left, int right) { //當(dāng)區(qū)間只有一個元素或沒有元素時不需要排序了 if (left >= right) return; //遍歷一趟進行交換排序 int mid=PartSort3(a, left, right); //遞歸排序左右區(qū)間 QuickSort(a, left, mid - 1); QuickSort(a, mid+1, right); }

小區(qū)間優(yōu)化：

當(dāng)待排序數(shù)組的區(qū)間很小時，遞歸開辟的函數(shù)棧幀數(shù)量時很大的，很多時甚至可能造成棧溢出

為了解決這一問題，當(dāng)區(qū)間小到一定程度時，我們選擇使用希爾排序，小到一定程度時待排序數(shù)列已經(jīng)快接近有序，而希爾排序?qū)τ诮咏行驍?shù)列的排序時非常高效的

實現(xiàn)代碼：

//快排+局部優(yōu)化 void QuickSort1(int* a, int left, int right) { if (left >= right)//當(dāng)區(qū)間只有一個元素或沒有元素時遞歸結(jié)束 return; if (right - left + 1 <= 10) { InsertSort(a + left, right - left + 1); } else { int mid = PartSort3(a, left, right);//進行一趟交換排序 QuickSort1(a, left, mid - 1);//遞歸交換排序 QuickSort1(a, mid + 1, right); } }

快速排序的特性總結(jié)：

快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序

時間復(fù)雜度：O(N*logN)

空間復(fù)雜度：O(logN)

穩(wěn)定性：不穩(wěn)定

3、快排非遞歸

基本思想;

對于遞歸函數(shù)在內(nèi)存實際上是在棧中進行開辟函數(shù)棧幀，這里我們使用數(shù)據(jù)結(jié)構(gòu)中的棧來模擬內(nèi)存中的棧，從而實現(xiàn)快排的非遞歸

實現(xiàn)代碼：

// 快速排序 非遞歸實現(xiàn) void QuickSortNonR(int* a, int left, int right) { //首先構(gòu)建一個棧（C語言來說需要自己實現(xiàn)） ST st; StackInit(&st); StackPush(&st, left);//將左右區(qū)間入棧 StackPush(&st, right); while (!StackEmpty(&st)) { int end = StackTop(&st);//讀取區(qū)間數(shù)據(jù) StackPop(&st); int begin = StackTop(&st); StackPop(&st); int mid = PartSort3(a, begin, end);//排序（排好基準(zhǔn)值） //劃分基準(zhǔn)值的左右區(qū)間 int begin1 = mid + 1, end1 = end; //先入右邊區(qū)域（棧的特點是先入后出） if (end1 - begin1 + 1 > 1) { StackPush(&st, begin1); StackPush(&st, end1); } //再將左邊區(qū)域入棧 int begin2 = begin, end2 = mid-1; if (end2 - begin2 + 1 > 1) { StackPush(&st, begin2); StackPush(&st, end2); } } //到空棧則排序結(jié)束 StackDestroy(&st);//棧銷毀 }

七、歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法，采用分治法

1、歸并排序

1）遞歸歸并

基本思想：

將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序

核心步驟：

動圖展示：

實現(xiàn)代碼：

//歸并排序 void _MergeSort(int* a, int left, int right, int* tmp) { if (left >= right)//只有一個元素或沒有元素為有序，則返回 return; int mid = (right + left) / 2; _MergeSort(a, left, mid, tmp); _MergeSort(a, mid+1, right, tmp); //左區(qū)間和右區(qū)間有序后開始?xì)w并 int begin1 = left, end1 = mid; int begin2 = mid+1, end2 = right; int p = left;//記錄下標(biāo) while (begin1<=end1&&begin2<=end2)//歸并排序 { if (a[begin1] < a[begin2])//升序 { tmp[p++] = a[begin1++]; } else { tmp[p++] = a[begin2++]; } } while (begin1 <= end1)//剩下部分 { tmp[p++] = a[begin1++]; } while (begin2 <= end2) { tmp[p++] = a[begin2++]; } //拷貝回數(shù)組a for (int i = left; i <= right; i++) { a[i] = tmp[i]; } void MergeSort(int* a, int n) { //創(chuàng)建暫存數(shù)據(jù)數(shù)組（保存歸并好的數(shù)據(jù)） int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("nalloc fail\n"); exit(-1); } //歸并排序 _MergeSort(a, 0, n - 1, tmp); //釋放 free(tmp); tmp = NULL; }

歸并排序的特性總結(jié)：

歸并的缺點在于需要O(N)的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題

時間復(fù)雜度：O(N*logN)

空間復(fù)雜度：O(N)

穩(wěn)定性：穩(wěn)定

2）非遞歸歸并

基本思路：

對于歸并的非遞歸來說可以用棧也可以用循環(huán)，這里主要講解循環(huán)（比較簡單，直接從合并步驟開始）

實現(xiàn)代碼：

void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int)*n); if (tmp == NULL) { perror("malloc fail"); exit(-1); } int gap = 1;//數(shù)組歸并距離 //（初始gap為1即每個數(shù)組只有一個元素，此時每個數(shù)組都為有序數(shù)組） while (gap < n)//歸并趟次 { for (int i = 0; i < n; i += gap * 2)//分組歸并 { //劃分區(qū)間 int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; //判斷越界的情況 //這種情況不用考慮歸并（已經(jīng)有序） if (end1 >= n|| begin2 >= n) { break; } //這種情況需要歸并 if (end2 >= n) { end2 = n - 1; } //歸并 int p = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[p++] = a[begin1++]; } else { tmp[p++] = a[begin2++]; } } while (begin1 <= end1) { tmp[p++] = a[begin1++]; } while (begin2 <= end2) { tmp[p++] = a[begin2++]; } //拷貝排序后數(shù)據(jù)到原數(shù)組 for (int j = i; j <= end2; j++) { a[j] = tmp[j]; } } gap *= 2; } free(tmp);//釋放 tmp = NULL; }

八、計數(shù)排序

計數(shù)排序是一種非比較排序，又稱為鴿巢原理，是對哈希直接定址法的變形應(yīng)用

1、計數(shù)排序

基本思想：

在排序數(shù)組中找到最大最小的數(shù)據(jù)，算出對應(yīng)范圍并創(chuàng)建對應(yīng)長度個數(shù)組用來計數(shù)，遍歷排序數(shù)組，根據(jù)每個出現(xiàn)的數(shù)據(jù)值與計數(shù)數(shù)組下標(biāo)構(gòu)建的相對映射關(guān)系進行統(tǒng)計數(shù)據(jù)出現(xiàn)次數(shù)，最后將統(tǒng)計的出的數(shù)據(jù)按次序賦值給原數(shù)組

動圖展示：

實現(xiàn)代碼：

void CountSort(int* a, int n) { //遍歷找出數(shù)組最大最小值（算出范圍） int max = a[0], min = a[0]; for (int i = 1; i < n; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } int range = max - min + 1; //開辟對應(yīng)長度個計數(shù)數(shù)組 int* count = (int*)malloc(sizeof(int) * range); if (count == NULL) { perror("malloc fail"); exit(-1); } //初始化數(shù)組計數(shù)為0 memset(count, 0, sizeof(int)*range); //遍歷計數(shù)據(jù)出現(xiàn)次數(shù) for (int i = 0; i < n; i++) { count[a[i] - min]++; //a[i] - min：數(shù)據(jù)與下標(biāo)構(gòu)成的相對映射關(guān)系 } //排入原數(shù)組 int p = 0; for (int i = 0; i < range; i++) { while (count[i]--) { a[p++] = i + min; } } free(count);//釋放 count = NULL; }

計數(shù)排序的特性總結(jié)：

計數(shù)排序在數(shù)據(jù)范圍集中時，效率很高，但是適用范圍及場景有限（只能對整數(shù)排序）

時間復(fù)雜度：O(MAX(N,range))

空間復(fù)雜度：O(range)

穩(wěn)定性：穩(wěn)定

九、性能分析

排序算法復(fù)雜度及穩(wěn)定性總結(jié)：

性能測試代碼：

void TestOP() { srand(time(0)); const int N = 100000;//測試數(shù)據(jù)個數(shù) int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); int* a3 = (int*)malloc(sizeof(int) * N); int* a4 = (int*)malloc(sizeof(int) * N); int* a5 = (int*)malloc(sizeof(int) * N); int* a6 = (int*)malloc(sizeof(int) * N); int* a7 = (int*)malloc(sizeof(int) * N); int* a8 = (int*)malloc(sizeof(int) * N); //給開辟數(shù)組賦值 for (int i = 0; i < N; ++i) { a1[i] = rand(); a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i]; a7[i] = a1[i]; a8[i] = a1[i]; } //數(shù)組排序并計算時間花費 int begin1 = clock(); InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); SelectSort(a3, N); int end3 = clock(); int begin4 = clock(); HeapSort(a4, N); int end4 = clock(); int begin5 = clock(); QuickSort(a5, 0, N - 1); int end5 = clock(); int begin6 = clock(); MergeSort(a6, N); int end6 = clock(); int begin7 = clock(); BubbleSort(a7, N); int end7 = clock(); int begin8 = clock(); CountSort(a8, N); int end8 = clock(); //展示數(shù)據(jù) printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("SelectSort:%d\n", end3 - begin3); printf("HeapSort:%d\n", end4 - begin4); printf("QuickSort:%d\n", end5 - begin5); printf("MergeSort:%d\n", end6 - begin6); printf("BubbleSort:%d\n", end7 - begin7); printf("CountSort:%d\n", end8 - begin8); //釋放數(shù)組 free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); free(a8); } int main() { TestOP(); return 0; }

注：在Release版本下測試比Debug好一點，Release會對測試具有優(yōu)化，更好的體現(xiàn)排序算法性能

測試結(jié)果：

總結(jié)：

總體來說插入排序，選擇排序，冒泡排序是低一級水平的排序算法，希爾排序，堆排序，歸并排序和快速排序是高一級別的排序，而計數(shù)排序效率非常高，但有一定局限

數(shù)據(jù)結(jié)構(gòu)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。