一、直接插入排序
基本思想：
我們平時(shí)玩撲克牌時(shí)，摸牌階段的排序就用到了插入排序的思想
- 1、當(dāng)插入第n個(gè)元素時(shí)，前面的n-1個(gè)數(shù)已經(jīng)有序
- 2、用這第n個(gè)數(shù)與前面的n-1個(gè)數(shù)比較，找到要插入的位置，將其插入（原來位置上的數(shù)不會(huì)被覆蓋，因?yàn)樘崆氨４媪耍?/li>
- 3、原來位置上的數(shù)據(jù)，依次后移
具體實(shí)現(xiàn)：
- ①單趟的實(shí)現(xiàn)（將x插入到 [0,end] 的有序區(qū)間）
即一般情況下的插入，我們隨機(jī)列舉了一些數(shù)字，待插入的數(shù)字分為兩種情況
（1）待插入的數(shù)字是在前面有序數(shù)字的中間數(shù)，直接比較將x賦值給end+1位置 （2）x是最小的一個(gè)數(shù)，end就會(huì)到達(dá)-1的位置，最后直接將x賦值給end+1位置
- ②整個(gè)數(shù)組排序的實(shí)現(xiàn)
我們一開始并不知道數(shù)組是不是有序的，所以我們控制下標(biāo)，end從0開始，將end+1位置的值始終保存到x中，循環(huán)進(jìn)行單趟排序即可，最后結(jié)束時(shí)end=n-2，n-1位置的數(shù)字保存到x中
總體代碼：
void InsertSort(int* a, int n)
{
assert(a);
for (int i = 0; i < n - 1; ++i)
{
int end = i;
int x=a[end+1];//將end后面的值保存到x里面了
//將x插入到[0，end]的有序區(qū)間
while (end >= 0)
{
if (a[end] > x)
{
a[end + 1] = a[end]; //往后挪動(dòng)一位
--end;
}
else
{
break;
}
}
a[end + 1] = x; //x放的位置都是end的后一個(gè)位置
}
}直接插入排序總結(jié)：
- ①元素越接近有序，直接插入排序的效率越高
- ②時(shí)間復(fù)雜度:O(N^2)
最壞的情況下，每次插入一個(gè)數(shù)字，前面的數(shù)字都要挪動(dòng)一下，一共需要挪動(dòng)1+2+3+……+n=n(n+1)/2
③空間復(fù)雜度：O(1)
沒有借助額外的空間，只用到常數(shù)個(gè)變量
二、希爾排序
基本思想：
- 1、先選定個(gè)小于n的數(shù)字作為gap，所有距離為gap的數(shù)分為一組進(jìn)行預(yù)排序（直接插入排序）
- 2、再選一個(gè)小于gap的數(shù)，重復(fù)①的操作
- 3、當(dāng)gap=1時(shí)，相當(dāng)于整個(gè)數(shù)組就是一組，再進(jìn)行一次插入排序即可整體有序
例如：
具體實(shí)現(xiàn)：
①單組排序
和前面的直接插入相同，就是把原來的間隔為1，現(xiàn)在變?yōu)間ap了，每組分別進(jìn)行預(yù)排序
②多組進(jìn)行排序
③整個(gè)數(shù)組進(jìn)行排序（控制gap）
多次預(yù)排序（gap>1）+ 一次插入排序（gap==1）
（1）gap越大，預(yù)排越快，越不接近于有序
（2）gap越小，預(yù)排越慢，越接近有序
結(jié)果就是：
總體代碼：
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap /= 2;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = x;
}
}
}希爾排序總結(jié)：
- ①希爾排序是對直接插入排序的優(yōu)化
- ②時(shí)間復(fù)雜度：O(N^1.3)
- ③空間復(fù)雜度：O(1)
三、選擇排序
基本思想：
每次從數(shù)組中選出最大的或者最小的，存放在數(shù)組的最右邊或者最左邊，直到全部有序
具體實(shí)現(xiàn)：
我們這里進(jìn)行了優(yōu)化，一次排序中，直接同時(shí)選出最大的數(shù)（a[maxi]）和最小的數(shù)（a[mini]）放在最右邊和最左邊，這樣排序效率是原來的2倍
- ①單趟排序
找到最小的數(shù)字（a[mini]）和最大的數(shù)字（a[maxi]），將他們放在最左邊和最右邊
ps：其中的begin，end保存記錄左右的下標(biāo)，mini，maxi記錄保存最小值和最大值得下標(biāo)
- ②整個(gè)數(shù)組排序
begin++和end--這樣下次就可以排剩下的n-2個(gè)數(shù)字，再次進(jìn)行單趟，如此可構(gòu)成循環(huán)，直到begin小于end
整體代碼：
void SelectSort(int* a, int n)
{
int begin = 0,end = n - 1;
while (begin<end)
{
int mini = begin, maxi = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[mini], &a[begin]);
//當(dāng)begin==maxi時(shí)，最大值會(huì)被換走，修正一下
if (begin==maxi)
{
maxi=mini;
}
Swap(&a[maxi], &a[end]);
begin++;
end--;
}
}直接選擇排序總結(jié)：
-
①直接選擇排序很好理解，但實(shí)際效率不高，很少使用
-
②時(shí)間復(fù)雜度：O(N^2)
-
③空間復(fù)雜度：O(1)
四、堆排序
基本思想：
-
1、將待排序的序列構(gòu)造成一個(gè)大堆，根據(jù)大堆的性質(zhì)，當(dāng)前堆的根節(jié)點(diǎn)（堆頂）就是序列中最大的元素；
-
2、將堆頂元素和最后一個(gè)元素交換，然后將剩下的節(jié)點(diǎn)重新構(gòu)造成一個(gè)大堆；
-
3、重復(fù)步驟2，如此反復(fù)，從第一次構(gòu)建大堆開始，每一次構(gòu)建，我們都能獲得一個(gè)序列的最大值，然后把它放到大堆的尾部。最后，就得到一個(gè)有序的序列了。
-
小結(jié)論： 排升序，建大堆 排降序，建小堆
具體實(shí)現(xiàn)：、
- ①向下調(diào)整算法
我們將給定的數(shù)組序列，建成一個(gè)大堆，建堆從根節(jié)點(diǎn)開始就需要多次的向下調(diào)整算法
堆的向下調(diào)整算法（使用前提）： （1）若想將其調(diào)整為小堆，那么根結(jié)點(diǎn)的左右子樹必須都為小堆。 （2）若想將其調(diào)整為大堆，那么根結(jié)點(diǎn)的左右子樹必須都為大堆。
向下調(diào)整算法的基本思想：
- 1、從根節(jié)點(diǎn)開始，選出左右孩子值較大的一個(gè)
- 2、如果選出的孩子的值大于父親的值，那么就交換兩者的值
- 3、將大的孩子看做新的父親，繼續(xù)向下調(diào)整，直到調(diào)整到葉子節(jié)點(diǎn)為止
//向下調(diào)整算法
//以建大堆為例
void AdJustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
//默認(rèn)左孩子較大
while (child < n)
{
if (child + 1 < n && a[child+1] > a[child ])//如果這里右孩子存在，
//且更大，那么默認(rèn)較大的孩子就改為右孩子
{
child++;
}
if(a[child]>a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}- ②建堆（將給定的任意數(shù)組建成大堆）
建堆思想： 從倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)開始，從后往前，依次將其作為父親，依次向下調(diào)整，一直調(diào)整到根的位置
建堆圖示：
//最后一個(gè)葉子結(jié)點(diǎn)的父親為i，從后往前，依次向下調(diào)整，直到調(diào)到根的位置
for (int i = (n - 1 - 1) / 2;i>=0;--i)
{
AdJustDown(a,n,i);
}- ③堆排序（利用堆刪的思想進(jìn)行）
堆排序的思想： 1、建好堆之后，將堆頂?shù)臄?shù)字與最后一個(gè)數(shù)字交換 2、將最后一個(gè)數(shù)字不看，剩下的n-1個(gè)數(shù)字再向下調(diào)整成堆再進(jìn)行第1步 3、直到最后只剩一個(gè)數(shù)停止，這樣就排成有序的了
for (int end = n - 1; end > 0; --end)
{
Swap(&a[end],&a[0]);
AdJustDown(a,end,0);
}整體代碼如下：
void AdJustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child+1] > a[child ])
{
child++;
}
if(a[child]>a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//堆排序
void HeapSort(int*a,int n)
{
for (int i = (n - 1 - 1) / 2;i>=0;--i)
{
AdJustDown(a,n,i);
}
for (int end = n - 1; end > 0; --end)
{
Swap(&a[end],&a[0]);
AdJustDown(a,end,0);
}
}五、冒泡排序
冒泡排序的基本思想：
一趟過程中，前后兩個(gè)數(shù)依次比較，將較大的數(shù)字往后推，下一次只需要比較剩下的n-1個(gè)數(shù)，如此往復(fù)
//優(yōu)化版本的冒泡排序
void BubbleSort(int* a, int n)
{
int end = n-1;
while (end>0)
{
int exchange = 0;
for (int i = 0; i < end; i++)
{
if (a[i] > a[i + 1])
{
Swap(&a[i], &a[i + 1]);
exchange = 1;
}
}
if (exchange == 0)//單趟過程中，若沒有交換過，證明已經(jīng)有序，沒有必要再排序
{
break;
}
end--;
}
}冒泡排序總結(jié)：
- ①非常容易理解的排序
- ②時(shí)間復(fù)雜度:O(N^2)
- ③空間復(fù)雜度:O(1)
六、快速排序
遞歸版本
1、hoare版本
hoare的單趟思想： 1、左邊作key，右邊先走找到比key小的值 2、左邊后走找到大于key的值 3、然后交換left和right的值 4、一直循環(huán)重復(fù)上述1 2 3步 5、兩者相遇時(shí)的位置，與最左邊選定的key值交換 這樣就讓key到達(dá)了正確的位置上
動(dòng)圖演示：
//hoare版本 //單趟排序 讓key到正確的位置上 keyi表示key的下標(biāo)，并不是該位置的值 int partion1(int* a, int left, int right) { int keyi = left;//左邊作keyi while (left < right) { //右邊先走，找小于keyi的值 while (left < right && a[right] >= a[keyi]) { right--; } //左邊后走，找大于keyi的值 while (left < right && a[left] <= a[keyi]) { left++; } Swap(&a[left], &a[right]); } Swap(&a[left], &a[keyi]); return left; } void QuickSort(int* a, int left, int right) { if (left >= right) return; int keyi = partion1(a, left, right); //[left,keyi-1] keyi [keyi+1,right] QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); }2、挖坑法
其實(shí)本質(zhì)上是hoare的變形
挖坑法單趟思想： 1、先將最左邊第一個(gè)數(shù)據(jù)存放在臨時(shí)變量key中，形成一個(gè)坑位 2、右邊先出發(fā)找到小于key的值，然后將該值丟到坑中去，此時(shí)形成一個(gè)新坑位 3、左邊后出發(fā)找到大于key的值，將該值丟入坑中去，此時(shí)又形成一個(gè)新的坑位 4、一直循環(huán)重復(fù)1 2 3步 5、直到兩邊相遇時(shí)，形成一個(gè)新的坑，最后將key值丟進(jìn)去 這樣key就到達(dá)了正確的位置上了
動(dòng)圖演示：
//hoare版本
//單趟排序 讓key到正確的位置上 keyi表示key的下標(biāo)，并不是該位置的值
int partion1(int* a, int left, int right)
{
int keyi = left;//左邊作keyi
while (left < right)
{ //右邊先走，找小于keyi的值
while (left < right && a[right] >= a[keyi])
{
right--;
}
//左邊后走，找大于keyi的值
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
return left;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int keyi = partion1(a, left, right);
//[left,keyi-1] keyi [keyi+1,right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}3、前后指針法（推薦這種寫法）
前后指針的思想：
1、初始時(shí)選定prev為序列的開始，cur指針指向prev的后一個(gè)位置，同樣選擇最左邊的第一個(gè)數(shù)字作為key 2、cur先走，找到小于key的值，找到就停下來 3、++prev 4、交換prev和cur為下標(biāo)的值 5、一直循環(huán)重復(fù)2 3 4步，停下來后，最后交換key和prev為下標(biāo)的值
這樣key同樣到達(dá)了正確的位置
動(dòng)圖演示：
int partion3(int* a, int left, int right)
{
int prev = left;
int cur = left + 1;
int keyi = left;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)//prev != cur 防止cur和prev相等時(shí)，相當(dāng)于自己和自己交換，可以省略
{ //前置 ++ 的優(yōu)先級大于 != 不等于的優(yōu)先級
Swap(&a[prev], &a[cur]);
}
++cur;
}
Swap(&a[keyi], &a[prev]);
return prev;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int keyi = partion3(a, left, right);
//[left,keyi-1] keyi [keyi+1,right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}遞歸展開圖
快速排序的優(yōu)化
1、三數(shù)取中法
快速排序?qū)τ跀?shù)據(jù)是敏感的，如果這個(gè)序列是非常無序，雜亂無章的，那么快速排序的效率是非常高的，可是如果數(shù)列有序，時(shí)間復(fù)雜度就會(huì)從O(N*logN)變?yōu)镺(N^2)，相當(dāng)于冒泡排序了
若每趟排序所選的key都正好是該序列的中間值，即單趟排序結(jié)束后key位于序列正中間，那么快速排序的時(shí)間復(fù)雜度就是O(NlogN)
但是這是理想情況，當(dāng)我們面對一組極端情況下的序列，就是有序的數(shù)組，選擇左邊作為key值的話，那么就會(huì)退化為O(N^2)的復(fù)雜度，所以此時(shí)我們選擇首位置，尾位置，中間位置的數(shù)分別作為三數(shù)，選出中間位置的數(shù)，放到最左邊，這樣選key還是從左邊開始，這樣優(yōu)化后，全部都變成了理想情況
//快排的優(yōu)化 //三數(shù)取中法 int GetMidIndex(int* a, int left, int right) { int mid = (left + right) / 2; if (a[left] < a[right]) { if (a[mid] < a[right]) { return mid; } else if (a[mid] > a[right]) { return right; } else { return left; } } else { if (a[mid] > a[left]) { return left; } else if (a[mid] < a[right]) { return right; } else { return mid; } } } int partion5(int* a, int left, int right) { //三數(shù)取中,面對有序時(shí)是最壞的情況O(N^2)，現(xiàn)在每次選的key都是中間值，變成最好的情況了 int midi = GetMidIndex(a, left, right); Swap(&a[midi], &a[left]);//這樣還是最左邊作為key int prev = left; int cur = left + 1; int keyi = left; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur)//prev != cur 防止cur和prev相等時(shí)，相當(dāng)于自己和自己交換，可以省略 { //前置 ++ 的優(yōu)先級大于 != 不等于的優(yōu)先級 //++prev; Swap(&a[prev], &a[cur]); } ++cur; } Swap(&a[keyi], &a[prev]); return prev; }2、遞歸到小子區(qū)間
隨著遞歸深度的增加，遞歸次數(shù)以每層2倍的速度增加，這對效率有著很大的影響，當(dāng)待排序序列的長度分割到一定大小后，繼續(xù)分割的效率比插入排序要差，此時(shí)可以使用插排而不是快排
我們可以當(dāng)劃分區(qū)間長度小于10的時(shí)候，用插入排序?qū)κＯ碌臄?shù)進(jìn)行排序
//快排的優(yōu)化
//三數(shù)取中法
int GetMidIndex(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] < a[right])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[mid] > a[right])
{
return right;
}
else
{
return left;
}
}
else
{
if (a[mid] > a[left])
{
return left;
}
else if (a[mid] < a[right])
{
return right;
}
else
{
return mid;
}
}
}
int partion5(int* a, int left, int right)
{
//三數(shù)取中,面對有序時(shí)是最壞的情況O(N^2)，現(xiàn)在每次選的key都是中間值，變成最好的情況了
int midi = GetMidIndex(a, left, right);
Swap(&a[midi], &a[left]);//這樣還是最左邊作為key
int prev = left;
int cur = left + 1;
int keyi = left;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)//prev != cur 防止cur和prev相等時(shí)，相當(dāng)于自己和自己交換，可以省略
{ //前置 ++ 的優(yōu)先級大于 != 不等于的優(yōu)先級
//++prev;
Swap(&a[prev], &a[cur]);
}
++cur;
}
Swap(&a[keyi], &a[prev]);
return prev;
}非遞歸版本
遞歸的算法主要是在劃分子區(qū)間，如果要非遞歸實(shí)現(xiàn)快排，只要使用一個(gè)棧來保存區(qū)間就可以了。一般將遞歸程序改成非遞歸首先想到的就是使用棧，因?yàn)檫f歸本身就是一個(gè)壓棧的過程。
非遞歸的基本思想：
1. 申請一個(gè)棧，存放排序數(shù)組的起始位置和終點(diǎn)位置。
2. 將整個(gè)數(shù)組的起始位置和終點(diǎn)位置入棧。
3. 由于棧的特性是：后進(jìn)先出，right后進(jìn)棧，所以right先出棧。 定義一個(gè)end接收棧頂元素，出棧操作、定義一個(gè)begin接收棧頂元素，出棧操作。
4. 對數(shù)組進(jìn)行一次單趟排序，返回key關(guān)鍵值的下標(biāo)。
5. 這時(shí)候需要排基準(zhǔn)值key左邊的序列。 如果只將基準(zhǔn)值key左邊序列的起始位置和終點(diǎn)位置存入棧中，等左邊排序完將找不到后邊的區(qū)間。所以先將右邊序列的起始位置和終點(diǎn)位置存入棧中，再將左邊的起始位置和終點(diǎn)位置后存入棧中。
6.判斷棧是否為空，若不為空 重復(fù)4、5步、若為空則排序完成。
void QuickSortNonR(int* a, int left, int right)
{
Stack st;
StackInit(&st);
StackPush(&st,left);
StackPush(&st, right);
while (!StackEmpty(&st))
{
int end = StackTop(&st);
StackPop(&st);
int begin = StackTop(&st);
StackPop(&st);
int keyi = partion5(a,begin,end);
//區(qū)間被成兩部分了 [begin,keyi-1] keyi [keyi+1,end]
if (keyi + 1 < end)
{
StackPush(&st,keyi+1);
StackPush(&st,end);
}
if (keyi-1>begin)
{
StackPush(&st, begin);
StackPush(&st, keyi -1);
}
}
StackDestroy(&st);
}快速排序的總結(jié)：
- ①快排的整體綜合性能和使用場景都是比較好的，所以才敢叫快速排序
- ②快排唯一死穴，就是排一些有序或者接近有序的序列，例如 2,3,2,3,2,3,2,3這樣的序列時(shí)，會(huì)變成O(N^2)的時(shí)間復(fù)雜度
- ③時(shí)間復(fù)雜度O(N*logN)
- ④空間復(fù)雜度O(logN)
七、歸并排序
歸并排序的基本思想（分治思想）：
- 1、（拆分）將一段數(shù)組分為左序列和右序列，讓他們兩個(gè)分別有序，再將左序列細(xì)分為左序列和右序列，如此重復(fù)該步驟，直到細(xì)分到區(qū)間不存在或者只有一個(gè)數(shù)字為止
- 2、（合并）將第一步得到的數(shù)字合并成有序區(qū)間
具體實(shí)現(xiàn)：
-
①拆分
-
②合并
遞歸實(shí)現(xiàn)：
從思想上來說和二叉樹很相似，所以我們可以用遞歸的方法來實(shí)現(xiàn)歸并排序
代碼如下：
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid+1, right, tmp);
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int i = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
for (int j = left; j <= right; j++)
{
a[j] = tmp[j];
}
}
//歸并排序
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
_MergeSort(a,0,n-1,tmp);
free(tmp);
tmp = NULL;
}非遞歸實(shí)現(xiàn)：
我們知道，遞歸實(shí)現(xiàn)的缺點(diǎn)就是會(huì)一直調(diào)用棧，而棧內(nèi)存往往是很小的。所以，我們嘗試著用循環(huán)的辦法去實(shí)現(xiàn)
由于我們操縱的是數(shù)組的下標(biāo)，所以我們需要借助數(shù)組，來幫我們存儲(chǔ)上面遞歸得到的數(shù)組下標(biāo)，和遞歸的區(qū)別就是，遞歸要將區(qū)間一直細(xì)分，要將左區(qū)間一直遞歸劃分完了，再遞歸劃分右區(qū)間，而借助數(shù)組的非遞歸是一次性就將數(shù)據(jù)處理完畢，并且每次都將下標(biāo)拷貝回原數(shù)組
歸并排序的基本思路是將待排序序列a[0…n-1]看成是n個(gè)長度為1的有序序列，將相鄰的有序表成對歸并，得到n/2個(gè)長度為2的有序表；將這些有序序列再次歸并，得到n/4個(gè)長度為4的有序序列；如此反復(fù)進(jìn)行下去，最后得到一個(gè)長度為n的有序序列。
但是我們這是理想情況下（偶數(shù)個(gè)），還有特殊的邊界控制，當(dāng)數(shù)據(jù)個(gè)數(shù)不是偶數(shù)個(gè)時(shí)，我們所分的gap組，勢必會(huì)有越界的地方
第一種情況：
第二種情況：
代碼如下：
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
// [i,i+gap-1] [i+gap,i+2*gap-1]
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
// 核心思想：end1、begin2、end2都有可能越界
// end1越界 或者 begin2 越界都不需要?dú)w并
if (end1 >= n || begin2 >= n)
{
break;
}
// end2 越界，需要?dú)w并，修正end2
if (end2 >= n)
{
end2 = n- 1;
}
int index = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
// 把歸并小區(qū)間拷貝回原數(shù)組
for (int j = i; j <= end2; ++j)
{
a[j] = tmp[j];
}
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}歸并排序的總結(jié)：
- ①缺點(diǎn)是需要O(N)的空間復(fù)雜度，歸并排序更多的是解決磁盤外排序的問題
- ②時(shí)間復(fù)雜度:O(N*logN)
- ③空間復(fù)雜度:O(N)
八、計(jì)數(shù)排序
又叫非比較排序，又稱為鴿巢原理，是對哈希直接定址法的變形應(yīng)用
基本思想：
- 1、統(tǒng)計(jì)相同元素出現(xiàn)的個(gè)數(shù)
- 2、根據(jù)統(tǒng)計(jì)的結(jié)果，將數(shù)據(jù)拷貝回原數(shù)組
具體實(shí)現(xiàn)：
- ①統(tǒng)計(jì)相同元素出現(xiàn)的個(gè)數(shù)
對于給定的任意數(shù)組a，我們需要開辟一個(gè)計(jì)數(shù)數(shù)組count，a[i]是幾，就對count數(shù)組下標(biāo)是幾++
這里我們用到了絕對映射，即a[i]中的數(shù)組元素是幾，我們就在count數(shù)組下標(biāo)是幾的位置++，但是對于數(shù)據(jù)比較聚集，不是從較小的數(shù)字開始，例如1001,1002,1003,1004這樣的數(shù)據(jù)，我們就可以用到相對映射的方法，以免開辟數(shù)組空間的浪費(fèi)，count數(shù)組的空間大小我們可以用a數(shù)組中最大值減去最小值+1來確定（即：range=max-min+1）,我們可以得到count數(shù)組下標(biāo) j =a[i]-min
- ②根據(jù)count數(shù)組的結(jié)果，將數(shù)據(jù)拷貝回a數(shù)組
count[j]中數(shù)據(jù)是幾，說明該數(shù)出現(xiàn)了幾次，是0就不用拷貝
代碼如下：
void CountSort(int* a, int n)
{
int min = a[0], max = a[0];//如果不賦值，min和max就是默認(rèn)隨機(jī)值，最好給賦值一個(gè)a[0]
for (int i=1;i<n;i++)//修正 找出A數(shù)組中的最大值和最小值
{
if (a[i] < min)
{
min=a[i];
}
if (a[i]>max)
{
max=a[i];
}
}
int range = max - min + 1;//控制新開數(shù)組的大小，以免空間浪費(fèi)
int* count = (int*)malloc(sizeof(int) * range);
memset(count,0, sizeof(int) * range);//初始化為全0
if (count==NULL)
{
printf("malloc fail\n");
exit(-1);
}
//1、統(tǒng)計(jì)數(shù)據(jù)個(gè)數(shù)
for (int i=0;i<n;i++)
{
count[a[i]-min]++;
}
//2、拷貝回A數(shù)組
int j = 0;
for (int i=0;i<range;i++)
{
while (count[i]--)
{
a[j++] = i + min;
}
}
free(count);
count = NULL;
}計(jì)數(shù)排序總結(jié)：
- ①在數(shù)據(jù)范圍比較集中時(shí)，效率很高，但是使用場景很有限，可以排負(fù)數(shù)，但對于浮點(diǎn)數(shù)無能為力
- ②時(shí)間復(fù)雜度：O(MAX(N,range))
- ③空間復(fù)雜度：O(range)
八大排序的穩(wěn)定性總結(jié)：
穩(wěn)定的排序有：直接插入排序、冒泡排序、歸并排序
不穩(wěn)定的排序有：希爾排序、選擇排序、堆排序、快速排序、計(jì)數(shù)排序