? ?
??博客昵稱：博客小夢
??最喜歡的座右銘：全神貫注的上吧?。?！
??作者簡介：一名熱愛C/C++，算法等技術(shù)、喜愛運(yùn)動、熱愛K歌、敢于追夢的小博主！
??博主小留言：哈嘍！??各位CSDN的uu們，我是你的博客好友小夢，希望我的文章可以給您帶來一定的幫助，話不多說，文章推上！歡迎大家在評論區(qū)嘮嗑指正，覺得好的話別忘了一鍵三連哦！??
前言??
? ? 哈嘍各位友友們??，我今天又學(xué)到了很多有趣的知識，現(xiàn)在迫不及待的想和大家分享一下！??我僅已此文，手把手帶領(lǐng)大家使用C語言手撕八大經(jīng)典排序~ 都是精華內(nèi)容，可不要錯過喲?。?！??????
排序的認(rèn)識
? 排序分為內(nèi)排序和外排序，這是根據(jù)數(shù)據(jù)在什么位置上進(jìn)行排序而決定的。在內(nèi)存中，對數(shù)據(jù)進(jìn)行排序稱為內(nèi)排序；在外存中，對數(shù)據(jù)進(jìn)行排序稱為外排序。
經(jīng)典的排序有以下幾種：
- 直接插入排序（InsertSort)
- 希爾排序（ShellSort)
- 冒泡排序（BubbleSort）
- 堆排序（HeapSort）
- 選擇排序（SelectSort）
- 快速排序（QuickSort）
- 歸并排序（MergeSort）
- 計數(shù)排序（CountSort）
排序的穩(wěn)定性：
其中，歸并排序的身份比較特殊，它既可以做內(nèi)排序，也可以做外排序。其余排序都是屬于內(nèi)排序的。
- 穩(wěn)定的排序：直接插入排序，冒泡排序，堆排序，選擇排序，快速排序，
- 不穩(wěn)定的排序：希爾排序，歸并排序，計數(shù)排序
排序的時間復(fù)雜度和空間復(fù)雜度以及如何選擇適合的排序：
- 直接插入排序（InsertSort)：時間復(fù)雜度：**O(n2),**空間復(fù)雜度：O(1)。但是，是n2 級別排序中可以說最好的排序。特別是當(dāng)數(shù)據(jù)比較有序或者有序時，最好選擇插入排序。但是如果數(shù)據(jù)一開始是逆序的，那就是最壞的情況。
- 希爾排序（ShellSort)：這個排序的時間復(fù)雜度比較難計算，大約為O(N^1.3)。 時間復(fù)雜度O(1) 。其是在直接排序上的一個改良版解決了數(shù)據(jù)比較隨機(jī)時，插入排序比較慢的缺點(diǎn)。
- 冒泡排序（BubbleSort）：時間復(fù)雜度：O(N^2)，空間復(fù)雜度：O(1) 。是比較經(jīng)典的算法，適合小白入門學(xué)習(xí)的第一種算法。本篇文章對此進(jìn)行一個優(yōu)化，當(dāng)數(shù)據(jù)本身就是有序的情況下，可將時間復(fù)雜度優(yōu)化為O(n)。
- 堆排序（HeapSort）: 時間復(fù)雜度：O(N*logn)，空間復(fù)雜度：O(1) 。適合大數(shù)據(jù)量的排序，一般可以用來解決TopK的問題。
- 選擇排序（SelectSort）：時間復(fù)雜度：O(N^2)，空間復(fù)雜度：O(1) 。是比較差的排序，比冒泡還差。這里是對選擇排序進(jìn)行了優(yōu)化，一般情況下，整體測試性能變得和冒泡差不多了，甚至好一點(diǎn)。
- 快速排序（QuickSort）：時間復(fù)雜度：O(N*logn)，空間復(fù)雜度：O(logn) 。幾乎什么情況都是可以使用快速排序。但是還是有一些特殊情況不適合。例如，最左邊的值為最或者最大值，導(dǎo)致一開始選定的keyi為最值。從而惡化為O(n^2)的時間復(fù)雜度，也會有溢出的風(fēng)險。還有就是全為相同數(shù)據(jù)的情況或者其他一些專門針對快排設(shè)計的數(shù)據(jù)，都會導(dǎo)致快排變“慢排”。這里進(jìn)行了**三數(shù)取中，小區(qū)間優(yōu)化，三路規(guī)劃，隨機(jī)數(shù)mid ，**解決了目前針對快排的絕大多數(shù)問題。
- 歸并排序（MergeSort）：時間復(fù)雜度：O(N*logn)，空間復(fù)雜度：O(n) 。它是完全的二分分割思維，從理論上來，比快排還要快一點(diǎn)。但是由于需要拷貝，拷貝也會消耗性能的，因此其和快排差不多。歸并排序還可以應(yīng)用于外存上的排序場景，這是相對其他排序的一個優(yōu)勢。
- 計數(shù)排序（CountSort）：時間復(fù)雜度：O(N），空間復(fù)雜度：O(max - min + 1 ) 。其性能的好壞取決這一組數(shù)據(jù)中大小的范圍max - min 。在對一組大小比較集中的數(shù)據(jù)進(jìn)行排序時，計數(shù)排序是一個非常好的選擇。
實(shí)現(xiàn)兩個數(shù)交換的代碼
void Swap(int* p1, int* p2)
{
int tem = *p1;
*p1 = *p2;
*p2 = tem;
}
實(shí)現(xiàn)
優(yōu)化版選擇排序
傳統(tǒng)的選擇排序時，一次選定最小的值放到最左邊，以此類推。這里優(yōu)化的思路是：一次選定最小值和最大值，分別放到最左邊和最右邊。
//選擇排序
void SelectSort(int* a, int n)
{
int left = 0;
int right = n - 1;
while (left < right)
{
int maxi = left;
int mini = left;
//找出最大和最小的兩個數(shù)的位置
for (int i = left; i <= right; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[mini], &a[left]);
if (maxi == left)
{
maxi = mini;
}
Swap(&a[maxi], &a[right]);
left++;
right--;
}
}
冒泡排序
普通版冒泡排序
// 普通版冒泡排序
void BubbleSort(int* a, int len)
{
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len - i - 1; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
}
}
}
}
升級版冒泡排序
? 這里是對冒泡排序最好的情況下進(jìn)行一個優(yōu)化，當(dāng)遍歷一遍數(shù)組發(fā)現(xiàn)是有序的，則直接跳出循環(huán)不在交換數(shù)據(jù)。這樣可以將冒泡最好的情況下，優(yōu)化為O(n)。
// 升級版冒泡排序
void BubbleSort(int* a, int len)
{
for (int i = 0; i < len; i++)
{
int flag = 1;
for (int j = 0; j < len - i - 1; j++)
{
if (a[j] > a[j + 1])
{
flag = 0;
Swap(&a[j], &a[j + 1]);
}
}
if (flag == 0)
break;
}
}
直接插入排序
? 直接插入排序的實(shí)現(xiàn)思路可以簡單的理解為我們打撲克牌時，進(jìn)行將牌從小到大排序的情況。每次取一個數(shù)，和前面的數(shù)比較，并將該數(shù)插入到合適的位置。這樣可以保證，每一次取一個數(shù)據(jù)時，前面的數(shù)都是有效的。
//直接插入排序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tem = a[end + 1];
while (end >= 0)
{
if (tem < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tem;
}
}
希爾排序
希爾排序主要是基于插入排序的思想，不同點(diǎn)是希爾排序其利用分組的思想。先進(jìn)行預(yù)排序，將數(shù)據(jù)變得比較有序，再進(jìn)行插入排序的方式。
//希爾排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tem = a[end + gap];
while (end >= 0)
{
if (tem < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tem;
}
}
}
堆排序
堆排序是一個比較抽象的排序。邏輯上我們控制的是一個完全二叉樹，物理上我們控制的是一個數(shù)組。這里采用向下調(diào)整算法。
運(yùn)用的知識點(diǎn)和技巧：
- 排升序——建大堆
- 排降序——建小堆
- 左孩子 ：child = parent * 2 + 1
- 右孩子：child = parent * 2 + 2。
- parent = (child - 1) / 2
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
//選出最大的孩子
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
{
child++;
}
//最大的孩子和父親比
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
//堆排序
void HeapSort(int* a, int n)
{
//建堆--升序建大堆
//向下調(diào)整建堆 --時間復(fù)雜度：O(n)
for (int i = (n - 2) / 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--;
}
}
快速排序
快速排序遞歸版（進(jìn)行過三數(shù)取中優(yōu)化+小區(qū)間優(yōu)化）
三數(shù)取中，解決的是取得keyi是最值的問題。小區(qū)間優(yōu)化，是為了減少遞歸調(diào)用次數(shù)。
快速排序遞歸版1——hoare
注意點(diǎn)：
- 左邊選keyi，右邊先走；右邊選keyi，左邊先走
- 右邊選比 a[keyi]小的值，左邊先比 a[keyi] 大的值
- 注意特殊情況對邊界的處理。
// 快速排序hoare版本
int GetMidnum(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
{
return mid;
}
else if(a[left] > a[right])
{
return right;
}
else
{
return left;
}
}
//a[left] <= a[mid]
else
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
}
int PartSort1(int* a, int left, int right)
{
int keyi = left;
int mid = GetMidnum(a, left, right);
Swap(&a[mid], &a[keyi]);
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
keyi = left;
return keyi;
}
快速排序遞歸版2——挖坑法
這個和hoare版本差不多，只是在理解的思維上有所不同。挖坑法的思路是比較好理解的。不同區(qū)哪個先走的問題。
// 快速排序挖坑法
int GetMidnum(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
{
return mid;
}
else if(a[left] > a[right])
{
return right;
}
else
{
return left;
}
}
//a[left] <= a[mid]
else
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
}
int PartSort2(int* a, int left, int right)
{
int mid = GetMidnum(a, left, right);
Swap(&a[mid], &a[left]);
int key = a[left];
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[left] = key;
return left;
}
快速排序遞歸版3——前后指針法
這個版本是我比較推薦的快速排序的實(shí)現(xiàn)方法。主要是因?yàn)槠渚帉懘a的坑相對于上面兩種比較少。而且整體代碼比較簡短。
// 快速排序前后指針法
int GetMidnum(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
{
return mid;
}
else if(a[left] > a[right])
{
return right;
}
else
{
return left;
}
}
//a[left] <= a[mid]
else
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
}
int PartSort3(int* a, int left, int right)
{
int keyi = left;
int prev = left;
int cur = prev + 1;
int mid = GetMidnum(a, left, right);
Swap(&a[mid], &a[left]);
while (cur <= right)
{
if (a[cur] < a[keyi] && prev++ != cur)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
return prev;
}
上述三個版本，在性能上沒有什么差別，只是在思維的理解上，挖坑法比較好理解。而前后指針法比較好寫代碼。
快速排序非遞歸1
快速排序的非遞歸實(shí)現(xiàn)，需要利用數(shù)據(jù)結(jié)構(gòu)棧。解決的是，遞歸版本下，棧溢出的情況。
// 快速排序 非遞歸實(shí)現(xiàn)
void QuickSortNonR(int* a, int left, int right)
{
ST st;
STInit(&st);
if (left < right)
{
STPush(&st, right);
STPush(&st, left);
}
while (!STEmpty(&st))
{
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
int keyi = PartSort3(a, begin, end);
//[begin,keyi - 1] keyi [ keyi + 1, end]
if (keyi + 1 < end)
{
STPush(&st, end);
STPush(&st, keyi + 1);
}
if (begin < keyi - 1)
{
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
STDestroy(&st);
}
快速排序非遞歸2
棧實(shí)現(xiàn)的頭文件.h
#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);
棧實(shí)現(xiàn)的功能文件.c
#include "Stack.h"
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
//pst->top = -1; // top 指向棧頂數(shù)據(jù)
pst->top = 0; // top 指向棧頂數(shù)據(jù)的下一個位置
pst->capacity = 0;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
void STPush(ST* pst, STDataType x)
{
if (pst->top == pst->capacity)
{
int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capacity = newCapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
void STPop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}
STDataType STTop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->a[pst->top - 1];
}
bool STEmpty(ST* pst)
{
assert(pst);
/*if (pst->top == 0)
{
return true;
}
else
{
return false;
}*/
return pst->top == 0;
}
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
歸并排序
歸并排序遞歸版
歸并排序遞歸版1（進(jìn)行過小區(qū)間優(yōu)化）
歸并排序是一個使用二分來劃分區(qū)間，然后進(jìn)行歸并的排序。主要還是要注意區(qū)間的劃分。
void _MergeSort(int* a, int begin, int end, int* tem)
{
// 遞歸結(jié)束的條件
if (begin == end)
return;
//小區(qū)間優(yōu)化
if ((begin - end) < 10)
{
InsertSort(a, begin - end + 1);
}
int mid = (begin + end) / 2;
//[left , mid] [ mid + 1, right]
_MergeSort(a, begin, mid, tem);
_MergeSort(a, mid + 1, end, tem);
//歸并數(shù)據(jù)
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tem[i++] = a[begin1++];
}
else
{
tem[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tem[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tem[i++] = a[begin2++];
}
memmove(a + begin, tem + begin, sizeof(int) * (end2 - begin + 1));
}
//歸并排序 -- 遞歸版
void MergeSort(int* a, int n)
{
int* tem = (int*)malloc(sizeof(int) * n);
_MergeSort(a, 0, n - 1,tem);
free(tem);
}
歸并排序非遞歸版
歸并排序非遞歸版1（部分歸并思路實(shí)現(xiàn)）
非遞歸版本的歸并排序，最主要的是要處理好區(qū)間邊界的問題和修正，防止越界。以及拷貝數(shù)據(jù)時，區(qū)間的邊界把控問題。
//歸并排序 -- 非遞歸版1
void MergeSortNonR(int* a, int n)
{
int* tem = (int*)malloc(sizeof(int) * n);
int begin = 0;
int end = n - 1;
int gap = 1;
while (gap < n)
{
int j = 0;
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;
//printf("修正前：[ %d , %d ] [ %d , %d ]\n",begin1,end1,begin2,end2);
if (end1 >= n || begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
//printf("修正后：[ %d , %d ] [ %d , %d ]\n", begin1, end1, begin2, end2);
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tem[j++] = a[begin1++];
}
else
{
tem[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tem[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tem[j++] = a[begin2++];
}
memmove(a + i, tem + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
}
歸并排序非遞歸版2（整體歸并思路實(shí)現(xiàn)）
//歸并排序 -- 非遞歸版2
void MergeSortNonR2(int* a, int n)
{
int* tem = (int*)malloc(sizeof(int) * n);
int begin = 0;
int end = n - 1;
int gap = 1;
while (gap < n)
{
int j = 0;
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;
//printf("修正前：[ %d , %d ] [ %d , %d ]\n",begin1,end1,begin2,end2);
if (end1 >= n)
{
end1 = n - 1;
begin2 = n;
end2 = n - 1;
}
else if(begin2 >= n)
{
begin2 = n;
end2 = n - 1;
}
else if(end2 >= n)
{
end2 = n - 1;
}
//printf("修正后：[ %d , %d ] [ %d , %d ]\n", begin1, end1, begin2, end2);
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tem[j++] = a[begin1++];
}
else
{
tem[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tem[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tem[j++] = a[begin2++];
}
}
memmove(a, tem, sizeof(int) * n);
gap *= 2;
}
}
? ?對于上述的排序，我都進(jìn)行了一個驗(yàn)證，結(jié)果都是正確的。
文章來源：http://www.zghlxwxcb.cn/news/detail-582780.html
總結(jié)撒花
? ?本篇文章旨在分享的是C語言手撕八大經(jīng)典排序。希望大家通過閱讀此文有所收獲！
? ???如果我寫的有什么不好之處，請在文章下方給出你寶貴的意見??。如果覺得我寫的好的話請點(diǎn)個贊贊和關(guān)注哦~??????文章來源地址http://www.zghlxwxcb.cn/news/detail-582780.html
到了這里，關(guān)于追夢之旅【數(shù)據(jù)結(jié)構(gòu)篇】——C語言手撕八大經(jīng)典排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[C語言實(shí)現(xiàn)]數(shù)據(jù)結(jié)構(gòu)——手撕順序棧之我出生就會寫一個棧](https://imgs.yssmx.com/Uploads/2024/02/479835-1.png)
