C語言中的八大排序算法詳解
更新時間：2023年07月29日 10:35:18 作者：杯淺
這篇文章主要介紹了C語言中的八大排序算法詳解,所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作,需要的朋友可以參考下
前言
所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。
排序算法在很多領(lǐng)域得到相當?shù)刂匾?，尤其是在大量?shù)據(jù)的處理方面，一個優(yōu)秀的算法可以節(jié)省大量的資源。
一、八大排序算法：
1.直接插入排序：
直接插入排序就是把待排序的元素逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。
實際中我們玩撲克牌時，就用了插入排序的思想
動圖演示：
那比如給我們一段序列，代碼如何實現(xiàn)呢？ 我們可以把第一個元素看成有序序列（一個元素序列必然有序）進行多次單趟插排
void InsertSort(int* arr, int size)//直接插入排序
{
for (int i = 0; i < size - 1; i++)
{
//單趟插入排序
//基本思想：[0,end]區(qū)間值為有序
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;//在這里break出去再去賦值tmp是為了防止最后一次end = -1進不來賦值
}
}
arr[end + 1] = tmp;
}
}2.希爾排序：
希爾排序是對直接插入排序的優(yōu)化，它對序列先進行多次預(yù)排序使之接近有序，因為最后接近有序使用直接插入排序非?？?。
如圖所示：
- 當gap越大，預(yù)排序越快，但是越不接近有序
- 當gap越小，數(shù)據(jù)處理越慢，越接近有序
- 當gap為1即直接插入排序
如下代碼所示：所以我們可以對gap進行動態(tài)改變
void ShellSort(int* arr, int size)//希爾排序
{
int gap = size;
//多次預(yù)排+最后一次直接插入排序
while (gap > 1)
{
gap = gap / 3 + 1;//控制最后一次進來gap為1進行直接插入排序
for (int i = 0; i < size - gap; i++)
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}3.選擇排序:
選擇排序在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?，然后以此類推，直到所有元素均排序完畢。
動圖演示:
我們實際可以在一次遍歷中同時找到最小和最大的值：
void SelectSort(int* arr, int size)//優(yōu)化選擇排序
{
int begin = 0;
int end = size - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin + 1; i <= end; i++)
{
if (arr[i] < arr[mini])
{
mini = i;
}
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
Swap(&arr[mini], &arr[begin]);
//如果maxi = begin，上一步交換了begin和mini的值，會影響maxi指向的值
if (maxi == begin)
{
maxi = mini;
}
Swap(&arr[maxi], &arr[end]);
begin++;
end--;
}
}4.堆排序:
堆排序可以看之前這篇：C語言中的二叉樹和堆詳解
5.冒泡排序:
冒泡排序也是通過遍歷比較左右值得大小，例如排升序即左值大于右值交換，最后最大值即排到最右邊。
動圖演示：
void BubbleSort(int* arr, int size)//冒泡排序
{
for (int i = 1; i < size; i++)
{
int flag = 0;
for (int j = 0; j < size - i; j++)
{
if (arr[j] > arr[j + 1])
{
Swap(&arr[j], &arr[j + 1]);
flag++;
}
}
if (flag == 0)
{
break;
}
}
}6.快速排序:
這邊講解的是快速排序的前后指針法：
- 首先選擇一個keyi位置，一般為序列首。
- 創(chuàng)建兩個指針，prev指向keyi，cur指向prev+1
- cur往右找小于keyi位置的值，如果找到了prev往前找大于keyi位置的值，然后交換cur和prev位置的值（注意，這里既然cur找到arr[cur]>arr[keyi],那么cur和prev之間的值必然都會大于arr[keyi]）
- 最后cur走完序列，再把keyi和prev位置值交換，這樣keyi左邊都會比他小，右邊都會比他大
- 再將區(qū)間分為[begin,keyi-1],[keyi+1,end]繼續(xù)遞歸直至有序
動圖演示：
7.歸并排序:
歸并排序?qū)⒁延行虻淖有蛄泻喜?，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
動圖演示：
void _MergeSort(int* arr, int begin, int end, int* tmp)
{
if (begin >= end)
{
return;
}
//遞歸找有序區(qū)間
int mid = (end + begin) / 2;
//[begin, mid][mid+1,end]
_MergeSort(arr, begin, mid, tmp);
_MergeSort(arr,mid + 1, end, tmp);
//左右區(qū)間歸并有序
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] <= arr[begin2])
{
tmp[i++] = arr[begin1++];
}
else
{
tmp[i++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = arr[begin2++];
}
//輔助數(shù)組tmp中數(shù)據(jù)返回拷貝到原數(shù)組
memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* arr, int size)//歸并排序
{
int* tmp = (int*)malloc(sizeof(int) * size);
if (tmp == NULL)
{
perror("malloc:fail");
exit(-1);
}
int begin = 0;
int end = size - 1;
_MergeSort(arr, begin, end, tmp);
}8.計數(shù)排序:
- 統(tǒng)計相同元素出現(xiàn)次數(shù)根據(jù)
- 統(tǒng)計的結(jié)果將序列回收到原來的序列中
- 計數(shù)排序只適用于范圍集中且重復(fù)數(shù)據(jù)較高的數(shù)據(jù)
動圖演示：
//計數(shù)排序只適用于范圍集中且重復(fù)數(shù)據(jù)較高的數(shù)據(jù)
void CountSort(int* arr, int size)//計數(shù)排序
{
int min = arr[0];
int max = arr[0];
for (int i = 1; i < size; i++)
{
if (arr[i] < min)
{
min = arr[i];
}
if (arr[i] > max)
{
max = arr[i];
}
}
//計數(shù)數(shù)組count
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc:fail");
exit(-1);
}
memset(count, 0, sizeof(int) * range);
//開始計數(shù)
for (int i = 0; i < size; i++)
{
count[arr[i] - min]++;
}
//回寫排序
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
arr[j++] = i + min;
}
}
}二、八大排序算法總結(jié)：
| 排序算法 | 時間復(fù)雜度（平均） | 時間復(fù)雜度（最壞） | 時間復(fù)雜度（最好） | 空間復(fù)雜度 | 穩(wěn)定性 |
| 插入排序 | O(N^2) | O(N^2) | O(N) | O(1) | 穩(wěn)定 |
| 希爾排序 | O(N^1.3) | O(N^2) | O(N) | O(1) | 不穩(wěn)定 |
| 選擇排序 | O(N^2) | O(N^2) | O(N^2) | O(1) | 不穩(wěn)定 |
| 堆排序 | O(N*log2(N)) | O(N*log2(N)) | O(N*log2(N)) | O(1) | 不穩(wěn)定 |
| 冒泡排序 | O(N^2) | O(N^2) | O(N) | O(1) | 穩(wěn)定 |
| 快速排序 | O(N*log2(N)) | O(N^2) | O(N*log2(N)) | O(N*log2(N)) | 不穩(wěn)定 |
| 歸并排序 | O(N*log2(N)) | O(N*log2(N)) | O(N*log2(N)) | O(N) | 穩(wěn)定 |
| 計數(shù)排序 | O(N+K) | O(N+K) | O(N+K) | O(N+K) | 穩(wěn)定 |
到此這篇關(guān)于C語言中的八大排序算法詳解的文章就介紹到這了,更多相關(guān)C語言排序算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
QT5中使用QRegularExpression代替QRegExp方法代碼
這篇文章主要給大家介紹了關(guān)于QT5中使用QRegularExpression代替QRegExp的相關(guān)資料,正則表達式(regep)是處理字符串和文本的強大工具,驗證regexp可以測試子字符串是否滿足某些條件,例如是整數(shù)或不包含空格,需要的朋友可以參考下2024-04-04
因為之前的文章有說過C++中 set的介紹及用法，今天這篇文章我們就來說說C++為什么不能修改set里的值，如果非要修改的話應(yīng)該怎么辦，下面我們一起進入文章看看下面內(nèi)容,需要的朋友可以參考以下，希望對你有所幫助2021-11-11
這篇文章主要為大家詳細介紹了C語言貪吃蛇經(jīng)典小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
std::vector<T>?可以通過多種方式清除（刪除所有元素）,本文主要介紹了C++ 中std::vector＜T＞的幾種清除方式,具有一定的參考價值,感興趣的可以了解一下2025-04-04
這篇文章主要介紹了print緩沖區(qū)刷新問題，實現(xiàn)代碼簡單易懂，具有很好的參考價值，希望對大家有所幫助，需要的朋友可以參考下2022-05-05
C++實現(xiàn)LeetCode(41.首個缺失的正數(shù))
這篇文章主要介紹了C++實現(xiàn)LeetCode(41.首個缺失的正數(shù)),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
Qt實現(xiàn)將qsqlite數(shù)據(jù)庫中的數(shù)據(jù)導(dǎo)出為Excel表格
這篇文章主要為大家詳細介紹了如何通過Qt實現(xiàn)將qsqlite數(shù)據(jù)庫中的數(shù)據(jù)導(dǎo)出為Excel表格,文中的示例代碼簡潔易懂,有需要的小伙伴可以了解一下2024-12-12
C++實現(xiàn)LeetCode(50.求x的n次方)
這篇文章主要介紹了C++實現(xiàn)LeetCode(50.求x的n次方),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
本文通過實例代碼給大家介紹了基于Qt實現(xiàn)視頻播放器功能，代碼簡單易懂，對大家的學(xué)習或工作具有一定的參考借鑒價值，需要的朋友參考下吧2021-09-09
這篇文章主要介紹了深入淺析C語言中堆棧和隊列的相關(guān)資料,需要的朋友可以參考下2016-06-06