> 作者簡(jiǎn)介：?舊言~，目前大一，現(xiàn)在學(xué)習(xí)Java，c，c++，Python等
> 座右銘：松樹千年終是朽，槿花一日自為榮。

> 目標(biāo)：掌握每種排序的方法，理解每種排序利弊和復(fù)雜度。

> 毒雞湯：船停在碼頭是最安全的，但那不是造船的目的；人呆在家里是最舒服的，但那不是人生的意義。最美好的生活方式，莫過于和一群志同道合的人奔跑在理想的路上！
> 望小伙伴們點(diǎn)贊👍收藏?加關(guān)注喲💕💕?

🌟前言?

? ? ? ? 談起排序這個(gè)事情，大家都是耳熟能詳?shù)氖铝?#xff0c;從我們認(rèn)識(shí)的斗地主，每一復(fù)牌都是按照從小到大的順序排序的，如圖：

? ? ? ?排序的目的是為了讓我們很好的管理，使無序的事情變成有序，當(dāng)然排序的方法有很多，如由大到小，由大到小.....。而面對(duì)大量數(shù)據(jù)就需要排序。在數(shù)據(jù)結(jié)構(gòu)中我們發(fā)明了多種排序，如我們最早認(rèn)識(shí)的冒泡排序，本篇博客讓大家對(duì)多種排序有一個(gè)很好的認(rèn)知，閑話少談。

?主體??

咱們就掌握八種就行啦

🌙冒泡排序

這里博主在C語言刷題訓(xùn)練專欄中講到過冒泡排序，咱們?cè)倩仡櫥仡?img referrerpolicy="no-referrer" alt="" height="28" src="https://img-blog.csdnimg.cn/37a1f48659d84b0197d13a1abcc579b9.png" width="28" />

這里我們以接口的形式寫代碼，那咱們上代碼咯

//冒泡排序測(cè)試
void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int exchange = 0;for (int j = 1; j < n - i; j++){if (a[i - 1] > a[i]){//這里是一個(gè)交換函數(shù)Swap(&a[i - 1], &a[i]);exchange = 1;}}//這里進(jìn)行一趟有序時(shí)，直接跳出循環(huán)if (exchange == 0){break;}}
}

注意事項(xiàng)：
💦1.我們知道當(dāng)給的數(shù)據(jù)有序時(shí)，就不再需要進(jìn)行循環(huán)了，直接跳出循環(huán)（exchange作用）。
💦2. 第二個(gè)循環(huán)中??j < n - i? 不能搞錯(cuò)。

時(shí)間復(fù)雜度：O(N2)

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

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

復(fù)雜性：簡(jiǎn)單

🌙直接插入排序

直接插入排序是一種簡(jiǎn)單的插入排序法，其基本思想是： 把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個(gè)新的有序序列 ，就好像我們斗地主拿牌插入相似。

//插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];//一個(gè)元素進(jìn)行插入while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];}else{break;}--end;}//最后把插入的元素賦值回去a[end + 1] = tmp;}
}

//希爾排序測(cè)試
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){//間隔gap的元素進(jìn)行排序gap = gap / 3 + 1;//本質(zhì)上是插入排序for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];//一個(gè)元素進(jìn)行插入while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end = end - gap;}else{break;}}//最后把插入的元素賦值回去a[end + gap] = tmp;}}
}

//選擇排序測(cè)試
void SelectSort(int* a, int n)
{//初始化第一個(gè)元素 和 最后一個(gè)元素int begin = 0;int end = n - 1;while (begin < end){//選出最大值和最小值int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}//最小值和最初的元素交換Swap(&a[begin], &a[mini]);//如果max被換走就需要重新賦值if (maxi == begin){maxi = mini;}//最大值和最末的元素交換Swap(&a[end], &a[maxi]);++begin;--end;}
}

//堆排序測(cè)試
//實(shí)現(xiàn)向下調(diào)整建大堆
void AdjustDown(int* a, int n, int parent)
{//孩子和父親的關(guān)系 int child = parent * 2 + 1;while (child < n){//找出小的那個(gè)孩子if (child + 1 < n && a[child + 1] < a[child]){++child;}//實(shí)現(xiàn)向下調(diào)整元素if (a[child] < a[parent]){//元素交換Swap(&a[child], &a[parent]);// 繼續(xù)往下調(diào)整parent = child;child = parent * 2 + 1;}else{break;}}
}//堆排序測(cè)試
void HeapSort(int* a, int n)
{//向下調(diào)整建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){//實(shí)現(xiàn)向下調(diào)整建大堆AdjustDown(a, n, i);}int end = n - 1;while (end > 0){//元素交換Swap(&a[0], &a[end]);//實(shí)現(xiàn)向下調(diào)整建大堆AdjustDown(a, end, 0);--end;}
}

//三數(shù)取中 （找出中間值）
int GetMidi(int* a, int left, int right)
{//中間值int mid = (left + right) / 2;//三個(gè)數(shù)比較找出中間值if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}// 右邊找小，左邊找大，交換，把左邊的值跟a[keyi]交換
int PartSort1(int* a, int left, int right)
{//找中間值（相對(duì)）int midi = GetMidi(a, left, right);//把最左邊（相對(duì)）跟中間值（相對(duì)）換Swap(&a[left], &a[midi]);//定位最左邊（相對(duì)）int keyi = left;while (left < right){//找小while (left < right && a[right] >= a[keyi]){--right;}//找大while (left < right && a[left] <= a[keyi]){++left;}//左右交換Swap(&a[left], &a[right]);}//此時(shí)左邊走到中間了，開始交換Swap(&a[keyi], &a[left]);//返回return left;
};

//三數(shù)取中 （找出中間值）
int GetMidi(int* a, int left, int right)
{//中間值int mid = (left + right) / 2;//三個(gè)數(shù)比較找出中間值if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}//挖坑法
int PartSort2(int* a, int left, int right)
{//找中間值（相對(duì)）int midi = GetMidi(a, left, right);//把最左邊（相對(duì)）跟中間值（相對(duì)）換Swap(&a[left], &a[midi]);//定位最左邊（相對(duì)）int key = a[left];//保存key值以后，左邊形成第一個(gè)坑int hole = left;while (left < right){//右邊先走，找小，填到左邊的坑，右邊形成新的坑位while (left < right && a[right] >= key){--right;}a[hole] = a[right];hole = right;//左邊再走，找大，填到右邊的坑，左邊形成新的坑位while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}

//三數(shù)取中 （找出中間值）
int GetMidi(int* a, int left, int right)
{//中間值int mid = (left + right) / 2;//三個(gè)數(shù)比較找出中間值if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}//前后指針
int PartSort3(int* a, int left, int right)
{//找中間值（相對(duì)）int midi = GetMidi(a, left, right);//把最左邊（相對(duì)）跟中間值（相對(duì)）換Swap(&a[left], &a[midi]);//定義指針開頭int prev = left;//定義指針開頭后一個(gè)int cur = prev + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}//交換Swap(&a[prev], &a[keyi]);return prev;
}

//快排非遞歸（采用棧的形式）（先進(jìn)后出）
void QuickSortNonR(int* a, int begin, int end)
{//定義ST st;//初始化STInit(&st);//添加元素STPush(&st, end);STPush(&st, begin);while (!STEmpty(&st)){//剝離元素  讓left取先入但是后出的元素（區(qū)間的左邊）int left = STTop(&st);STPop(&st);//讓right取棧頂元素（是我們后入的區(qū)間的右邊）int right = STTop(&st);STPop(&st);// 右邊找小，左邊找大，交換，把左邊的值跟a[keyi]交換int keyi = PartSort1(a, left, right);//分割成段 // [lefy,keyi-1] keyi [keyi+1, right]if (keyi + 1 < right){//添加元素STPush(&st, right);STPush(&st, keyi + 1);}if (left < keyi - 1){//添加元素STPush(&st, keyi - 1);STPush(&st, left);}}//銷毀STDestroy(&st);
}

void _MergeSort(int* a, int* tmp, int begin, int end)
{//尾小于頭時(shí)if (end <= begin)return;//開始分割int mid = (end + begin) / 2;// [begin, mid][mid+1, end]_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);//歸并到tmp數(shù)據(jù)組，再拷貝回去//a->[begin, mid][mid+1, end]->tmpint begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int index = begin;//開始拷貝while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}//當(dāng)?shù)谝欢卧貨]有完全拷貝完就把剩下的拷貝進(jìn)去while (begin1 <= end1){tmp[index++] = a[begin1++];}//當(dāng)?shù)诙卧貨]有完全拷貝完就把剩下的拷貝進(jìn)去while (begin2 <= end2){tmp[index++] = a[begin2++];}//拷貝回原數(shù)組memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}//歸并排序（分路并歸）
void MergeSort(int* a, int n)
{//開辟空間int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//調(diào)用_MergeSort(a, tmp, 0, n - 1);//釋放內(nèi)存free(tmp);
}

//歸并排序（非遞歸）
void MergeSortNonR(int* a, int n)
{//開辟空間int* tmp = (int*)malloc(sizeof(int) * n);//判斷if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;// [begin1,end1] [begin2,end2] 歸并// 如果第二組不存在，這一組不用歸并了if (begin2 >= n){break;}// 如果第二組的右邊界越界，修正一下if (end2 >= n){end2 = n - 1;}//printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);int index = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}// 拷貝回原數(shù)組memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}printf("\n");gap *= 2;}free(tmp);
}

//計(jì)數(shù)排序測(cè)試
void CountSort(int* a, int n)
{//找最大值和最小值int min = a[0], max = a[0];for (size_t i = 0; i < n; i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}//找出區(qū)間int range = max - min + 1;//開辟（區(qū)間）int* count = (int*)malloc(sizeof(int) * range);printf("range:%d\n", range);//判斷if (count == NULL){perror("malloc fail");return;}//計(jì)入數(shù)字的個(gè)數(shù)memset(count, 0, sizeof(int) * range);// 統(tǒng)計(jì)數(shù)據(jù)出現(xiàn)次數(shù)for (int i = 0; i < n; i++){count[a[i] - min]++;}//排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}
}

??總結(jié)

咱看看每種排序的復(fù)雜度和穩(wěn)定性。

?🌠Sort.h代碼

#include<stdio.h>//打印數(shù)據(jù)
void PrintArray(int* a, int n);//冒泡排序測(cè)試
void BubbleSort(int* a, int n);
//插入排序測(cè)試
void InsertSort(int* a, int n);
//希爾排序測(cè)試
void ShellSort(int* a, int n);
//選擇排序測(cè)試
void SelectSort(int* a, int n);
//堆排序測(cè)試
void HeapSort(int* a, int n);//快排測(cè)試
void QuickSort1(int* a, int begin, int end);
void QuickSort2(int* a, int begin, int end);
//快排非遞歸測(cè)試
void QuickSortNonR(int* a, int begin, int end);//歸并排序測(cè)試
void MergeSort(int* a, int n);
//歸并排序（非遞歸）測(cè)試
void MergeSortNonR(int* a, int n);
//計(jì)數(shù)排序測(cè)試
void CountSort(int* a, int n);

🌠Test.c代碼

#define _CRT_SECURE_NO_WARNINGS 1#include<time.h>
#include<stdlib.h>
#include"Sort.h"
#include"Stack.h"//希爾排序測(cè)試
void TestShellSort()
{int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };ShellSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}//冒泡排序測(cè)試
void TestBubbleSort()
{int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };BubbleSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}//堆排序測(cè)試
void TestHeapSort()
{int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };HeapSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}//選擇排序測(cè)試
void TestSelectSort()
{int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };SelectSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}//測(cè)試代碼
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);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = N - 1; i >= 0; --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];}int begin1 = clock();//插入排序InsertSort(a1, N);int end1 = clock();int begin2 = clock();//希爾排序測(cè)試ShellSort(a2, N);int end2 = clock();int begin7 = clock();//冒泡排序測(cè)試BubbleSort(a7, N);int end7 = clock();int begin3 = clock();//選擇排序測(cè)試SelectSort(a3, N);int end3 = clock();int begin4 = clock();//堆排序測(cè)試HeapSort(a4, N);int end4 = clock();int begin5 = clock();//快排測(cè)試//QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();//MergeSort(a6, N);//計(jì)數(shù)排序測(cè)試//CountSort(a6, N);int end6 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("BubbleSort:%d\n", end7 - begin7);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("CountSort:%d\n", end6 - begin6);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}int main()
{TestOP();//TestBubbleSort();//TestHeapSort();//TestSelectSort();//TestQuickSort();//TestMergeSort();//TestCountSort();//printf("%d\n", Func(100000));return 0;
}

?🌠Sort.c代碼

#define _CRT_SECURE_NO_WARNINGS 1#include"Sort.h"
#include"Stack.h"//交換函數(shù)
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//打印數(shù)據(jù)
void PrintArray(int* a, int n)
{//循環(huán)for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}//冒泡排序測(cè)試
void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int exchange = 0;for (int j = 1; j < n - i; j++){if (a[i - 1] > a[i]){//這里是一個(gè)交換函數(shù)Swap(&a[i - 1], &a[i]);exchange = 1;}}//這里進(jìn)行一趟有序時(shí)，直接跳出循環(huán)if (exchange == 0){break;}}
}//插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];//一個(gè)元素進(jìn)行插入while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];}else{break;}--end;}//最后把插入的元素賦值回去a[end + 1] = tmp;}
}//希爾排序測(cè)試
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){//間隔gap的元素進(jìn)行排序gap = gap / 3 + 1;//本質(zhì)上是插入排序for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];//一個(gè)元素進(jìn)行插入while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end = end - gap;}else{break;}}//最后把插入的元素賦值回去a[end + gap] = tmp;}}
}//void ShellSort(int* a, int n)
//{/*int gap = 3;for (int j = 0; j < gap; j++){for (int i = j; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}	*///選擇排序測(cè)試
void SelectSort(int* a, int n)
{//初始化第一個(gè)元素 和 最后一個(gè)元素int begin = 0;int end = n - 1;while (begin < end){//選出最大值和最小值int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}//最小值和最初的元素交換Swap(&a[begin], &a[mini]);//如果max被換走就需要重新賦值if (maxi == begin){maxi = mini;}//最大值和最末的元素交換Swap(&a[end], &a[maxi]);++begin;--end;}
}//堆排序測(cè)試
//實(shí)現(xiàn)向下調(diào)整建大堆
void AdjustDown(int* a, int n, int parent)
{//孩子和父親的關(guān)系 int child = parent * 2 + 1;while (child < n){//找出小的那個(gè)孩子if (child + 1 < n && a[child + 1] < a[child]){++child;}//實(shí)現(xiàn)向下調(diào)整元素if (a[child] < a[parent]){//元素交換Swap(&a[child], &a[parent]);// 繼續(xù)往下調(diào)整parent = child;child = parent * 2 + 1;}else{break;}}
}//堆排序測(cè)試
void HeapSort(int* a, int n)
{//向下調(diào)整建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){//實(shí)現(xiàn)向下調(diào)整建大堆AdjustDown(a, n, i);}int end = n - 1;while (end > 0){//元素交換Swap(&a[0], &a[end]);//實(shí)現(xiàn)向下調(diào)整建大堆AdjustDown(a, end, 0);--end;}
}//三數(shù)取中 （找出中間值）
int GetMidi(int* a, int left, int right)
{//中間值int mid = (left + right) / 2;//三個(gè)數(shù)比較找出中間值if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}// 右邊找小，左邊找大，交換，把左邊的值跟a[keyi]交換
int PartSort1(int* a, int left, int right)
{//找中間值（相對(duì)）int midi = GetMidi(a, left, right);//把最左邊（相對(duì)）跟中間值（相對(duì)）換Swap(&a[left], &a[midi]);//定位最左邊（相對(duì)）int keyi = left;while (left < right){//找小while (left < right && a[right] >= a[keyi]){--right;}//找大while (left < right && a[left] <= a[keyi]){++left;}//左右交換Swap(&a[left], &a[right]);}//此時(shí)左邊走到中間了，開始交換Swap(&a[keyi], &a[left]);//返回return left;
};//挖坑法
int PartSort2(int* a, int left, int right)
{//找中間值（相對(duì)）int midi = GetMidi(a, left, right);//把最左邊（相對(duì)）跟中間值（相對(duì)）換Swap(&a[left], &a[midi]);//定位最左邊（相對(duì)）int key = a[left];//保存key值以后，左邊形成第一個(gè)坑int hole = left;while (left < right){//右邊先走，找小，填到左邊的坑，右邊形成新的坑位while (left < right && a[right] >= key){--right;}a[hole] = a[right];hole = right;//左邊再走，找大，填到右邊的坑，左邊形成新的坑位while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}//前后指針
int PartSort3(int* a, int left, int right)
{//找中間值（相對(duì)）int midi = GetMidi(a, left, right);//把最左邊（相對(duì)）跟中間值（相對(duì)）換Swap(&a[left], &a[midi]);//定義指針開頭int prev = left;//定義指針開頭后一個(gè)int cur = prev + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}//交換Swap(&a[prev], &a[keyi]);return prev;
}//快排測(cè)試一
void QuickSort1(int* a, int begin, int end)
{if (begin >= end)return;//小區(qū)間優(yōu)化，小區(qū)間不再遞歸分割排序，降低遞歸次數(shù)//當(dāng)元素小于10時(shí)，采用插入排序if ((end - begin + 1) > 10){//找值int keyi = PartSort3(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi + 1, end);}else{//插入排序InsertSort(a + begin, end - begin + 1);}
}//快排測(cè)試二
void QuickSort2(int* a, int begin, int end)
{if (begin >= end)return;//調(diào)用int keyi = PartSort3(a, begin, end);//[begin, keyi-1] keyi [keyi+1, end]QuickSort2(a, begin, keyi - 1);QuickSort2(a, keyi + 1, end);
}//快排非遞歸（采用棧的形式）（先進(jìn)后出）
void QuickSortNonR(int* a, int begin, int end)
{//定義ST st;//初始化STInit(&st);//添加元素STPush(&st, end);STPush(&st, begin);while (!STEmpty(&st)){//剝離元素  讓left取先入但是后出的元素（區(qū)間的左邊）int left = STTop(&st);STPop(&st);//讓right取棧頂元素（是我們后入的區(qū)間的右邊）int right = STTop(&st);STPop(&st);// 右邊找小，左邊找大，交換，把左邊的值跟a[keyi]交換int keyi = PartSort1(a, left, right);//分割成段 // [lefy,keyi-1] keyi [keyi+1, right]if (keyi + 1 < right){//添加元素STPush(&st, right);STPush(&st, keyi + 1);}if (left < keyi - 1){//添加元素STPush(&st, keyi - 1);STPush(&st, left);}}//銷毀STDestroy(&st);
}void _MergeSort(int* a, int* tmp, int begin, int end)
{//尾小于頭時(shí)if (end <= begin)return;//開始分割int mid = (end + begin) / 2;// [begin, mid][mid+1, end]_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);//歸并到tmp數(shù)據(jù)組，再拷貝回去//a->[begin, mid][mid+1, end]->tmpint begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int index = begin;//開始拷貝while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}//當(dāng)?shù)谝欢卧貨]有完全拷貝完就把剩下的拷貝進(jìn)去while (begin1 <= end1){tmp[index++] = a[begin1++];}//當(dāng)?shù)诙卧貨]有完全拷貝完就把剩下的拷貝進(jìn)去while (begin2 <= end2){tmp[index++] = a[begin2++];}//拷貝回原數(shù)組memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}//歸并排序（分路并歸）
void MergeSort(int* a, int n)
{//開辟空間int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//調(diào)用_MergeSort(a, tmp, 0, n - 1);//釋放內(nèi)存free(tmp);
}//歸并排序（非遞歸）
void MergeSortNonR(int* a, int n)
{//開辟空間int* tmp = (int*)malloc(sizeof(int) * n);//判斷if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;// [begin1,end1] [begin2,end2] 歸并// 如果第二組不存在，這一組不用歸并了if (begin2 >= n){break;}// 如果第二組的右邊界越界，修正一下if (end2 >= n){end2 = n - 1;}//printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);int index = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}// 拷貝回原數(shù)組memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}printf("\n");gap *= 2;}free(tmp);
}//計(jì)數(shù)排序測(cè)試
void CountSort(int* a, int n)
{//找最大值和最小值int min = a[0], max = a[0];for (size_t i = 0; i < n; i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}//找出區(qū)間int range = max - min + 1;//開辟（區(qū)間）int* count = (int*)malloc(sizeof(int) * range);printf("range:%d\n", range);//判斷if (count == NULL){perror("malloc fail");return;}//計(jì)入數(shù)字的個(gè)數(shù)memset(count, 0, sizeof(int) * range);// 統(tǒng)計(jì)數(shù)據(jù)出現(xiàn)次數(shù)for (int i = 0; i < n; i++){count[a[i] - min]++;}//排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}
}

🌟結(jié)束語

? ? ? ?今天內(nèi)容就到這里啦，時(shí)間過得很快，大家沉下心來好好學(xué)習(xí)，會(huì)有一定的收獲的，大家多多堅(jiān)持，嘻嘻，成功路上注定孤獨(dú)，因?yàn)閳?jiān)持的人不多。那請(qǐng)大家舉起自己的小說手給博主一鍵三連，有你們的支持是我最大的動(dòng)力💞💞💞，回見。