朋友們、伙計們，我們又見面了，本期來給大家解讀一下有關(guān)排序算法的相關(guān)知識點，如果看完之后對你有一定的啟發(fā)，那么請留下你的三連，祝大家心想事成！
C 語 言 專 欄：C語言：從入門到精通
數(shù)據(jù)結(jié)構(gòu)專欄：數(shù)據(jù)結(jié)構(gòu)
個? 人? 主? 頁?：stackY、
目錄
?
前言：
1.排序的概念及其運用
1.1排序的概念
1.2排序的應(yīng)用
1.3常見的排序算法
2.排序算法的實現(xiàn)
2.1插入排序
2.1.1基本思想
2.1.2直接插入排序
#直接插入排序完整代碼：
2.1.3希爾排序?
#預(yù)排序
#直接插入排序
#希爾排序完整代碼：
3.算法的效率比較
前言：
排序無處不在，在生活中我們無時無刻都在間接或者直接的使用排序這個方法，很多復(fù)雜的事情在經(jīng)過排序之后都會變得簡單許多。那么，在現(xiàn)階段我們學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)一這塊排序又該怎么實現(xiàn)呢？
1.排序的概念及其運用
1.1排序的概念
排序：所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，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ù)的排序。
1.2排序的應(yīng)用
比如我們電腦桌面上的應(yīng)用的排序方式：
比如我們網(wǎng)購的時候也可以對商品進行排序：
比如2023中國高校排行榜：
?等等都是通過排序來展示出來的，所以可見排序無論是在哪個領(lǐng)域都應(yīng)用廣泛。
1.3常見的排序算法
如果大家想要測試自己的排序算法正確與否可以在這個OJ鏈接來進行測試：https://leetcode.cn/problems/sort-an-array/
2.排序算法的實現(xiàn)
2.1插入排序
2.1.1基本思想
直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為 止，得到一個新的有序序列 。這其實就跟我們玩撲克牌一樣，摸牌、插入：
2.1.2直接插入排序
當(dāng)插入第 i(i>=1) 個元素時，前面的 array[0],array[1],…,array[i-1] 已經(jīng)排好序，此時用 array[i] 的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將 array[i] 插入，原來位置上的元素順序后移。排升序：簡單的總結(jié)就是在[0, end]這個區(qū)間中插入tmp，從end的位置開始比較，如果tmp小于end這個位置的元素，那么就將end往后面挪，然后與end-1這個元素再作比較（前提是：[0, end] 這個區(qū)間的元素有序）。
我們先來寫出一趟插入排序的基本邏輯：
排升序：在[0,end]區(qū)間插入tmp，先比較tmp與end的大小關(guān)系，如果比end小，那么將end往后面挪一個，在用tmp和end-1比較，如果比end-1小，再將end-1往后挪，直到tmp比[0,end]區(qū)間中那個元素大，那么就停止，如果tmp比這個區(qū)間的所有數(shù)都要小，那么直接將tmp放在第一個位置即可。
代碼演示：?
//直接插入排序 //在[0,end]插入tmp //升序 void InsertSort(int* a, int n) { //一趟插入排序 int end; int tmp; while (end >= 0) { if (a[end] > tmp) { //挪數(shù)據(jù) a[end + 1] = a[end]; end--; } else { break; } } //放數(shù)據(jù) //走到這里有兩種情況： //1.tmp比a[end]大 //2.tmp比a中的任何數(shù)都小 a[end + 1] = tmp; }
完成了一趟的插入排序，那么怎么樣實現(xiàn)在數(shù)組中排序呢？
第一次取數(shù)組的第一個元素直接放進去即可，第二次就需要和第一次放進去的元素進行比較，然后排成有序，也就是說我們可以將第一個元素看成有序，然后把后面的依次插入，所以呢，我們可以將已插入的數(shù)據(jù)看作是手里的手牌，未插入的數(shù)據(jù)看作牌堆的牌，我們每一次摸一張插入一張，這樣子就實現(xiàn)了使用插入排序排序數(shù)組
#直接插入排序完整代碼：
//直接插入排序 //在[0,end]插入tmp //升序 void InsertSort(int* a, int n) { for (int i = 1; i < n; i++) { //一趟插入排序 int end = i - 1; int tmp = a[i]; while (end >= 0) { if (a[end] > tmp) { //挪數(shù)據(jù) a[end + 1] = a[end]; end--; } else { break; } } //放數(shù)據(jù) //走到這里有兩種情況： //1.tmp比a[end]大 //2.tmp比a中的任何數(shù)都小 a[end + 1] = tmp; } }
直接插入排序的特性總結(jié)：1. 元素集合越接近有序，直接插入排序算法的時間效率越高2. 時間復(fù)雜度：O(N^2)（最好的情況可以做到O(N)）3. 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法4. 穩(wěn)定性：穩(wěn)定
直接插入排序和冒泡排序比較：
通過上面的實現(xiàn)過程還看不出來插入排序的速度，我們可以和之前學(xué)過的??冒泡排序作一比較
冒泡排序的時間復(fù)雜度也為O(N^2)，那么使用它們兩個算法分別來排升序一個原本就是升序的數(shù)組，那么即便數(shù)據(jù)一次都不需要挪動，冒泡排序還需要O(N^2)，但是直接插入排序只需要O(N)。所以直接插入排序在某種特殊情況下還是蠻快的。
2.1.3希爾排序?
希爾排序也被稱為縮小增量排序
希爾排序法的基本思想是：1.預(yù)排序：接近有序2.插入排序
整體步驟就是確定一個整數(shù)值gap，然后間隔為gap，將所有數(shù)據(jù)分為gap組，對著gap組數(shù)據(jù)分別進行插入排序，最后再整體來一次插入排序，這個預(yù)排序的目的就是為了讓數(shù)據(jù)接近有序，以便減少最后一次插入排序的時間。例如要將：9 8 7 6 5 4 3 2 1 0 排成升序
#預(yù)排序
接下來我們就用代碼來演示：
我們先不管gap怎么設(shè)置，在這里我們就先將gap設(shè)置為3
還是使用上面的例子：9 8 7 6 5 4 3 2 1 0 排成升序
1.先將這組數(shù)據(jù)分為gap組，然后分別對這gap組數(shù)據(jù)進行插入排序。
①我們先來進行一次排序，這次類比之前的直接插入排序不一樣的是：先得保存下一個數(shù)據(jù)，因為往后面挪動數(shù)據(jù)會進行覆蓋，然后每一次比較的是間隔為gap的數(shù)據(jù)：
代碼演示：
//希爾排序 void ShellSort(int* a, int n) { int gap = 3; //一次插入排序 int end; //保存下一個位置的數(shù)據(jù) int tmp = a[end + gap]; //比較、挪動 while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; }②接著我們?nèi)绾螌⑦@gap組中的其中一組進行排序呢？
這里要注意一個問題，對其中一組數(shù)據(jù)進行插入排序時每一次跳過的不是1，而是gap，并且end在往后面走的過程中不能大于n - gap，如果大于n - gap，那么tmp就會造成越界訪問。
代碼演示：
//希爾排序 void ShellSort(int* a, int n) { int gap = 3; // 控制條件得注意、 步長要注意 for (int i = 0; i < n - gap; i += gap) { //一次插入排序 int end = i; //保存下一個位置的數(shù)據(jù) int tmp = a[end + gap]; //比較、挪動 while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } }③進行完其中一組的排序，接下來就要進行g(shù)ap組分別排序，如果我們仔細觀察不難發(fā)現(xiàn)，當(dāng)end為0的時候排序的是第一組，當(dāng)end為1的時候排序的是第二組，那么我們可以再設(shè)置一個循環(huán)，以gap為控制循環(huán)條件：
代碼演示：
//希爾排序 void ShellSort(int* a, int n) { int gap = 3; //循環(huán)gap組，對gap組的數(shù)據(jù)分別進行插入排序 for (int j = 0; j < gap; j++) { // 控制條件得注意、 步長要注意 for (int i = j; i < n - gap; i += gap) { //一次插入排序 int end = i; //保存下一個位置的數(shù)據(jù) int tmp = a[end + gap]; //比較、挪動 while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } }上面的代碼用了三層循環(huán)，看起來是比較復(fù)雜的，但是我們可以進行改版一下，大家注意看代碼的變化：
//希爾排序 void ShellSort(int* a, int n) { int gap = 3; //對gap組數(shù)據(jù)分別進行插入排序 for (int i = 0; i < n - gap; i++) { //一次插入排序 int end = i; //保存下一個位置的數(shù)據(jù) int tmp = a[end + gap]; //比較、挪動 while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } }很多老鐵在這里看不懂改版之后代碼，小編在這里帶大家解釋一下：首先上面的這兩種代碼的所需要的時間是完全沒有區(qū)別的，如果使用三層循環(huán)，比較容易理解，改版之后的代碼比較難理解，三層循環(huán)采用的是分組排序，兩層循環(huán)采用的是多組并排（當(dāng)i == 0時排序的是第一組第一個元素，當(dāng)i == 1時排序的是第二組的第一個元素......以此類推就將這全部的數(shù)據(jù)排完了），這樣解釋應(yīng)該就不難理解。
?這里采取自愿，兩種方法的效率都是一樣，沒有區(qū)別，按照個人喜歡來自取。
#直接插入排序
當(dāng)把gap組數(shù)據(jù)分別插入排序之后，還需要進行最后一次插入排序，那么最直接的方法就是直接在上面的代碼的最后面再調(diào)用一次普通的插入排序即可，但是這未免有點太麻煩了，所以我們需要從gap下手，我們可以先來比較一下插入排序和希爾排序：
gap在這里決定了每一次的步長，所以：
gap越大，大的數(shù)可以更快的到后面，小的數(shù)可以更快的到前面，但是數(shù)據(jù)越不接近有序。
gap越小，大的數(shù)和小的數(shù)移動的比較緩慢，但是數(shù)據(jù)在移動完之后越接近有序。
gap == 1時，就是直接插入排序。
在上面排序10個數(shù)據(jù)的時候gap為3是比較合適的，但是如果要排序10000個數(shù)據(jù)，gap還是為3的話就有點挫了，所以gap的設(shè)定要根據(jù)元素個數(shù)來進行確定，然后在排序到最后一次時gap得是1，為了完成最后一次的直接插入排序。
#希爾排序完整代碼：
//希爾排序 void ShellSort(int* a, int n) { //1. gap > 1：預(yù)排序 //2. gap == 1 ：直接插入排序 int gap = n; while (gap > 1) { gap = gap / 3 + 1; //對gap組數(shù)據(jù)分別進行插入排序 for (int i = 0; i < n - gap; i++) { //一次插入排序 int end = i; //保存下一個位置的數(shù)據(jù) int tmp = a[end + gap]; //比較、挪動 while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } }
希爾排序的特性總結(jié)：1. 希爾排序是對直接插入排序的優(yōu)化。2. 當(dāng)gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。我們后面可以進行性能測試的對比。3. 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算，因此在好些樹中給出的希爾排序的時間復(fù)雜度都不固定，在某些大佬的書籍中就提到過：《數(shù)據(jù)結(jié)構(gòu) (C 語言版 ) 》 --- 嚴(yán)蔚敏
《數(shù)據(jù)結(jié)構(gòu) - 用面相對象方法與 C++ 描述》 --- 殷人昆
?所以呢，希爾排序的時間復(fù)雜度是
4. 穩(wěn)定性：不穩(wěn)定
3.算法的效率比較
?在這里我們來比較我們已學(xué)過的冒泡排序、堆排序、直接插入排序和希爾排序的效率，再比較之前我們再來回顧一下冒泡排序和堆排序：
//冒泡排序 void BubbleSort(int* a, int n) { //設(shè)置冒泡排序的趟數(shù) for (int i = 0; i < n - 1; i++) { //一趟冒泡排序的次數(shù) bool exchange = false; for (int j = 1; j < n - j; j++) { if (a[j] > a[j + 1]) //如果前面的一個數(shù)字大于后面的數(shù)字就交換 { int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp; exchange = true; } } if (exchange == false) { break; } } }
//堆排序 //交換函數(shù) void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } //向下調(diào)整 void AdjustDown(int* a, int n, int parent) { //假設(shè)左孩子為左右孩子中最小的節(jié)點 int child = parent * 2 + 1; while (child < n) //當(dāng)交換到最后一個孩子節(jié)點就停止 { if (child + 1 < n //判斷是否存在右孩子 && a[child + 1] < a[child]) //判斷假設(shè)的左孩子是否為最小的孩子 { child++; //若不符合就轉(zhuǎn)化為右孩子 } //判斷孩子和父親的大小關(guān)系 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); //更新父親和孩子節(jié)點 parent = child; child = parent * 2 + 1; } else { break; } } } //O(N * logN) void HeapSort(int* a, int n) { //建堆--向下調(diào)整算法建堆 //時間復(fù)雜度為O(N) for (int i = ((n - 1) - 1) / 2; i >= 0; --i) {// 這里的n-1表示最后一個葉子節(jié)點 // 最后一個葉子節(jié)點的父親就是： // （n-1）-1/2； AdjustDown(a, n, i); } //O(N * logN) int end = n - 1; while (end > 0) { //交換堆頂和最后一個數(shù)據(jù)的位置 Swap(&a[0], &a[end]); //向下調(diào)整，找次小的 AdjustDown(a, end, 0); end--; } }
接下來我們可以使用一段代碼來測試一下上面的這四種算法的效率區(qū)別。
采用的思路就是隨機生成1w個數(shù)據(jù)，然后使用這些算法進行排序：
代碼演示：
// 測試排序的性能對比 void TestOP() { srand(time(0)); const int N = 100000; 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); for (int i = 0; i < N; ++i) { a1[i] = rand(); a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; } int begin1 = clock(); InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); BubbleSort(a3, N); int end3 = clock(); int begin4 = clock(); HeapSort(a4, N); int end4 = clock(); int begin5 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("BubbleSort:%d\n", end3 - begin3); printf("HeapSort:%d\n", end4 - begin4); free(a1); free(a2); free(a3); free(a4); }在這里測試的時候建議大家使用Release版本，測試效果會更好（這里測試的單位都是毫秒）：
文章來源：http://www.zghlxwxcb.cn/news/detail-489724.html
朋友們、伙計們，美好的時光總是短暫的，我們本期的的分享就到此結(jié)束，最后看完別忘了留下你們彌足珍貴的三連喔，感謝大家的支持！文章來源地址http://www.zghlxwxcb.cn/news/detail-489724.html
到了這里，關(guān)于排序算法：插入排序（直接插入排序、希爾排序）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
