??博主個人主頁:不是笨小孩??
?專欄分類:數(shù)據(jù)結(jié)構(gòu)與算法?? 刷題專欄?? C語言??
??代碼倉庫:笨小孩的代碼庫??
?社區(qū)：不是笨小孩??
??歡迎大家三連關(guān)注，一起學(xué)習(xí)，一起進(jìn)步?。??
排序的概念
排序：所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。
穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次 序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排 序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。
外部排序：數(shù)據(jù)元素太多不能同時放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序。
常見的排序算法：
除了這些排序以外，該有一個很奇怪的排序，計數(shù)排序，我們待會將，我們接下來，就從第一個排序開始：
插入排序
插入排序的思想很簡單就是把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。插入排序可以理解為就是我們打撲克牌摸排的過程，摸一張排，依次比較然后將它插入的合適的位置。
我們看圖：
這個排序很簡單，根據(jù)圖我們就可以把第一個數(shù)據(jù)當(dāng)成有序的數(shù)據(jù)，然后后面的數(shù)據(jù)依次插入，直到將數(shù)據(jù)插入完，這樣就有序了。
代碼如下：
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n-1; i++)
{
//end表示有序數(shù)據(jù)的最后一數(shù)的下標(biāo)
int end = i;
//tmp保存需要插入的值
int tmp = arr[end+1];
while (end >= 0)
{
//依次比較如果比需要插入的數(shù)大，就往后移，否則就跳出循環(huán)
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
//跳出循環(huán)后將需要插入的數(shù)據(jù)放到end后面的位置
arr[end + 1] = tmp;
}
}
總結(jié)：
- 元素集合越接近有序，直接插入排序算法的時間效率越高
- 時間復(fù)雜度：O(N^2)
- 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法
- 穩(wěn)定性：穩(wěn)定
希爾排序
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數(shù)gap，把待排序文件中所有記錄分成gap個組，所有距離為gap的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進(jìn)行排序。然后，重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_(dá)=1時，所有記錄在統(tǒng)一組內(nèi)排好序。
插入排序第一步我們需要預(yù)排序
預(yù)排序后插入排序就很快了，直接使用插入排序就可以了。但是當(dāng)我們的gap=1是，希爾排序就相當(dāng)于插入排序了。這里gap可以取很多值，但是要保證最后一次gap=1.
代碼如下：
void ShellSort(int* arr, int n)
{
int gap = n;
//要進(jìn)行多趟排序
while (gap > 1)
{
//+1是為了保證gap最后一次等于1
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)
{
//每次分別排gap組數(shù)據(jù)，每組間隔gap個數(shù)據(jù)，一共gap組
int end = i;
int tmp = arr[i + gap];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}
總結(jié)：
- 希爾排序是對直接插入排序的優(yōu)化。
- 當(dāng)gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就 會很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測試的對比。
- 希爾排序的時間復(fù)雜度不好計算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計算，因此在好些樹中給出的 希爾排序的時間復(fù)雜度都不固定：我們記住大約就等于O(N^1.3)
- 穩(wěn)定性：不穩(wěn)定
選擇排序
選擇排序是每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完 。
我們這里實(shí)現(xiàn)的是依次找大的，然后放到最后面，和圖不太一樣，但是思想都一樣。
代碼如下：
void SelectSort(int* arr, int n)
{
int end = n - 1;
while (end>0)
{
//每次初始化最大在0處，防止maxi到已經(jīng)在排好序的位置
int maxi = 0;
for (int i = 0; i <= end; i++)
{
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
//找到后和最后一個數(shù)據(jù)交換
Swap(&arr[maxi], &arr[end]);
end--;
}
}
選擇排序我們這里可以優(yōu)化一下，就是每次選出最小的和最大的，然后最小的放到左邊，最大的放到右邊，然后接著找剩余數(shù)據(jù)的最大最小，直到結(jié)束。
代碼如下：
void SelectSort(int* arr, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int maxi = begin;
int mini = begin;
//依次找大和找小
for (int i = begin; i <= end; i++)
{
if (arr[mini] > arr[i])
{
mini = i;
}
if (arr[maxi] < arr[i])
{
maxi = i;
}
}
//找到后將大的數(shù)據(jù)放到后面
Swap(&arr[maxi], &arr[end]);
//防止最小的數(shù)據(jù)在最后面被換走了，及時修正
if (mini == end)
{
mini = maxi;
}
Swap(&arr[mini], &arr[begin]);
begin++;
end--;
}
}
總結(jié)：
- 直接選擇排序思考非常好理解，但是效率不是很好。實(shí)際中很少使用
- 時間復(fù)雜度：O(N^2)
- 空間復(fù)雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
冒泡排序
冒泡排序大多數(shù)人應(yīng)該都知道，它的基本思想就是依次比較，將大的數(shù)據(jù)冒到最后然后重復(fù)前面的過程，就可以完成排序。
代碼如下：
void BubbleSort(int* arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
int flag = 1;
for (int j = 1; j < n - i; j++)
{
if (arr[j] < arr[j - 1])
{
Swap(arr + j, arr + j - 1);
flag = 0;
}
}
if (flag == 1)
{
break;
}
}
}
總結(jié)：
- 冒泡排序是一種非常容易理解的排序
- 時間復(fù)雜度：O(N^2)
- 空間復(fù)雜度：O(1)
- 穩(wěn)定性：穩(wěn)定
堆排序
堆排序前面已經(jīng)講過一次了，這里就不做過多的解釋了，想要詳細(xì)了解請戳。
這里是引用
總結(jié)：
- 堆排序使用堆來選數(shù)，效率就高了很多。
- 時間復(fù)雜度：O(N*logN)
- 空間復(fù)雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
快速排序
快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中
的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右
子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。
我們每次可以將數(shù)組劃分為兩部分，keyi是那個選出來的數(shù)的最終的下標(biāo)，然后第一次排序后就是[left,keyi-1],keyi,[keyi+1,right]，我們每一趟要保證的是keyi左邊的數(shù)據(jù)逗比key小，右邊的都比它大，然后左區(qū)間重復(fù)這個操作，右區(qū)間也重復(fù)這個操作，這就有點(diǎn)像二叉樹的前序遍歷，直到每個區(qū)間只剩下一個值，或者區(qū)間不存在時，我們結(jié)束遞歸。
快排的整體框架：
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = partSort(arr,left,right);
QuickSort(arr,left, keyi - 1);
QuickSort(arr,keyi + 1, right);
}
這里的partSort就是我們的單趟排序，我們講三種方法：
- hoare版本
我們需要兩個指針，一個從左邊開始走，一個從右邊開始走，再定義一個key，和keyi，keyi保存key的小標(biāo)，如果左邊左key就右邊先走，右邊左key就左邊先走，，然后左邊找比key大的數(shù)，右邊找比key小的數(shù)，找到后交換，然后接著走，直到相遇，然后把相遇的位置和key交換一下。
為什么左邊做key右邊先走呢？
因?yàn)檫@樣可以保證相遇的位置一定是比key小等于的數(shù)，相遇無非就是兩種情況，L遇到R，R遇到L，如果是L遇到R，我們讓右邊先走，R停下的位置一定是比key小的數(shù)，如果是R遇L，假設(shè)數(shù)組中的數(shù)都比key大，所以key遇到L是就是等于key，所以我們左邊做key讓右邊先走，是可以保證相遇位置一定比key小的。
代碼如下：
int partSort1(int* arr, int left, int right)
{
int keyi = left;
while (left < right)
{
//右邊找小
while (left < right && arr[right] >= arr[keyi])
{
right--;
}
//左邊找大
while (left < right && arr[left] <= arr[keyi])
{
left++;
}
Swap(&arr[left], &arr[right]);
}
Swap(&arr[left], &arr[keyi]);
return left;
}
- 挖坑法
我們還是將左邊做key，然后保存它的值，然后它就是一個坑，還是兩個指針，由于左邊有一個坑，所以右邊就要找小的數(shù)來填這個坑，然后將右邊的那個位置變成新的坑，然后左邊找大，找到后接著填坑，更新坑的位置，L和R一定有一個是坑，所以，當(dāng)他們相遇時，那個位置一定是坑，然后將key放進(jìn)去即可。
代碼如下：
int partSort2(int* arr, int left, int right)
{
int hole = arr[left];
int keyi = left;
while (left < right)
{
while (left < right && arr[right] >= hole)
{
right--;
}
arr[keyi] = arr[right];
keyi = right;
while (left < right && arr[left] <= hole)
{
left++;
}
arr[keyi] = arr[left];
keyi = left;
}
arr[keyi] = hole;
return keyi;
}
- 前后指針法
定義兩個指針一個prev一個cur，cur用來遍歷數(shù)組，還是用左邊的值來做key，然后將cur找到比key小的值就和++prev位置的數(shù)交換直到遍歷結(jié)束，然后再把prev位置的值可key交換即可。
代碼如下：
int partSort3(int* arr, int left, int right)
{
int keyi = left;
int cur = left + 1;
int prev = left;
while (cur <= right)
{
if (arr[cur] < arr[keyi]&&++prev!=cur)
{
Swap(&arr[prev], &arr[cur]);
}
cur++;
}
Swap(&arr[prev], &arr[keyi]);
return prev;
}
快速排序的非遞歸版本
非遞歸的話，我們用隊(duì)列和棧都是可以的，但是想要模仿遞歸的路徑的話我們就要使用棧，我們先把數(shù)組的整個區(qū)間放到棧里面，然后在進(jìn)行一趟排序后，我們把排出來的左區(qū)間和右區(qū)間入棧，由于先走左邊，所以就要先把右邊的區(qū)間壓棧，然后依次進(jìn)行，只要區(qū)間存在，我們就壓，只要棧不為空，就代表一直有區(qū)間未處理。所以我們就一直重復(fù)操作，當(dāng)然單趟排序的話，用上面的那種方法都可以。
代碼如下：
void QuickSortNonR(int* arr, int left, int right)
{
Stack st;
StackInit(&st);
StackPush(&st,right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
int keyi = partSort1(arr, begin, end);
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (keyi - 1 > begin)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
}
快速排序，還可以優(yōu)化，他的效率和選的key的關(guān)系很大，所以我們有種方法叫做三數(shù)取中，左邊的值、右邊的值、中間的值，然都找到這三個數(shù)中間的數(shù)，把他換到左邊，就可以了。
總結(jié)：
- 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
- 時間復(fù)雜度：O(N*logN)
- 空間復(fù)雜度：O(logN)
- 穩(wěn)定性：不穩(wěn)定
歸并排序
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
歸并排序需要將區(qū)間分為兩部分，然后兩部分都要有序才能歸并，那左右區(qū)間又可以分割，以此類推，當(dāng)區(qū)間只有一個數(shù)的時候就可以認(rèn)為有序，這時我們可以走一個類似與二叉樹后序遍歷的思路，我們想歸并左右區(qū)間，但是左右區(qū)間都無序，我們就遞歸左邊讓左邊有序，在遞歸右邊讓右邊有序，最后再左右歸并，就可以排好了。
我們這里就需要一個數(shù)組來保存我們歸并的值，我們?nèi)啥螀^(qū)間的值依次比較，拿小的尾插到tmp數(shù)組中，等歸并完再拷回原數(shù)組，即可。
代碼如下：
void _MergeSort(int* arr, int left, int right,int* tmp)
{
if (left >= right)
{
return;
}
//分割區(qū)間
int mid = (left + right) / 2;
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid+1, right, tmp);
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int k = left;
while (begin1 <= end1 && begin2 <= end2)
{
//選小的來尾插
if (arr[begin1] <= arr[begin2])
{
tmp[k++] = arr[begin1++];
}
else
{
tmp[k++] = arr[begin2++];
}
}
//不管哪個沒有拷貝完，因?yàn)閰^(qū)間是有序地，直接尾插就可以
while (begin1 <= end1)
{
tmp[k++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[k++] = arr[begin2++];
}
//拷貝回原數(shù)組
memcpy(arr + left, tmp + left, (right - left + 1) * sizeof(int));
}
void MergeSort(int* arr, int left, int right)
{
int* tmp = (int*)malloc(sizeof(int) * (right - left + 1));
//不能在這個函數(shù)中遞歸，不然每次都要開辟數(shù)組
_MergeSort(arr, left, right, tmp);
free(tmp);
}
歸并排序的非遞歸版本
我們會發(fā)現(xiàn)歸并排序用隊(duì)列和棧都用不了，但是我們可以使用循環(huán)來解決它，首先我們需要一個gap來記錄每組歸并的數(shù)據(jù)有幾個，然后控制區(qū)間，來進(jìn)行歸并。
但是在歸并中，會存在很多的越界問題，比如end1越界了，或者begin1越界了，但是這兩種情況我們都很好處理，等處理到這種錯誤時我們可以看成只剩下一組數(shù)據(jù)，就可以不用動，放在原數(shù)就好，等待下一輪歸，直接break跳出就可以，還有一種情況是end2越界了，這時還有一部分?jǐn)?shù)據(jù)需要?dú)w并，那我們就調(diào)整end2為n-1就可以了。
代碼如下：
void MergeSortNonR(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
int gap = 1;
//gap表示每組數(shù)據(jù)的長度
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
//控制區(qū)間
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
int k = i;
//越界即使調(diào)整或退出
if (end1 >= n || begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] <= arr[begin2])
{
tmp[k++] = arr[begin1++];
}
else
{
tmp[k++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[k++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[k++] = arr[begin2++];
}
//每次歸并完拷貝會原數(shù)組
memcpy(arr+i, tmp+i, sizeof(int)*(end2-i+1));
}
gap *= 2;
}
free(tmp);
}
總結(jié)：
- 歸并的缺點(diǎn)在于需要O(N)的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
- 時間復(fù)雜度：O(N*logN)
- 空間復(fù)雜度：O(N)
- 穩(wěn)定性：穩(wěn)定
計數(shù)排序
計數(shù)排序是非常奇怪的排序，它不需要比較任何數(shù)據(jù)，他開辟一個和最大值一樣的數(shù)組，然后將該數(shù)組初始化為0，然后原遍歷數(shù)組，將原數(shù)組的值對應(yīng)到我們開辟數(shù)組的下標(biāo)，出現(xiàn)一次我們就++該位置，然后統(tǒng)計每個位置出現(xiàn)的次數(shù)，然后在依次拷貝回原數(shù)組，就可以了。
但是如果數(shù)據(jù)很大很集中，我們就沒必要開那么大，會很浪費(fèi)，我們需要找到最大值和最小值，然后使用相對位置，就可以了，每個數(shù)對應(yīng)到減去最小值的那個小下標(biāo)，這樣我們數(shù)組也不用開的很大。
代碼如下：
void CountSort(int* arr, int n)
{
int min = arr[0];
int max = arr[0];
//找最大值和最小值
for (int i = 0; i < n; i++)
{
if (max < arr[i])
{
max = arr[i];
}
if (min > arr[i])
{
min = arr[i];
}
}
//計算區(qū)間方便開數(shù)組
int c =max-min+1;
int* nums = (int*)malloc(sizeof(int) * c);
memset(nums, 0, c * sizeof(int));
//統(tǒng)計
for (int i = 0; i < n; i++)
{
nums[arr[i]-min]++;
}
int k = 0;
//拷貝回原數(shù)組
for (int i = 0; i < c; i++)
{
while (nums[i]--)
{
arr[k++] = i+min;
}
}
free(nums);
}
總結(jié)：文章來源：http://www.zghlxwxcb.cn/news/detail-652428.html
- 計數(shù)排序在數(shù)據(jù)范圍集中時，效率很高，但是適用范圍及場景有限。
- 時間復(fù)雜度：O(MAX(N,范圍))
- 空間復(fù)雜度：O(范圍)
- 穩(wěn)定性：穩(wěn)定
各大排序的比較：
今天的分享就到這里感謝大家的關(guān)注和支持！文章來源地址http://www.zghlxwxcb.cn/news/detail-652428.html
到了這里，關(guān)于八大排序超詳解(動圖+源碼)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
