前言：生活中我們總是會碰到各種各樣的排序，今天我們就對部分常用的排序進行總結和學習，今天的內容還是相對比較簡單的一部分，各位一起加油哦！

💖 博主CSDN主頁:衛(wèi)衛(wèi)衛(wèi)的個人主頁 💞
👉 專欄分類:數(shù)據(jù)結構 👈
💯代碼倉庫:衛(wèi)衛(wèi)周大胖的學習日記💫
💪關注博主和博主一起學習!一起努力！

---

插入排序

插入排序：我們可以通俗的理解成將一個數(shù)記錄下來按其數(shù)值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。(由于動圖畫的實在太過于繁瑣博主就畫了一半，請見諒)

代碼思路：由此圖我們可以知道，我們用一個tmp記錄后面一個元素，如果后面的比前面的小，就讓前面的元素逐一和他比較并往后走，如果碰到比他小的就停下來插入到此位置。（不理解的話可以理解成我們平常玩的斗地主的牌，拿一張牌插到應該有的位置）。

---

代碼實現(xiàn)：

void InsertSort(int* a, int n)//插入排序
{for (int i = 0; i < n - 1; i++)//升序{int end = i;int tmp = a[end + 1];//保存后一個while (end >= 0){if (tmp < a[end])//前一個大于后一個,讓大的全部往后走{a[end + 1] = a[end];end--;}else{break;	}}a[end + 1] = tmp;//在把小的放在此時的位置}
}

測試函數(shù):

void Test_InsertSort()
{int a[] = { 1,2,30,0,99,1,7,8,2,11,0,3,13 };InsertSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
}

排序結果:

---

希爾排序

希爾排序:我們可以通俗的把待排的序列看成若干個子序列，然后對其分別進行直接插入排序，最后在對全部進行一次排序即可。(如下圖所示)

---

我們可以理解成gap>1是預排序，目的是讓它接近有序
gap == 1是直接插入排序，目的是讓它有序。但是記住最后一定要讓gap最后一次排序為1。
代碼思路:我們可以把每次排序寫成一次插入排序，然后最后一讓其間距不斷的變化直到最后一次全部排序完成。
代碼實現(xiàn):

void ShellSort(int* a, int n)//希爾排序 
{int gap = n;while (gap){gap = gap / 2 ;for (int i = 0; i < n - gap; i++)//升序{int end = i;int tmp = a[end + gap];//保存后一個while (end >= 0){if (tmp < a[end])//前一個大于后一個,讓大的全部往后走{a[end + gap] = a[end];end = end -gap;}else{break;}}a[end + gap] = tmp;//在把小的放在此時的位置}}
}

---

函數(shù)測試

void Test_ShellSort()
{int a[] = { 1,2,30,0,99,1,7,8,2,11,0,3,13 };ShellSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
}

運行結果:

---

冒泡排序

冒泡排序：也是我們所碰到的最簡單的一種排序，這種排序的思想是十分簡單的，我們可以理解成每一趟找到序列中最大的一個或最小的元素，排序到序列的最左邊(右邊)，然后排序序列的有效次數(shù)趟即可排序完成(如下圖)。

代碼實現(xiàn):

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void BubbleSort(int* a, int n)//冒泡排序
{int i = 0;for (int j = 0; j < n - 1; j++){for (i = 0; i < n - j -1; i++)//每一趟找到一個最大的{if (a[i] < a[i + 1]){Swap(&a[i], &a[i + 1]);}}}
}

---

函數(shù)測試:

void Test_BubbleSort()
{int a[] = { 1,2,30,0,99,1,7,8,2,11,0,3,13 };BubbleSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
}

運行結果

---

選擇排序

選擇排序：我們現(xiàn)在一組有序序列中找到最大(最小)和第一個位置交換，然后再找次大的和第二個交換以此類推，最后我們即可得到一個有序序列。（如下圖所示）

---

代碼實現(xiàn)：

void SelectSort(int*a ,int n)//選擇排序
{//現(xiàn)在數(shù)組中找到最小的，然后和第一個位置交換//再找到次小的，和第二個位置交換int min = 0;for (int i = 0; i < n - 1 ; i++){min = i;//最小的數(shù)的下標for (int j = i; j < n; j++){if (a[min] > a[j])//找到最小位置的下標{min = j;}}if(min != i)Swap(&a[i], &a[min]);}
}

---

測試函數(shù)

void Test_SelectSort()
{//int a[] = { 1,2,30,0,99,1,7,8,2,11,0,3,13 };int a[] = { 1,0,0,0,99,1,7,8,2,9,0,3,0 };SelectSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));}

運行結果:

---

但是上面這種方法我們一共要找n-1次，我們思考一下每一次查找的過程中，如果我們每次一起查找最大的和最小的，那我們不就提高了一倍的效率。所以我們只需要再引入一個max變量來幫助我們再記錄一下這個值即可。
代碼實現(xiàn)：

void SelectSort_best(int* a, int n)//選擇排序
{int begin = 0;int end = n - 1;while (begin < end){int max = begin;int min = begin;int i = 0;for (i = begin + 1; i <= end; i++)//找最小的和最大的{if (a[i] < a[min]){min = i;}if (a[i] > a[max]){max = i;}}Swap(&a[begin], &a[min]);if (begin == max)//防止最大的和最小的是相同的{max = min;}Swap(&a[end], &a[max]);begin++;end--;}
}

運行結果依然和前面的相同，這里就不做更多的闡述了。

---

堆排序

堆排序：前面我們講了堆的模擬實現(xiàn)，我們知道堆的父親結點一定比它的孩子結點大(小)，因此我們可以充分的利用這一點來進行排序。

1. 首先我們們將數(shù)組中的元素，想象成一個堆，將其中的父親結點全部向下調整。（如下圖）
2. 根據(jù)我們模擬建立的大堆或者小堆，將其堆頂元素和堆尾進行交換，因此我們可以得到一個最大(最小的元素)再堆底，然后再通過一個end記錄尾部，交換一次減減一次，以此循環(huán)到end為0的時候即堆中所有元素也排序完成。(如下圖所示)
   

---

代碼實現(xiàn):

void AdjustDown(int* a, int size, int parent)//向下調整
{assert(a);int child = parent * 2 + 1;//找到第一個孩子while (child < size){//看倆個孩子誰更小，交小的那個與父親去比較if (a[child] < a[child + 1] && (child + 1) < size){child += 1;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;//讓父親和兒子往下走child = child * 2 + 1;}else{break;}}
}void HeapSort(int* a, int n)//堆排序
{int i = 0;for (i = (n - 1 - 1) / 2; i >= 0; i--)//建堆,只有父親結點需要調整{AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

---

函數(shù)測試:

void Test_HeapSort()
{int a[] = { 20,10,8,2,1,2,7 };HeapSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
}

運行結果:

---

好啦，今天的內容就到這里啦，下期內容預告【快速排序的模擬實現(xiàn)】-- 四種方式

---

結語：今天的內容就到這里吧，謝謝各位的觀看，如果有講的不好的地方也請各位多多指出，作者每一條評論都會讀的，謝謝各位。

---

🫵🫵🫵 祝各位接下來好運連連 💞