🔥個人主頁：@草莓熊Lotso

🎬作者簡介：C++研發方向學習者

📖個人專欄：?《C語言》?《數據結構與算法》《C語言刷題集》《Leetcode刷題指南》

??人生格言：生活是默默的堅持，毅力是永久的享受。

前言：在前面的學習中，我們實現了順序表和鏈表，棧和隊列以及二叉樹。通過這些知識的學習和實現我們的代碼能力也有了一定的提升。那么我們從這篇博客開始就進入到了初階數據結構最后一個板塊，排序的學習。我們會學習多種排序，其實每種排序單獨拿出來都不會很難。但是如果讓我們自己去實現的話就不是那么容易的了。還是和之前一樣，我們先分部分來講解。

---

目錄

一.排序的概念及應用?

?常見的排序算法：

二.直接插入排序

代碼實現：?

時間復雜度：?

三.希爾排序

代碼實現：

時間復雜度：

四.直接插入排序和希爾排序的性能對比

代碼演示：

---

一.排序的概念及應用?

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

--我們在日常生活中經常可以見到排序的使用，比如購物平臺的篩選排序，還有各種各樣的排行榜

?常見的排序算法：

--如圖所示

---

二.直接插入排序

基本思想：直接插入排序是一種簡單的插入排序法，其基本思想是把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的序列中，直到所有的記錄插入完為止，最后得到一個新的有序序列。

--我們在實際生活中玩撲克牌時，就用了插入排序的思想

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

代碼實現：?

void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){//升序:>   降序:<if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else {break;}}arr[end + 1] = tmp;}
}

圖示如下：?

test.c：?

#include"Sort.h"void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}void test1()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int size = sizeof(a) / sizeof(a[0]);printf("排序前:");PrintArr(a, size);//直接插入排序InsertSort(a, size);printf("排序后:");PrintArr(a, size);
}int main()
{test1();return 0;
}

--測試完成，打印沒有問題，排成了升序，退出碼為0

時間復雜度：?

• O(n^2)

---

三.希爾排序

基本思想：希爾排序（Shell Sort）是一種改進的插入排序算法，其核心思想是通過將數組分割成若干個“子序列”逐步縮小排序范圍，最終實現整體有序。

--先選定?個整數（通常是gap = n/3+1），把待排序文件所有記錄分成各組，所有的距離相等的記錄分在同一組內，并對每?組內的記錄進行排序，然后gap=gap/3+1得到下?個整數，再將數組分成各組，進行插入排序，當gap=1時，就相當于直接插入排序。

希爾排序的特性：

• 希爾排序是對直接插入排序的優化。
• 當 gap > 1 時都是預排序，目的是讓數組更接近于有序。當 gap == 1 時，數組已經接近有序的了，這樣就會很快。這樣整體而言，可以達到優化的效果。

代碼實現：

void ShellSort(int* arr, int n)
{int gap = n;while(gap>1){ gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++)//用i++比用i+=gap省了一個循環{int end = i;int tmp = arr[end + gap];while (end >= 0){//升序:>   降序:<if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else {break;}}arr[end + gap] = tmp;}}
}

圖示如下：?

為啥要用gap=gap/3-1：

test.c：?

#include"Sort.h"void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}void test1()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int size = sizeof(a) / sizeof(a[0]);printf("排序前:");PrintArr(a, size);//希爾排序ShellSort(a, size);printf("排序后:");PrintArr(a, size);
}int main()
{test1();return 0;
}

--測試完成，打印沒有問題，升序排列正確，退出碼為0

時間復雜度：

• O(n^1.3)

---

四.直接插入排序和希爾排序的性能對比

--除了通過時間復雜度以外，我們也可以通過下面這串代碼來實現兩種排序的性能對比

代碼演示：

#include"Sort.h"void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}void test1()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int size = sizeof(a) / sizeof(a[0]);printf("排序前:");PrintArr(a, size);//直接插入排序//InsertSort(a, size);//希爾排序ShellSort(a, size);printf("排序后:");PrintArr(a, size);
}// 測試排序的性能對比
void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);free(a1);free(a2);
}int main()
{TestOP();//test1();return 0;
}

--測試完成，可以看出10w個數據排序，希爾排序的用時比直接插入排序少很多(單位：ms)

---

往期回顧：

【數據結構初階】--二叉樹(四)

【數據結構初階】--二叉樹(五)

【數據結構初階】--二叉樹(六)

結語：本篇博客就到此結束了，主要實現了一下兩種插入排序，一個直接插入排序，一個希爾排序。我們通過對比可知希爾排序大部分情況下都是優于直接插入排序的。這里聲明一下，博主這里展示的都是Sort.c文件和test.c文件，其中.h文件由于比較簡單這里就不展示了，大家可以直接看圖片。如果文章對你有幫助的話，歡迎評論，點贊，收藏加關注，感謝大家的支持。