一、冒泡排序
如需更詳細步驟可見：冒泡排序
1、定義
冒泡排序(bubble sort)是最基礎(chǔ)的排序算法，它是一種基礎(chǔ)的交換排序。它的原理就像汽水一樣，汽水中常常有許多小氣泡飄到上面。而冒泡排序這種排序算法的每一個元素也可以像小氣泡一樣根據(jù)自身大小一點點地向著數(shù)組一端移動。
2、思想及圖解
冒泡排序的思想：相鄰元素兩兩比較，當(dāng)一個元素大于右側(cè)相鄰元素時，交換他們的位置；當(dāng)一個元素小于或等于右側(cè)元素時，位置不變。
對于以下這個無序的數(shù)列，用冒泡排序的思想進行排序：
冒泡排序單次排序圖解：
當(dāng)通過一輪排序之后，元素9作為最大的元素，移動到了數(shù)列的最右端。9是目前有序數(shù)列的唯一元素。，然后繼續(xù)對數(shù)列進行排序…
整體流程圖解：
3、代碼
//交換
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//冒泡排序
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n ; i++)
{
//記錄交換次數(shù)
int e = 0;
for (int j = 1; j < n-i; j++)
{
if (a[j] < a[j - 1])
{
Swap(&a[j], &a[j - 1]);
e++;
}
}
//本次沒有交換過，已經(jīng)有序
if (e == 0)
{
break;
}
}
}
時間復(fù)雜度：O(n2)
空間復(fù)雜度：O(1)
二、快速排序
如需更詳細步驟可見：快速排序
1、hoare版本
快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。
算法思想：
- 定義一個keyi存入隨機一個數(shù)key的下標換到數(shù)組首元素，這里先直接默認key為數(shù)組首元素
- 定義一個left和一個right，分別存入數(shù)組首元素和尾元素的下標，用來移動交換
- 排升序我們讓右邊right先向左移動，找到比key的值小的元素則停下來換到left移動
- left向右移動，找到比key的值大的元素則停下
- 交換下標為left和right的元素
- 重復(fù)以上操作直到left與right相遇（相等）
- 交換key和下標為left的元素
- 此時key的左邊都是比它小的數(shù)，右邊都是比它大的數(shù)
- 再分別對左右序列進行以上的單趟排序，反復(fù)操作直到左右序列只有一個或者沒有元素時停止操作，數(shù)列即可有序
hoare版本單趟排序圖示：
hoare版本代碼：
//交換
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//hoare版本
void QuickSort1(int* a, int begin, int end)
{
//遞歸結(jié)束條件
if (begin >= end)
{
return;
}
int keyi = begin;
int left = begin;
int right = end;
//每趟排序直到左右相遇
while (left < right)
{
//右邊先走，找到比key值小的
while (left < right && a[right] >= a[keyi])
{
right--;
}
//right找到比key值小的之后換到left走，找到比key值大的
while (left < right && a[left] <= a[keyi])
{
left++;
}
//交換
Swap(&a[left], &a[right]);
}
//將key值換到中間
Swap(&a[keyi], &a[left]);
//更新key
keyi = left;
//對左右序列繼續(xù)排序
QuickSort1(a, begin, keyi - 1);
QuickSort1(a, keyi + 1, end);
}
整體流程圖：
2、挖坑法
挖坑法思想：
- 先將第一個數(shù)據(jù)存在變量key中，將此處作為最開始的坑位，用下標hole記錄
- 然后right開始向前走，找到比key值小的元素后停下，將此元素放進坑里（下標為hole處），然后此處變?yōu)榭?，hole變?yōu)榇藭r的right
- 然后left開始向后移動，找到比key值大的元素后停下，將此元素放進坑里（下標為hole處），然后此處變?yōu)榭樱琱ole變?yōu)榇藭r的left
- 然后又換回right移動，如此反復(fù)直到left與right相遇（left與right相遇的地方一定是坑）
- 然后將key放入left與right相遇的位置，也就是坑的位置，此時hole左邊都是小于等于它的，右邊都是大于等于它的
- 如此單趟排序便結(jié)束，然后繼續(xù)對hole左右序列繼續(xù)反復(fù)執(zhí)行以上操作，直到左右序列只有一個或者沒有元素時停止操作，數(shù)列即可有序
挖坑法單趟排序圖示：
挖坑法代碼：
//挖坑法
void QuickSort2(int* a, int begin, int end)
{
//遞歸結(jié)束條件
if (begin >= end)
{
return;
}
int left = begin;
int right = end;
int key = a[left];
//坑最初與left一樣在開始位置
int hole = left;
//每趟排序直到左右相遇
while (left < right)
{
//右邊先走，找到比key值小的
while (left < right && a[right] >= key)
{
right--;
}
//將right找到的比key小的元素放進坑中
a[hole] = a[right];
//更新坑的位置
hole = right;
//然后左邊走找到比key值大的元素停下來
while (left < right && a[left] <= key)
{
left++;
}
//將left找到的比key大的元素放進坑中
a[hole] = a[left];
//更新坑的位置
hole = left;
}
//將key放入坑中
a[hole] = key;
//對左右序列繼續(xù)排序
QuickSort2(a, begin, hole - 1);
QuickSort2(a, hole+1, end);
}
3、前后指針法
前后指針法思想：
- 定義一個keyi存入隨機一個數(shù)key的下標換到數(shù)組首元素，這里先直接默認key為數(shù)組首元素
- 定義一個prev為開頭元素的下標，定義一個cur為prev下一個元素的下標
- cur下標處的值與key比較，直到cur找到比key小的值則停下來
- prev下標后移一位然后與cur下標處的值交換，然后cur后移一位（prev相當(dāng)于前面比key小的那些數(shù)的最后一個的下標，所以要先后移一位再交換）
- cur繼續(xù)尋找比key小的值，反復(fù)執(zhí)行直到cur的值大于n
- 將key與prev下標處的值交換，此時key左邊都是小于等于它的，右邊都是大于等于它的
- 如此單趟排序便結(jié)束，然后繼續(xù)對key左右序列繼續(xù)反復(fù)執(zhí)行以上操作，直到左右序列只有一個或者沒有元素時停止操作，數(shù)列即可有序
前后指針法單趟排序圖示：
前后指針法代碼：
//交換
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//前后指針
void QuickSort3(int* a, int begin, int end)
{
//遞歸結(jié)束條件
if (begin >= end)
{
return;
}
int keyi = begin;
int prev = begin;
int cur = begin + 1;
//每趟排序直到cur下標大于end
while (cur <= end)
{
//cur找比key小的值
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
//將key換到中間
Swap(&a[keyi], &a[prev]);
//更新key的下標
keyi = prev;
//對左右序列繼續(xù)排序
QuickSort3(a, begin, keyi - 1);
QuickSort3(a, keyi + 1, end);
}
快速排序是一種不穩(wěn)定的排序，它的時間復(fù)雜度為O(N*logN)，但最壞可以達到O(N2) ，它的空間復(fù)雜度為O(logN)
4、非遞歸快排
以上三種方法都是采用了分治法遞歸實現(xiàn)的快排，其實快速排序也可以非遞歸實現(xiàn)，非遞歸實現(xiàn)快排需要利用棧來實現(xiàn)
思路：
將數(shù)組首尾下標存入棧中，在循環(huán)中依次取出作為left和right對數(shù)組進行排序，然后對得到的key的左右兩邊序列也進行相同的操作，其中左邊為left到keyi-1，右邊為keyi+1到right，這些下標的入棧順序需要看取出的順序，如下面代碼中是先取出后面元素下標的，所以入棧時要先入后面的，因為棧的特點是先入后出。
非遞歸快排代碼：
（該代碼中用到的棧需自己實現(xiàn)，C語言實現(xiàn)?？蓞⒖迹簵５膶崿F(xiàn)）
//非遞歸快速排序
void QuickSortNonR(int* a, int begin, int end)
{
//創(chuàng)建一個棧
ST st;
//初始化棧
STInit(&st);
//插入尾元素下標
STPush(&st, end);
//插入首元素下標
STPush(&st, begin);
//棧為空停下
while (!STEmpty(&st))
{
//取出棧頂元素作為left
int left = STTop(&st);
//取出后在棧中刪除
STPop(&st);
//取出棧頂元素作為right
int right = STTop(&st);
//取出后在棧中刪除
STPop(&st);
int keyi = begin;
//每趟排序直到左右相遇
while (left < right)
{
//右邊先走，找到比key值小的
while (left < right && a[right] >= a[keyi])
{
right--;
}
//right找到比key值小的之后換到left走，找到比key值大的
while (left < right && a[left] <= a[keyi])
{
left++;
}
//交換
Swap(&a[left], &a[right]);
}
//將key值換到中間
Swap(&a[keyi], &a[left]);
//更新key的下標
keyi = left;
// 當(dāng)前數(shù)組下標樣子 [left,keyi-1] keyi [keyi+1, right]
//右邊還有元素，按順序插入right和keyi+1
if (keyi + 1 < right)
{
STPush(&st, right);
STPush(&st, keyi + 1);
}
//左邊還有元素，按順序插入keyi-1和left
if (left < keyi - 1)
{
STPush(&st, keyi - 1);
STPush(&st, left);
}
}
STDestroy(&st);
}
5、快速排序優(yōu)化
1）三數(shù)取中選key值
前面三種快速排序的方法起初都要隨機選取一個值作為key，我們之前是直接默認為數(shù)組首元素的，這樣不夠隨機，容易出現(xiàn)最壞的情況，使得它的時間復(fù)雜度接近O(N2)，所以我們可以寫一個函數(shù)來選取這個key，使得它比較隨機，而不是直接為首元素。
三數(shù)取中：
在一個數(shù)組最前面、最后面，中間這三個位置的數(shù)中選出大小處于中間的數(shù)
// 三數(shù)取中
int GetMidi(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] > a[right])
{
if (a[right] > a[mid])
{
return right;
}
else if(a[mid]>a[right]&&a[mid]<a[left])
{
return mid;
}
else
{
return left;
}
}
else
{
if (a[left] > a[mid])
{
return left;
}
else if (a[mid] > a[left] && a[mid] < a[right])
{
return mid;
}
else
{
return right;
}
}
}
在快排時用三數(shù)取中法選取key值再將它換到數(shù)組開頭，可以有效避免出現(xiàn)最壞的情況，大大提升算法效率
2）小區(qū)間優(yōu)化
當(dāng)遞歸到數(shù)據(jù)較小時可以使用插入排序，使得小區(qū)間不再遞歸分割，降低遞歸次數(shù)
三、直接插入排序
1、定義
直接插入排序就是將待排序的記錄按照它的關(guān)鍵碼值插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄都插入完，得到一個新的有序序列。
插入排序的思想就像我們平時玩撲克牌理牌時一樣，將每張牌逐個插入到一個有序的牌的序列里，最終所有的牌都是有序的。
2、代碼
//插入排序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n-1; i++)
{
//end可看作從左至右有序的最后一個數(shù)的下標
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
}
else
{
break;
}
end--;
}
//此時tmp的值大于或等于下標為end的值，所以插入在它的后面
a[end+1] = tmp;
}
}
當(dāng)插入第i(i>=1)個元素時，前面的a[0],a[1],…,a[i-1]已經(jīng)排好序，此時用a[i]的排序碼與a[i-1],a[i-2],…的排序碼順序進行比較，找到插入位置即將a[i]插入，原來位置上的元素順序后移
直接插入排序是一種穩(wěn)定的排序算法，元素集合越接近有序，直接插入排序算法的時間效率越高，它的時間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)
四、希爾排序
如需更詳細步驟可見：希爾排序
1、定義
希爾排序法又稱縮小增量法。希爾排序的基本思想是：先選定一個整數(shù)gap，把待排序數(shù)列中所有記錄分成個gap個組，所有距離為gap的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進行排序。然后縮小gap，可以取它的一半，重復(fù)上述分組和排序的工作。當(dāng)gap到達1時，該數(shù)列便已有序。
當(dāng)gap=1時相當(dāng)于直接插入排序。所以希爾排序可以拆分為預(yù)排序和直接插入排序兩部分：
- 預(yù)排序：當(dāng)gap大于1時，預(yù)排序可以讓大的數(shù)更快地到序列后面，小的更快到前面，gap越大跳的越快越不接近有序，gap越小跳的越慢，越接近有序
- 直接插入排序：gap不斷減小，當(dāng)gap為1時相當(dāng)于直接插入排序，進行最后一次直接插入排序后數(shù)列便已有序
2、圖解
對如下圖數(shù)列用希爾排序算法進行排序：
該數(shù)列一共有8個數(shù)，我們選定最初的gap值為8/2=4，相隔4的數(shù)為一組，如下圖，同一組數(shù)顏色相同
對每一組排序了之后，gap再除2變?yōu)?
對每一組排序了之后，gap再除2變?yōu)?，此時相當(dāng)于直接插入排序
3、代碼
//希爾排序
void ShellSort(int* a, int n)
{
//gap進入循環(huán)后會先除2
int gap = n ;
while (gap > 1)
{
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];
}
else
{
break;
}
end -= gap;
}
a[end + gap] = tmp;
}
}
}
希爾排序是不穩(wěn)定的，它是對直接插入排序的優(yōu)化，因為gap的取值方法不止一種，導(dǎo)致希爾排序的時間復(fù)雜度很難去計算
五、選擇排序
1、排序思想
每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完 。
- 在元素集合array[i]–array[n-1]中選擇關(guān)鍵碼最大(小)的數(shù)據(jù)元素
- 若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換
- 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重復(fù)上述步驟，直到集合剩余1個元素
2、代碼
這里的代碼是優(yōu)化過的，同時找最大和最小元素，最小的放左邊，最大的放右邊，然后對除了兩邊找出的值外剩下的元素繼續(xù)進行相同操作，直到left不再小于right則有序
//交換
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//選擇排序
void SelectSort(int* a, int n)
{
int left = 0;
int right = n - 1 ;
while (left < right)
{
int maxi = left;
int mini = left;
for (int i = left + 1; i <= right; i++)
{
//找區(qū)間內(nèi)最大元素下標
if (a[i] > a[maxi])
{
maxi = i;
}
//找區(qū)間內(nèi)最小元素下標
if (a[i] < a[mini])
{
mini = i;
}
}
Swap(&a[left], &a[mini]);
//如果最大數(shù)的下標等于left，上一次交換最小數(shù)時已經(jīng)被換到下標為mini元素上
if (maxi == left)
{
maxi = mini;
}
Swap(&a[right], &a[maxi]);
left++;
right--;
}
}
時間復(fù)雜度：O(N2)
空間復(fù)雜度：O(1)
六、堆排序
如需更詳細步驟可見：堆排序
1、定義
堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆
1、根據(jù)要排什么序建大堆或小堆，此時堆頂端的元素就是最值
2、將頂端元素和末尾元素交換，此時末尾元素就是有序的，剩下的還有n-1個元素
3、將剩下的n-1個元素再次構(gòu)建成堆，然后將堆頂端元素與第n-1個元素互換，反復(fù)執(zhí)行便可得到有序數(shù)組
2、向上調(diào)整建堆排序
使用向上調(diào)整算法建堆的堆排序
例如：將數(shù)組a用堆排序按從小到大排列（升序）
向上調(diào)整算法的前提條件是：前面的元素是堆
對于單個結(jié)點來說既可以看作一個大堆，所以便可以通過向上調(diào)整算法依次對數(shù)組元素進行調(diào)整，那進行調(diào)整的元素前就一定是堆，滿足條件
創(chuàng)建好的大堆如下：
將堆的頂端元素7和末尾元素2進行交換，對除7外剩下的元素進行向下調(diào)整重新構(gòu)建大堆
此時7已經(jīng)是有序的，將元素6和元素3進行交換，對除6、7外剩下元素進行向下調(diào)整重新構(gòu)建大堆
此時6、7已經(jīng)有序，將元素5和元素2進行交換，對除5、6、7外剩下元素進行向下調(diào)整重新構(gòu)建大堆
此時5、6、7已經(jīng)有序，將元素4和元素2進行交換，此時數(shù)組已經(jīng)有序
排序完數(shù)組a變?yōu)?br>
用向上調(diào)整算法建堆的升序的堆排序代碼如下：
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
//交換結(jié)點的函數(shù)
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向上調(diào)整算法(大堆)
void AdjustUp(HPDataType* a, int child)
{
//找出雙親的下標
int parent = (child - 1) / 2;
while (child>0)
{
//孩子結(jié)點比雙親大則交換
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下調(diào)整算法(大堆)
void AdjustDown(HPDataType* a, int n, int parent)
{
//先默認左孩子是較大的
int child = parent * 2 + 1;
while (child < n)
{
//找出左右孩子中較大的
if (child + 1 < n && a[child + 1] > a[child])
{
child++;
}
//孩子節(jié)點更小則交換
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//排序
void HeapSort(int* a, int n)
{
//向上調(diào)整建堆
for (int i = 1; i < n; i++)
{
AdjustUp(a, i);
}
//最尾端數(shù)據(jù)下標為總數(shù)減一
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
//對剩余元素進行向下調(diào)整
AdjustDown(a, end, 0);
end--;
}
}
建堆的：
空間復(fù)雜度：O(1)
平均時間復(fù)雜度：O(nlogn)
3、向下調(diào)整建堆排序
向下調(diào)整建堆排序與向上調(diào)整建堆排序不同的地方就在于建堆時用的算法不同，建好堆之后的后續(xù)操作都是相同的。
還是對上面那個案例，我們用向下調(diào)整算法建堆
向下調(diào)整算法前提條件：左右子樹必須是堆，才能調(diào)整
對于這個完全二叉樹來說，它的倒數(shù)第一個非葉子節(jié)點2的左子樹為4，沒有右子樹，可以用向下調(diào)整，再上一個節(jié)點6的左右子樹是單個節(jié)點也可以看作堆，所有我們就可以從倒數(shù)第一個非葉子節(jié)點也就是最后一個節(jié)點的父親開始向下調(diào)整：
利用向下調(diào)整建好堆之后的后續(xù)操作與向上調(diào)整建好堆之后的操作一樣，這里就不再演示
用向下調(diào)整算法建堆的升序的堆排序代碼更改如下：
void HeapSort(int* a, int n)
{
向上調(diào)整建堆
//for (int i = 1; i < n; i++)
//{
// AdjustUp(a, i);
//}
//
//向下調(diào)整建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
//最尾端數(shù)據(jù)下標為總數(shù)減一
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
//對剩余元素進行向下調(diào)整
AdjustDown(a, end, 0);
end--;
}
}
利用向下調(diào)整建堆的堆排序時間復(fù)雜度為：O(n)，比利用向上調(diào)整建堆更優(yōu)
七、歸并排序
如需更詳細步驟可見：歸并排序
1、定義
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
2、思想及圖解
歸并排序算法有兩個基本的操作，一個是分解，另一個是合并。分解是把原數(shù)組劃分成兩個子數(shù)組的過程，合并可以將兩個有序數(shù)組合并成一個更大的有序數(shù)組。
將待排序的線性表不斷地切分成若干個子表，直到每個子表只包含一個元素，這時，可以認為只包含一個元素的子表是有序表。將子表兩兩合并，每合并一次，就會產(chǎn)生一個新的且更長的有序表，重復(fù)這一步驟，直到最后只剩下一個子表，這個子表就是排好序的線性表。
3、代碼
1）遞歸實現(xiàn)
//歸并排序
void _MergeSort(int* a, int* tmp, int begin, int end)
{
//遞歸結(jié)束條件
if (begin >= end)
{
return;
}
int mid = (begin + end) / 2;
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid+1, end);
// 歸并到tmp數(shù)據(jù)組，再拷貝回去
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int index = begin;
//begin小于end說明還有兩部分都還有數(shù)據(jù)
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
//由于右邊沒有數(shù)據(jù)跳出的上一個循環(huán)，將左邊剩下的數(shù)放入tmp數(shù)組對應(yīng)位置
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
//由于左邊沒有數(shù)據(jù)跳出的上一個循環(huán)，將右邊剩下的數(shù)放入tmp數(shù)組對應(yīng)位置
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;
}
_MergeSort(a, tmp, 0, n - 1);
free(tmp);
}
2）非遞歸實現(xiàn)
非遞歸實現(xiàn)時當(dāng)gap的值不同時有許多數(shù)組的數(shù)據(jù)個數(shù)不適合當(dāng)前gap，訪問就會越界，比如9個值時當(dāng)gap==1就會訪問到下標為9的下標越界，所以要在代碼中加入解決措施。當(dāng)?shù)谝唤M右邊界越界，第二組左邊界也一定越界了，所以可分為第二組左邊界越界和第二組右邊界越界兩種情況處理。
//非遞歸歸并
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)
{
// 歸并到tmp數(shù)據(jù)組，再拷貝回去
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
// 如果第二組不存在，這一組不用歸并了
if (begin2 >= n)
{
break;
}
// 如果第二組的右邊界越界，修正一下
if (end2 >= n)
{
end2 = n - 1;
}
int index = i;
//begin小于end說明還有兩部分都還有數(shù)據(jù)
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
//由于右邊沒有數(shù)據(jù)跳出的上一個循環(huán)，將左邊剩下的數(shù)放入tmp數(shù)組對應(yīng)位置
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
//由于左邊沒有數(shù)據(jù)跳出的上一個循環(huán)，將右邊剩下的數(shù)放入tmp數(shù)組對應(yīng)位置
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
// 拷貝回原數(shù)組
memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));
}
gap *= 2;
}
free(tmp);
}
時間復(fù)雜度：O(N*logN)
空間復(fù)雜度：O(N)
穩(wěn)定性：穩(wěn)定
八、計數(shù)排序
1、原理
計數(shù)排序又稱為鴿巢原理，是對哈希直接定址法的變形應(yīng)用。
操作步驟為：
- 統(tǒng)計相同元素出現(xiàn)次數(shù)
- 根據(jù)統(tǒng)計的結(jié)果將序列回收到原來的序列中
2、圖解
首先找出數(shù)組a的最大值和最小值，計算出range
創(chuàng)建一個range大小的數(shù)組count，在下標為i的位置存儲原數(shù)組中大小為i+min的數(shù)的個數(shù)
然后按順序?qū)?shù)據(jù)放入原數(shù)組中
按照這樣便可以將所有數(shù)據(jù)排好序
3、代碼
//計數(shù)排序
void CountSort(int* a, int n)
{
int min = a[0];
int max = a[0];
//找出最大值和最小值
for (int i = 1; i < n; i++)
{
if (a[i] < min)
{
min = a[i];
}
if (a[i] > max)
{
max = a[i];
}
}
//確定建立數(shù)組的長度
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
//printf("range:%d\n", range);
if (count == NULL)
{
perror("malloc fail");
return;
}
//初始化數(shù)組count
memset(count, 0, sizeof(int) * range);
//計數(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++] = min + i;
}
}
}
計數(shù)排序在數(shù)據(jù)范圍集中時，效率很高，但是適用范圍及場景有限，僅適用于整型排序。
時間復(fù)雜度：O(N+range)
空間復(fù)雜度：O(range)
穩(wěn)定性：穩(wěn)定
九、總結(jié)
排序：所謂排序，就是使一串記錄，按照其中的某個或某些關(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ù)的排序。
文章來源：http://www.zghlxwxcb.cn/news/detail-801658.html
時空復(fù)雜度及穩(wěn)定性：文章來源地址http://www.zghlxwxcb.cn/news/detail-801658.html
| 排序算法 | 時間復(fù)雜度 | 空間復(fù)雜度 | 穩(wěn)定性 |
|---|---|---|---|
| 直接插入排序 | O(N2) | O(1) | 穩(wěn)定 |
| 希爾排序 | O(N1.3) | O(1) | 不穩(wěn)定 |
| 選擇排序 | O(N2) | O(1) | 不穩(wěn)定 |
| 堆排序 | O(N*logN) | O(1) | 不穩(wěn)定 |
| 冒泡排序 | O(N2) | O(1) | 穩(wěn)定 |
| 快速排序 | O(N*logN) | O(logN) | 不穩(wěn)定 |
| 歸并排序 | O(N*logN) | O(N) | 穩(wěn)定 |
| 計數(shù)排序 | O(MAX(N,范圍)) | O(范圍) | 穩(wěn)定 |
到了這里，關(guān)于【C語言】八大排序算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
