1.排序的概念
1.1排序的概念
- 排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
- 穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
- 內部排序：數(shù)據(jù)元素全部放在內存中的排序。
- 外部排序：數(shù)據(jù)元素太多不能同時放在內存中，根據(jù)排序過程的要求不能在內外存之間移動數(shù)據(jù)的排序。
2.常見排序算法的實現(xiàn)
2.1 插入排序
直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。
2.1.1直接插入排序
當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經排好序，此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移。
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];//待排序數(shù)據(jù)
while (end >= 0)
{
if (tmp < a[end])//將待排序數(shù)據(jù)前的數(shù)據(jù)依次與其比較
{
a[end + 1] = a[end];//數(shù)據(jù)后移
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;//將待排序數(shù)據(jù)放在合適位置
}
}
直接插入排序的特性總結：
- 元素集合越接近有序，直接插入排序算法的時間效率越高
- 時間復雜度：O(N^2)
- 空間復雜度：O(1)
- 穩(wěn)定性：穩(wěn)定
2.1.2希爾排序
-
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數(shù)作為gap，把待排序數(shù)據(jù)分成gap組，所有距離為gap的數(shù)據(jù)分在同一組內，并對每一組內的記錄進行排序。然后重新取gap，重復上述分組和排序的工作。當?shù)竭_gap==1時，所有記錄在統(tǒng)一組已內排好序。
-
希爾排序是對直接插入排序的優(yōu)化。
當gap > 1時都是預排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經接近有序的了，在使用直接插入排序，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。 -
在初始時，gap通常選擇 n/2 或 n/3+1(n為數(shù)據(jù)的個數(shù))
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
//gap = gap / 3 + 1;
gap = gap / 2;
//gap趟
for (int j = 0; j < gap; j++)
{
//一趟的
for (int i = j; i < n - gap; i+=gap)//每次跳躍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;
}
}
}
}
上面的代碼可以進行優(yōu)化，不需要單獨排每一趟，直接可將gap趟一次排。
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
//gap = gap / 3 + 1;
gap = gap / 2;
//gap趟一起排
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];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
希爾排序的特性總結：
- 時間復雜度：O(N^1.3)
- 空間復雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
2.2選擇排序
每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完 。
2.2.1直接選擇排序:
在元素集合array[i]–array[n-1]中選擇關鍵碼最大(小)的數(shù)據(jù)元素若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重復上述步驟，直到集合剩余1個元素。
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void SelectSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int m = i;//記錄當前數(shù)的下標
for (int j = i + 1; j < n; j++)
{
if (a[j] < a[m])//將當前數(shù)與其后的數(shù)對比
{
m = j;//記錄較小值的下標
}
}
//較小值不是當前數(shù)，交換
if (m != i)
{
Swap(&a[i], &a[m]);
}
}
}
優(yōu)化：一趟遍歷找出最大與最小值。
void SelectSort(int* a, int n)
{
int left = 0;
int right = n - 1;
while(left < right)
{
int max = left;
int min = left;
for (int i = left; i <= right; i++)
{
//找最大值
if (a[i] > a[max])
max = i;
//找最小值
if (a[i] < a[min])
min = i;
}
Swap(&a[min], &a[left]);
//若最大值在最左側，其會被換到最小值位置
if (max == left)
{
max = min;
}
Swap(&a[max], &a[right]);
left++;
right--;
}
}
選擇排序的特性總結：
- 直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用
- 時間復雜度：O(N^2)
- 空間復雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
2.2.2堆排序
堆排序在前面已經寫過，點擊鏈接跳轉至堆排序
排序的特性總結：
- 堆排序使用堆來選數(shù)，效率就高了很多。
- 時間復雜度：O(N*logN)
- 空間復雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
2.3交換排序
- 基本思想：所謂交換，就是根據(jù)序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置。
- 交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。
2.3.1冒泡排序
冒泡排序相信大家都非常熟悉了，直接上代碼吧。
void BubbleSort(int* a, int n)
{
//進行多少趟比較
for (int i = 0; i < n - 1; i++)
{
//每趟比較的次數(shù)
for (int j = 0; j < n - 1 - i; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
}
}
Print(a, n);
}
}
冒泡排序的特性總結：
- 冒泡排序是一種非常容易理解的排序
- 時間復雜度：O(N^2)
- 空間復雜度：O(1)
- 穩(wěn)定性：穩(wěn)定
2.3.2快速排序
Hoare法
快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。
如圖所示：
right從右往左找小于key的；left從左往右找大于key的，然后二者交換。繼續(xù)找，直到二者相遇；相遇以后，需要和key位置數(shù)交換，此時key位置的數(shù)就處在了排序完成后應該在的位置。
然后再對key位置左邊與右邊進行上述相同的操作即可完成排序。
為什么二者相遇的位置一定比key小呢？
此處就是該算法的精髓，因為是right先走，right停下來的位置一定比key小，或者right到了key位置。、
void QuickSort(int* a, int left,int right)
{
//若區(qū)間只有一個數(shù)，則已經有序
if (left >= right)
return;
int begin = left;
int end = right;
int key = left;//基準值
while (left < right)
{
//從右往左，找比key位置小的，不小就左移
while (left < right && a[right] >= a[key])
{
right--;
}
//從左往右，找比key位置大的，不大就右移
while (left < right && a[left] <= a[key])
{
left++;
}
//left位置比key大，right位置比key小。交換
Swap(&a[left], &a[right]);
}
//left與right相遇，那就與key交換
Swap(&a[key], &a[right]);
key = left;
//遞歸左右區(qū)間
//[begin,key-1] key [key+1,end]
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
我們都知道快排很快，它的時間復雜度為O(N*logN)，但真的是這樣嗎？
思考：若數(shù)據(jù)有序或已經接近有序，該算法還快嗎？
如果是這種情況，那么這個基準值每次都會選到最小的值，此時它的時間復雜度就是N^2。那有什么解決辦法嗎？
使用隨機取key法或三數(shù)取中法。
- 隨機數(shù)選key就是每次選的key都不一定，但有時可以避免最壞情況
int begin = left;
int end = right;
//使隨機數(shù)的范圍再[left,rihgt]中
int randk = rand() % (right - left);
randk += left;
//為了我們后面代碼的邏輯不改變，將randk位置與left位置交換
Swap(&a[left], &a[randk]);
int key = left;//基準值
- 三數(shù)取中法
這里的取中并不是取中間的數(shù)，而是三個數(shù)中，位于中間大小的數(shù)。
int GetMid(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[mid] < a[right])
{
if (a[mid] > a[left])
{
//left < mid < right
return mid;
}
else if (a[left] < a[right])
{
//mid < left < right
return left;
}
else
{ //left < right < mid
return right;
}
}
else//a[mid] > a[right]
{
if (a[mid] < a[left])
{
//right < mid < left
return mid;
}
else if (a[left] > a[right])
{
//right < left < mid
return left;
}
else
{
//left < right < mid
return right;
}
}
}
void QuickSort(int* a, int left,int right)
{
//若區(qū)間只有一個數(shù)，則已經有序
if (left >= right)
return;
int begin = left;
int end = right;
使隨機數(shù)的范圍再[left,rihgt]中
//int randk = rand() % (right - left);
//randk += left;
為了我們后面代碼的邏輯不改變，將randk位置與left位置交換
//Swap(&a[left], &a[randk]);
int midk = GetMid(a, left, right);
Swap(&a[left], &a[midk]);
int key = left;//基準值
while (left < right)
{
//從右往左，找比key位置小的，不小就左移
while (left < right && a[right] >= a[key])
{
right--;
}
//從左往右，找比key位置大的，不大就右移
while (left < right && a[left] <= a[key])
{
left++;
}
//left位置比key大，right位置比key小。交換
Swap(&a[left], &a[right]);
}
//left與right相遇，那就與key交換
Swap(&a[key], &a[right]);
key = left;
//遞歸左右區(qū)間
//[begin,key-1] key [key+1,end]
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
- 小區(qū)間優(yōu)化
當快排進行到數(shù)據(jù)元素比較少的時候，使用快速排序走遞歸的消耗是比較大的，最后一層的遞歸占整個遞歸的80%-%90。是不值當?shù)?，如下圖這種情況：
對于這種情況，我們給出小區(qū)間優(yōu)化的方式。即當遞歸進入待排序數(shù)字只剩下10個左右時，直接使用插入排序。
//小區(qū)間優(yōu)化
if (right - left + 1 < 10)
{
//進行插入排序
InsertSort(a + left, right - left - 1);
}
else
{
//繼續(xù)進行遞歸
}
前后指針法
先看一下動圖演示
此方法與第一種方法不同之處在于，它不是一左一右了。使用前后指針，cur指針為前指針，它找比key小的，找到以后，先讓prev++，然后二者在交換，最后自己在++；當cur超出范圍時，prev位置小于key，將prev與key交換，本輪排序結束。
void QuickSort2(int* a, int left, int right)
{
if (left >= right)
return;
int prev = left;
int cur = prev + 1;
int key = left;
//當前值比key小，先++prev,然后交換
while (cur <= right)
{
if (a[cur] < a[key])
{
++prev;
Swap(&a[prev], &a[cur]);
}
cur++;
}
//使key位于正確位置
Swap(&a[key], &a[prev]);
key = prev;
//遞歸左右區(qū)間
QuickSort2(a, left, key - 1);
QuickSort2(a, key + 1, right);
}
為了避免自己與自己進行無意義的交換，代碼也可以寫成這樣：
void QuickSort2(int* a, int left, int right)
{
if (left >= right)
return;
int prev = left;
int cur = prev + 1;
int key = left;
//當前值比key小，先++prev,然后交換
/*while (cur <= right)
{
if (a[cur] < a[key])
{
++prev;
Swap(&a[prev], &a[cur]);
}
cur++;
}*/
while (cur <= right)
{
if (a[cur] < a[key] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
//使key位于正確位置
Swap(&a[key], &a[prev]);
key = prev;
//遞歸左右區(qū)間
QuickSort2(a, left, key - 1);
QuickSort2(a, key + 1, right);
}
挖坑法
挖坑法與Hoare法類似
將步驟拆解下來就是下面這樣
void QuickSort3(int* a, int left, int right)
{
if (left >= right)
return;
int begin = left;
int end = right;
int key = a[left];
int pos = left;//選定坑位
while (left < right)
{
while (left < right && a[right]>= key)
{
right--;
}
//從右邊找，找到了比key小的，數(shù)據(jù)變化，坑位變化
a[pos] = a[right];
pos = right;//換坑
while (left < right && a[left] <= key)
{
left++;
}
//從左邊找，找到了比key大的，數(shù)據(jù)變化，坑位變化
a[pos] = a[left];
pos = left;
}
//此時left與right相遇
a[pos] = key;
//[begin,pos-1] pos [pos+1,end]
QuickSort3(a, begin, pos - 1);
QuickSort3(a, pos + 1, end);
}
非遞歸版本
如果待排序的數(shù)據(jù)量非常大時，會遞歸很多次，可能會導致棧溢出，所以非遞歸版本也是我們必須掌握的。
其實非遞歸版本也是利用棧后進先出的特性，模擬出的遞歸的效果。
void QuickSortNonR(int* a, int left, int right)
{
Stack st;
StackInit(&st);
//左右區(qū)間先入棧
StackPush(&st, right);
StackPush(&st, left);
//棧不為空，就取棧頂元素排序
while (!StackEmpty(&st))
{
int begin = StackTopElement(&st);
StackPop(&st);
int end = StackTopElement(&st);
StackPop(&st);
//前后指針法，進行單趟排
int prev = begin;
int cur = prev + 1;
int key = begin;
while (cur <= end)
{
if (a[cur] < a[key] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
//使key位于正確位置
Swap(&a[key], &a[prev]);
key = prev;
//[begin,key-1] key [key+1,end]
//繼續(xù)入棧,先入右，再入左
if (key + 1 < end)
{
StackPush(&st, end);
StackPush(&st, key + 1);
}
if (key - 1 > begin)
{
StackPush(&st, key - 1);
StackPush(&st, begin);
}
}
StackDestroy(&st);
}
快速排序的特性總結：
- 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
- 時間復雜度：O(N*logN
- 空間復雜度：O(logN)
- 穩(wěn)定性：不穩(wěn)定
2.4歸并排序
基本思想：
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
歸并排序算法有兩個基本的操作，一個是分，也就是把原數(shù)組劃分成兩個子數(shù)組的過程。另一個是治，它將兩個有序數(shù)組合并成一個更大的有序數(shù)組。
- 將待排序的線性表不斷地切分成若干個子表，直到每個子表只包含一個元素，這時，可以認為只包含一個元素的子表是有序表。
- 將子表兩兩合并，每合并一次，就會產生一個新的且更長的有序表，重復這一步驟，直到最后只剩下一個子表，這個子表就是排好序的線性表
分的過程就是將數(shù)據(jù)拆到只有一個數(shù)據(jù)時，此時該數(shù)據(jù)自身有序。
什么時候就拆好了呢？
當數(shù)據(jù)的左右邊界相等時，就只剩下一個數(shù)據(jù)，此時可以合并了，如下圖：
那它的合并又是怎么合的呢？難道在原數(shù)組上合并嗎？
肯定不是這樣的，如果在原數(shù)組上合并的話，那數(shù)據(jù)就亂套了。
因此，我們需要借助一個臨時數(shù)組來保存數(shù)據(jù)，待數(shù)據(jù)合并后，在將臨時數(shù)組中的數(shù)據(jù)拷回到原數(shù)組中。
動圖演示：
遞歸版本
#include<string.h>
void _MergeSort(int* a, int begin, int end, int* tmp)
{
//僅剩下一個數(shù)據(jù)，自身有序，不在進行遞歸
if (begin == end)
return;
int mid = (begin + end) / 2;
//分的過程：遞歸左右區(qū)間，使左右區(qū)間有序
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid+1, end, tmp);
//兩區(qū)間已經有序，進行合并
int left1 = begin, right1 = mid;
int left2 = mid + 1, right2 = end;
int tmpi = begin;//往tmp數(shù)組存放位置的下標
//兩區(qū)間均未遍歷完
while (left1 <= right1 && left2 <= right2)
{
//按序存放進tmp數(shù)組
if (a[left1] < a[left2])
{
tmp[tmpi++] = a[left1++];
}
else
{
tmp[tmpi++] = a[left2++];
}
}
//有一個遍歷完了
while (left1 <= right1)
{
tmp[tmpi++] = a[left1++];
}
while (left2 <= right2)
{
tmp[tmpi++] = a[left2++];
}
//tmp數(shù)組中的數(shù)據(jù)已經有序，拷貝回原數(shù)組
//注意數(shù)據(jù)拷貝元素的位置
memcpy(a + begin, tmp + begin, sizeof(int) * (tmpi - begin));
}
void MergeSort(int* a, int n)
{
//開辟臨時數(shù)組
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}
非遞歸版本
該方法的思想和遞歸相似。
void MergeSortNonR(int* a, int n)
{
//開辟臨時數(shù)組
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1; //最開始為 1個一組,每組均有序
while (gap < n)
{
//gap個分為一組,每次分兩組，然后取小進行尾插
for (int i = 0; i < n; i += 2*gap)
{
int left1 = i, right1 = left1 + gap - 1;
int left2 = left1 + gap, right2 = left2 + gap - 1;
int tmpi = i;
while (left1 <= right1 && left2 <= right2)
{
//按序存放進tmp數(shù)組
if (a[left1] < a[left2])
{
tmp[tmpi++] = a[left1++];
}
else
{
tmp[tmpi++] = a[left2++];
}
}
//有一個遍歷完了
while (left1 <= right1)
{
tmp[tmpi++] = a[left1++];
}
while (left2 <= right2)
{
tmp[tmpi++] = a[left2++];
}
//將臨時數(shù)組拷回原數(shù)組
memcpy(a + i, tmp + i, sizeof(int) * tmpi - i);
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
運行上述代碼，我們會發(fā)現(xiàn)會出現(xiàn)越界問題
我們分析一下：
- 首先，我們的left1=i，i<n，所以left1不可能越界
- right1可能越界，如果right1越界那說明數(shù)組已經有序了，不需要進行排序
- left2可能越界，如果right2越界那說明數(shù)組也已經有序了，不需要進行排序
- right2也可能越界，當right2越界時，[left2,未越界] right2，那么我們需要對未越界的部分進行排序。
if (right1 >= n || left1 >= n)
{
break;
}
if (right2 >= n)
{
right2 = n - 1;
}
到此，我們的歸并排序就算完美了。
void MergeSortNonR(int* a, int n)
{
//開辟臨時數(shù)組
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1; //最開始為1個一組,每組均有序
while (gap < n)
{
//gap個分為一組,每次分兩組
for (int i = 0; i < n; i += 2*gap)
{
int left1 = i, right1 = left1 + gap - 1;
int left2 = left1 + gap, right2 = left2 + gap - 1;
//printf("[%d,%d][%d,%d] ", left1, right1, left2, right2);
//無需再排
if (right1 >= n || left1 >= n)
{
break;
}
//部分要排
if (right2 >= n)
{
right2 = n - 1;
}
int tmpi = i;
while (left1 <= right1 && left2 <= right2)
{
//按序存放進tmp數(shù)組
if (a[left1] < a[left2])
{
tmp[tmpi++] = a[left1++];
}
else
{
tmp[tmpi++] = a[left2++];
}
}
//有一個遍歷完了
while (left1 <= right1)
{
tmp[tmpi++] = a[left1++];
}
while (left2 <= right2)
{
tmp[tmpi++] = a[left2++];
}
//將臨時數(shù)組拷回原數(shù)組
memcpy(a + i, tmp + i, sizeof(int) * (tmpi - i));
}
gap *= 2;
//printf("\n");
}
free(tmp);
tmp = NULL;
}
歸并排序的特性總結：
- 歸并的缺點在于需要O(N)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
- 時間復雜度：O(N*logN)
- 空間復雜度：O(N)
- 穩(wěn)定性：穩(wěn)定
2.5計數(shù)排序
計數(shù)排序屬于非比較排序，那什么較非比較排序呢？–排序的關鍵邏輯不是比較出來的。
那具體是如何實現(xiàn)的呢？
- 統(tǒng)計相同元素出現(xiàn)次數(shù)
- 根據(jù)統(tǒng)計的結果將序列回收到原來的序列中
動圖演示：
從圖中我們可以看出，它是將數(shù)據(jù)的個數(shù)收集到一個臨時數(shù)組中，最后根據(jù)臨時數(shù)組的內容有序放回到原數(shù)組中。
但我們這個臨時數(shù)組開多大呢？和原數(shù)組一樣大嗎？那未免有點太浪費了。
我們只需要找出數(shù)據(jù)中的最大與最小值，數(shù)組大小開最大-最小+1就夠了。
例如：假設數(shù)組元素大小為100-200之間的數(shù)據(jù)，那就只需要開100+1個空間。 由于數(shù)組下標是從0開始的，而我最小的數(shù)據(jù)是100，那101就越界了，所以我們需要將待排序數(shù)據(jù)減去所有數(shù)組中的最小值再放進臨時數(shù)組中。
void CountSort(int* a, int n)
{
int max = a[0];
int min = a[0];
for (int i = 0; i < n; i++)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
//所開數(shù)組的大小
int range = max - min + 1;
int* tmp = (int*)calloc(range, sizeof(int));
if (tmp == NULL)
{
perror("calloc fail");
return;
}
//統(tǒng)計各數(shù)據(jù)的個數(shù)
for (int i = 0; i < n; i++)
{
tmp[a[i]-min]++;
}
int j = 0;
for (int i = 0; i < range; i++)
{
//當前數(shù)組元素不為0，還有為排序元素
while (tmp[i]--)
{
a[j++] = i + min;
}
}
}
計數(shù)排序的特性總結：
- 計數(shù)排序在數(shù)據(jù)范圍集中時，效率很高，但是適用范圍及場景有限。
- 時間復雜度：O(MAX(N,范圍))
- 空間復雜度：O(范圍)
- 穩(wěn)定性：穩(wěn)定
3.排序的比較
| 排序方法 | 平均情況 | 最好情況 | 最壞情況 | 輔助空間 | 穩(wěn)定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n)（有序） | O(n2) | O(1) | 穩(wěn)定 |
| 簡單選擇排序 | O(n2) | O(2) | O(n2) | O(1) | 不穩(wěn)定 |
| 直接插入排序 | O(n2) | O(n)（有序） | O(n2) | O(1) | 穩(wěn)定 |
| 希爾排序 | O(nlogn)~O(n2) | O(n1.3) | O(n2) | O(1) | 不穩(wěn)定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩(wěn)定 |
| 歸并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 穩(wěn)定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(logn)~O(n)（遞歸） | 不穩(wěn)定 |
| 計數(shù)排序 | O(Max(n,范圍)) | O(Min(n,范圍)) | O(Max(n,范圍)) | O(范圍) | 不穩(wěn)定 |
穩(wěn)定性：
若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。文章來源：http://www.zghlxwxcb.cn/news/detail-845525.html
穩(wěn)定的都好理解，不穩(wěn)定的如下：
文章來源地址http://www.zghlxwxcb.cn/news/detail-845525.html
到了這里，關于【八大排序】一篇文章搞定所有排序的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
