概述
排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序，這里八大排序就是內(nèi)部排序，指直接插入，希爾，選擇，堆排，冒泡，快排，歸并，計數(shù)。
下面讓我們來共同學(xué)習(xí)這八大排序吧！??????
什么是外部排序：
外排序是數(shù)據(jù)量較大,內(nèi)存放不下,數(shù)據(jù)放到外部磁盤空間,一般使用歸并排序進行外排序
假設(shè)內(nèi)存為512m,給10億個數(shù)據(jù),然后內(nèi)存每次讀取512m的數(shù)據(jù),排序完成后返回給磁盤,然后重復(fù)這個過程,直到拍完,然后外部的小文件,再經(jīng)過歸并,即可得到一個有序的數(shù)據(jù).????????
目錄
概述
?一、插入排序
1、直接插入排序
2、希爾排序?
二、選擇排序
1、直接選擇排序
2、堆排序
?
?三、交換排序
1、冒泡排序
2、快速排序
2.1?hoare版本
2.2?挖坑法
2.3?前后指針法
2.4?快排非遞歸版
四、歸并排序
1、歸并排序遞歸版
2、遞歸排序非遞歸版
五、計數(shù)排序 -?非比較排序
六、對排序的分析總結(jié)
什么是排序的穩(wěn)定性：?
排序算法復(fù)雜度及穩(wěn)定性總結(jié)：
?一、插入排序
1、直接插入排序
基本思想：
把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中（我們假設(shè)有序），直到所有的記錄插入完為止，得到一個新的有序序列。就像是我們玩撲克牌時按順序大小整理好牌的過程
動圖展示 ：
實現(xiàn)代碼：?
void InsertSort(int* arr, int n)
{
//我們默認序列有序，從一個數(shù)據(jù)開始，即只有一個數(shù)據(jù)有序
for (int i = 0; i < n - 1; i++) // 最后一個插入數(shù)據(jù)下標為n-1，此次end下標為n-2
{
int end = i; //end標記當(dāng)前有序序列的最后一個位置下標
int tmp = arr[end + 1];// 要插入的數(shù)據(jù)的位置為end后面
while (end >= 0) //利用end來進行單趟遍歷排序
{
//升序
if (arr[end] > tmp) //若原數(shù)據(jù)比插入數(shù)據(jù)大，則后移一位
{
arr[end + 1] = arr[end];
end--; //向前遍歷，進行數(shù)據(jù)排序
}
else //原數(shù)據(jù)小于插入數(shù)據(jù)，直接break
{
break;
}
}
arr[end + 1] = tmp;
}
}相關(guān)分析 ：
對于插入排序：
時間復(fù)雜度
- 最壞：逆序? （計算類似等差數(shù)列）? --O(N^2)
- 最好：順序? ?（數(shù)據(jù)有序）? ? ? ?? ? ? ? ---O(N)
待排序元素集合越接近有序，直接插入排序算法的時間效率越高
2、希爾排序?
?希爾排序是1959 年由D.L.Shell 提出來的，相對直接插入排序有較大的改進。希爾排序又叫縮小增量排序.。希爾排序是對直接插入排序的優(yōu)化。
基本思想：?
- 希爾排序 =?預(yù)排序（分組插入排序）?+?直接插入排序（最后一次為整體排序）
- 我們先選定一個整數(shù)gap，間隔為Gap的數(shù)據(jù)為一組,然后對這組數(shù)據(jù)進行排序（預(yù)排序）,再分組,再排,直到數(shù)組被分完.
- 將Gap減小,繼續(xù)分組,排序.
- 最后Gap設(shè)為1,此時數(shù)據(jù)基本有序，即進行直接插入排序,得到有序數(shù)組
動圖展示：?
?代碼實現(xiàn)：
void ShellSort(int* arr, int n)
{
//多組預(yù)排,插排
int gap = n;
while (gap > 1) //當(dāng)gap為1時，最后一次為直接插入排序，循環(huán)結(jié)束
{
gap = gap / 3 + 1; //除3能保證最后一次分組 gap == 1，即進行直接插入排序
for (int i = 0; i < n - gap; ++i) //++i實現(xiàn)gap組并排，減少循環(huán)調(diào)用
{
int end = i; //end 為最后一個有效數(shù)據(jù)下標
int tmp = arr[end + gap];
while (end>=0) //希爾的單趟排序?qū)崿F(xiàn)
{
if (arr[end] > tmp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}?相關(guān)分析：
- 希爾排序?qū)χ苯硬迦肱判虻膬?yōu)化在于：優(yōu)化了直接插入排序?qū)δ嫘驍?shù)據(jù)排序效率很差的缺點。我們將數(shù)據(jù)進行了一個gap分組，然后進行組預(yù)排序，這樣下來數(shù)據(jù)會越來越接近有序，等到最后一次排序的時候，我們無需進行大量的數(shù)據(jù)遍歷，只需遍歷個別不滿足升序的數(shù)據(jù)即可。這樣希爾排序效率就會比直接插入排序高很多。
- 對于希爾排序的時間復(fù)雜度：計算是不好計算的，需要進行數(shù)學(xué)推導(dǎo)，推導(dǎo)出來平均時間復(fù)雜度： O(N^1.3—N^2）
二、選擇排序
1、直接選擇排序
基本思想：
每次將數(shù)組遍歷一遍，在數(shù)組[0,n]中選取最小（最大）的數(shù),存放在序列的起始（或者末尾）位置，在[1,n-1]再次遍歷選取,交換,縮減,直到全部待排序的數(shù)據(jù)元素排完
優(yōu)化版：每次遍歷待排序數(shù)據(jù)找出最大和最小的數(shù)據(jù)，分別排列到序列起始和末尾
動圖展示：?
?代碼實現(xiàn)：
void Swap(int* p1, int* p2)
{
int* tmp = *p1;
*p1 = *p2;
*p2 = *tmp;
}
//一般版
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin<end)
{
int min = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] < a[min]) //遍歷最小數(shù)據(jù)并記錄下標
min = i;
}
Swap(&a[begin], &a[min]);
begin++; //縮小范圍
}
}
//優(yōu)化版
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int max = begin, min = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] > a[max])
max = i;
if (a[i] < a[min])
min = i;
}
if (begin == max) //若最大數(shù)據(jù)在begin位置，與begin下標重合，則需進行修正
max = min;
Swap(&a[begin], &a[min]); //進行交換
Swap(&a[end], &a[max]);
begin++;
end--; //接著縮小遍歷范圍
}
}相關(guān)分析：
直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用。其穩(wěn)定性也較差
2、堆排序
基本思想：?
學(xué)過二叉樹我們知道堆排序是指利用堆（數(shù)據(jù)結(jié)構(gòu)）進行選擇數(shù)據(jù)的一種排序算法。在已經(jīng)建好堆的情況下，升序建大堆，降序建小堆，通過堆來選擇數(shù)據(jù),向下調(diào)整算法,得到小數(shù)(大數(shù)),然后再與堆底數(shù)據(jù)進行交換。每重新調(diào)整堆時，傳給向下調(diào)整算法的數(shù)組個數(shù)要減1，數(shù)組的最后一個元素已經(jīng)變得有序了，因此不需要我們調(diào)整了。
圖示（大堆排序）：?
?
?代碼實現(xiàn)：
void Adjustdown(int* a, int n, int parent)
{
int child = parent * 2 + 1; //首先假設(shè)最大孩子為左孩子
while (child < n)
{
//找到數(shù)據(jù)大的子結(jié)點
if (child + 1 < n && a[child + 1] > a[child]) //可能父節(jié)點沒有右孩子
{
++child;
}
//父節(jié)點數(shù)據(jù)小于子節(jié)點就交換
if (a[parent] < a[child]) //大堆調(diào)整
{
Swap(&a[parent], &a[child]);
//更新下標
parent = child;
child = parent * 2 + 1;
}
else//否則直接break
break;
}
}
// 堆排序(升序)
void HeapSort(int* a, int n)
{
int i;
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
Adjustdown(a, n, i);
}
//交換調(diào)整
for (i = n - 1; i >= 0; i--)
{
Swap(&a[0], &a[i]);//與當(dāng)前堆尾數(shù)據(jù)交換
Adjustdown(a, i, 0);//對交換后堆頂數(shù)據(jù)進行向下調(diào)整
}
}相關(guān)分析：
- 堆排序使用堆來選數(shù)，效率就會高出很多
- 核心向下調(diào)整算法是實現(xiàn)排序的精髓，建堆同樣用到
?三、交換排序
1、冒泡排序
基本思想：
?每次遍歷待排序數(shù)組，對相鄰數(shù)據(jù)進行比較，將值較大的數(shù)據(jù)向序列尾部移動，值較小的數(shù)據(jù)向序列前部移動。
動圖展示：?
?代碼實現(xiàn)：
void Bubblesort(int* a, int n)
{
for (int i = 0; i < n; i++)//遍歷次數(shù)
{
for (int j = 0; j < n - i - 1; j++)//向后冒泡 ,控制邊界
{
if (a[j] > a[j + 1])//如果前一個值大于后一個值,交換.
{
swap(&a[j], &a[j + 1]);
}
}
}
}
//優(yōu)化
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; ++j)
{
int exchange = 0;
for (int i = 1; i < n-j; ++i)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
// 一趟冒泡過程中，沒有發(fā)生交換，說明已經(jīng)有序了，不需要再處理
if (exchange == 0)
{
break;
}
}
}相關(guān)分析：
我們可以做一個簡單的優(yōu)化，如果我們排序的某一趟每個元素都不用交換，則說明要排序的元素已經(jīng)有序，那么后面的排序就可以直接跳出循環(huán)了。
2、快速排序
2.1?hoare版本
基本思想：
我們將左邊值設(shè)為key,然后右邊right先走,找小的,比key小停下來,然后左邊left走找比key大,然后交換左邊右邊，繼續(xù)上述過程，直至left和right相遇，此時的值一定是比key小的值，我們再把key和這個相遇位置的值進行交換，此時key所在的位置，左邊的數(shù)據(jù)一定比key值小，右邊的數(shù)據(jù)一定比key值大，即key放到了合適的位置上。重復(fù)此過程進行遞歸，直至所有的元素都處在合適位置。
動圖展示：
?代碼實現(xiàn)：
int HoareSort(int* arr, int left, int right)
{
int key = left; //我們默認key為左邊值
while (left < right)
{
while (left < right && arr[right] >= arr[key]) //找小
{
right--;
}
while (left < right && arr[left] <= arr[key]) //找大
{
left++;
}
Swap(&arr[left], &arr[right]);
}
Swap(&arr[key], &arr[left]);
key = left;
return key;
}
void QuickSort(int* arr, int begin, int end) //快排hoare版
{
if (begin >= end)//遞歸結(jié)束條件
{
return;
}
int key = HoareSort(arr, begin, end);
QuickSort(arr, begin, key - 1); //遞歸key左邊數(shù)組排序
QuickSort(arr, key + 1, end); //遞歸key右邊數(shù)組排序
}
相關(guān)分析：
Hoare版本的快排需要注意的地方挺多的：
- 如果key后面的每個數(shù)都比key小或大的話，那left向后面找或right向前面找，會產(chǎn)生越界訪問的問題，所以我們選擇在if語句的判斷部分邏輯與&&保證left小于right，以免產(chǎn)生越界訪問的問題。
- ?在if語句的判斷部分，找的數(shù)據(jù)一定得比key小或大的。因為若相等會產(chǎn)生死循環(huán)。
對次的優(yōu)化：?
我們可以對key值的選取進行優(yōu)化，采用三數(shù)取中法讓我們選取的key數(shù)據(jù)在序列中的位置盡量靠中間，以提高遞歸的效率。同時，遞歸建立的棧幀數(shù)量會隨著遞歸深度的增加而增加，為了避免遞歸深度太深，造成棧溢出的問題。我們采用小區(qū)間優(yōu)化，當(dāng)遞歸區(qū)間的數(shù)據(jù)量較小的時候，采用直接插入法進行排序。
相關(guān)代碼：
//三數(shù)取中
int GetMidIndex(int *arr, int begin, int end)
{
int mid = (begin + end) / 2;
if (arr[begin] > arr[end])
{
if (arr[end] > arr[mid])
{
return end;
}
else if (arr[begin] < arr[mid])
{
return begin;
}
else
{
return mid;
}
}
else// arr[begin] < arr[end]
{
if (arr[mid] < arr[begin])
{
return begin;
}
else if (arr[end] > arr[mid])
{
return mid;
}
else
{
return end;
}
}
}
//對小區(qū)間優(yōu)化
void QuickSort(int* arr, int begin, int end)
{
if ((end - begin) < 1)//遞歸結(jié)束條件
{
return;
}
if ((end - begin + 1) < 15)
{
InsertSort(arr + begin, end - begin + 1);
}
else
{
int key = PartSort1(arr, begin, end);
QuickSort(arr, begin, key - 1);
QuickSort(arr, key + 1, end);
}
}
2.2?挖坑法
基本思想：
挖坑法對hoare的思想進行了優(yōu)化。我們設(shè)定key數(shù)組左邊第一個值為坑,右邊right找小,找到比key小的值填到坑位，right就成為新的坑位，然后左邊left找大,找到后填到坑位上,left此時更新為新的坑位,循環(huán)此過程，right接著找小，left找大，交換形成新的坑位，直至left和right相遇。最后把key放到坑里，即類似于hoare版本key應(yīng)處于的位置。
動圖展示：
代碼實現(xiàn)：?
int QuickSort2(int* arr, int left, int right) //快速排序挖坑法
{
int mid = GetMidIndex(arr, left, right); //三數(shù)取中
Swap(&arr[left], &arr[mid]);使中間值永遠在最左，便于決定誰先走
int hole = left; //對key值保存
int key = arr[left];//保存坑位下標
while (left < right)
{
while (left < right && arr[right] >= key) //右邊找小
{
--right;
}
arr[hole] = arr[right]; //填坑
hole = right;
while (left < right && arr[left] <= key) //左邊找大
{
++left;
}
arr[hole] = arr[left];//填坑
hole = left;
}
arr[hole] = key; //相遇時
return hole;
}
相關(guān)分析：
需要進行坑位的位置更新
2.3?前后指針法
基本思想：
我們定義兩個指針cur和prev，選取key值,cur去遍歷小于key的值,對prev++,交換cur與prev值,直至cur遍歷完整個數(shù)組，prev位置的值一定是比key值小的，即key應(yīng)處的正確位置
動圖展示：
?代碼實現(xiàn)：
int QuickSort3(int* arr, int left, int right) //前后指針版
{
int mid = GetMidIndex(arr, left, right);
Swap(&arr[left], &arr[mid]);
int key = left;
int prev = left, cur = left + 1; //初始化前后指針
while (cur <= right)
{
if (arr[cur] < arr[key] && ++prev != cur)//邏輯與防止交換同一個位置的元素
{
Swap(&arr[cur], &arr[++prev]);
}
cur++;
}
Swap(&arr[key], &arr[prev]);//遍歷結(jié)束將key值放在定位點
return prev;
}
相關(guān)分析：
++prev!=cur 是對防止同一位置元素進行交換的簡單優(yōu)化，實際中，前后指針法推薦掌握，簡單理解易于操控。
對前后指針法的優(yōu)化：
在數(shù)據(jù)量極大的情況下，會出現(xiàn)很多相同的數(shù)據(jù)，此時進行快排，會建立很多棧幀，造成遞歸深度太深，運行時間過長，對于那些相同的數(shù)據(jù)我們采用三指針法進行優(yōu)化
我們定義left，right，cur三個下標，利用cur對序列的遍歷，找出大于key，等于key，小于key的三種值，將他們交換到left和right下標位置，將等于key值的數(shù)據(jù)集中到數(shù)組區(qū)間中部，然后繼續(xù)遞歸剩余的左右區(qū)間，直至排序完成。
相關(guān)代碼：?
void _QuickSort3(int* arr, int begin, int end) //前后指針法優(yōu)化：三指針法
{
if (begin >= end)
{
return;
}
if ((end - begin + 1) < 15)
{
InsertSort(arr + begin, end - begin + 1);
}
else
{
int mid = GetMidIndex(arr, begin, end);
Swap(&arr[begin], &arr[mid]);
int key = arr[begin];
int left = begin, right = end, cur = begin + 1;
while (cur <= right)
{
if (arr[cur] < key)
{
Swap(&arr[left], &arr[cur]);
left++;
cur++;
}
else if (arr[cur] > key)
{
Swap(&arr[cur], &arr[right]);
right--;
}
else//arr[cur]==key時
{
cur++;
}
}
QuickSortPlus(arr, begin, left - 1);
QuickSortPlus(arr, right + 1, end);
}
}
2.4?快排非遞歸版
基本思想：
對于非遞歸版的實現(xiàn)，因為遞歸函數(shù)在內(nèi)存實際上是在棧中進行開辟函數(shù)棧幀，延用遞歸中的思想，這里我們采用數(shù)據(jù)結(jié)構(gòu)中的棧來模擬內(nèi)存中的棧，從而實現(xiàn)快排的非遞歸。
代碼實現(xiàn)：
void QuickSortNonR(int* arr, int begin, int end) // 快速排序 非遞歸實現(xiàn)
{
ST st; //首先構(gòu)建一個棧
StackInit(&st);
StackPush(&st, begin); //將左右區(qū)間入棧
StackPush(&st, end);
while (!StackEmpty(&st))
{
int right = StackTop(&st);
StackPop(&st);
int left = StackTop(&st);
StackPop(&st);
int key = QuickSort3(arr, left, right); //排序：利用上面的前后指針法進行排序
// [begin,key-1] [key+1,end]
if (key + 1 < right)//key+1==right說明區(qū)間只剩一個值時，則可以認為有序
{
StackPush(&st, key + 1);
StackPush(&st, right);
}
if (left < key - 1)
{
StackPush(&st, left);
StackPush(&st, key - 1);
}
}
StackDestroy(&st); //棧銷毀
}
四、歸并排序
1、歸并排序遞歸版
基本思想：
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。通過遞歸實現(xiàn)對小數(shù)組有序,再返回回來。
動圖展示:
?代碼實現(xiàn)：
void _MergeSort(int* arr, int begin, int end, int* tmp) //歸并排序
{
if (begin >= end) //只有一個元素或沒有元素為有序
{
return;
}
int mid = (begin + end) / 2;
_MergeSort(arr, begin, mid, tmp);
_MergeSort(arr, mid + 1, end, tmp);
//左區(qū)間和右區(qū)間有序后開始歸并
int i = begin;
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
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++];
}
memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));//拷貝回數(shù)組arr
}
void MergeSort(int* arr, int begin, int end)
{
int* tmp = (int*)malloc(sizeof(int) * (end - begin));//創(chuàng)建暫存數(shù)據(jù)數(shù)組，以保存歸并好的數(shù)據(jù)
_MergeSort(arr, begin, end - 1, tmp);
free(tmp);//釋放
tmp = NULL;
}
相關(guān)分析：
歸并的缺點在于需要O(N)的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
2、遞歸排序非遞歸版
基本思想：
因為遞歸實現(xiàn)過程就是分治,只不過非遞歸不用遞歸返回,我們可以不借助其他數(shù)據(jù)結(jié)構(gòu)，直接對序列進行歸并排序，這里主要采用循環(huán)：
void MergeSortNonR(int* a, int n) //歸并排序非遞歸版
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
int gap = 1;//定義數(shù)組歸并距離
//（初始gap為1即每個數(shù)組只有一個元素，此時每個數(shù)組都為有序數(shù)組）
while (gap < n)//歸并趟次
{
for (int i = 0; i < n; i += gap * 2)//分組歸并
{
//劃分區(qū)間
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
//判斷越界的情況
//這種情況不用考慮歸并（已經(jīng)有序）
if (end1 >= n || begin2 >= n)
{
break;
}
//這種情況需要歸并
if (end2 >= n)
{
end2 = n - 1;
}
//歸并
int p = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[p++] = a[begin1++];
}
else
{
tmp[p++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[p++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[p++] = a[begin2++];
}
//拷貝排序后數(shù)據(jù)到原數(shù)組
for (int j = i; j <= end2; j++)
{
a[j] = tmp[j];
}
}
gap *= 2;
}
free(tmp);//釋放
tmp = NULL;
}相關(guān)分析：
對于越界情況我們可以直接break掉，拷貝的時候我們只能在for循環(huán)里面進行拷貝，也就是部分拷貝，防止在for循環(huán)外面進行拷貝的話，arr中會出現(xiàn)隨機值的情況。
五、計數(shù)排序 -?非比較排序
計數(shù)排序基本思想：
- ?統(tǒng)計相同元素出現(xiàn)次數(shù)：在排序數(shù)組中找到最大最小的數(shù)據(jù)，算出對應(yīng)范圍（max -?min +1）并創(chuàng)建對應(yīng)長度個數(shù)組用來計數(shù)（相對位置遍歷一次+1），遍歷排序數(shù)組
- 根據(jù)統(tǒng)計的結(jié)果將序列回收到原來的序列中：根據(jù)每個出現(xiàn)的數(shù)據(jù)值與計數(shù)數(shù)組下標構(gòu)建的相對映射關(guān)系進行統(tǒng)計數(shù)據(jù)出現(xiàn)次數(shù)，最后將統(tǒng)計的出的數(shù)據(jù)按次序賦值給原數(shù)組
- 我們總共需要遍歷三遍數(shù)組
動圖展示：?
?代碼實現(xiàn)：
void CountSort(int* a, int n) //計數(shù)排序
{
//遍歷找出數(shù)組最大最小值（算出范圍）
int max = a[0], min = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] > max)
max = a[i];
if (a[i] < min)
min = a[i];
}
int range = max - min + 1;
//開辟對應(yīng)長度個計數(shù)數(shù)組
int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc fail");
exit(-1);
}
//初始化數(shù)組計數(shù)為0
memset(count, 0, sizeof(int) * range);
//遍歷計數(shù)據(jù)出現(xiàn)次數(shù)
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
//a[i] - min：數(shù)據(jù)與下標構(gòu)成的相對映射關(guān)系
}
//排入原數(shù)組
int p = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
a[p++] = i + min;
}
}
free(count);//釋放內(nèi)存
count = NULL;
}相關(guān)分析：
在數(shù)據(jù)較為集中的情況下，計數(shù)排序的性能是很好的，因為N大于range的話，其時間復(fù)雜度就是O(N)。缺點是：1、適用于數(shù)據(jù)集中的情況，數(shù)據(jù)分散會浪費空間 2、只適用于整型數(shù)據(jù)的排序
六、對排序的分析總結(jié)
什么是排序的穩(wěn)定性：?
如果在某個排序算法在排序過程中，沒有打亂原有序列中相同數(shù)據(jù)的相對位置關(guān)系，我們就稱這個算法是穩(wěn)定的。
像是希爾排序，相同的數(shù)據(jù)可能被預(yù)排序到不同的組，不能保證排序的穩(wěn)定性；像是冒泡排序是從左到右進行比較排序，相同數(shù)據(jù)的相對位置關(guān)系不會發(fā)生改變，因此排序是穩(wěn)定的。
排序算法復(fù)雜度及穩(wěn)定性總結(jié)：
?思維導(dǎo)圖：
總結(jié)：總體來說插入排序，選擇排序，冒泡排序是低一級水平的排序算法，希爾排序，堆排序，歸并排序和快速排序是高一級別的排序各有優(yōu)缺點，最后計數(shù)排序效率非常高，但有一定局限性。文章來源：http://www.zghlxwxcb.cn/news/detail-651528.html
??歡迎大家批評指正?文章來源地址http://www.zghlxwxcb.cn/news/detail-651528.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】 常見的八大排序算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
