文章目錄
- 快速排序
- 遞回實作
- Hoare版本
- 代碼實作
- 遞回圖解
- 挖坑法
- 代碼實作
- 遞回圖解
- 前后指標法
- 代碼實作
- 遞回圖解
- 非遞回實作
- Hoare版本
- 挖坑法
- 前后指標法
- 非遞回快排代碼實作
- 圖解代碼
- 快速排序的兩個優化
- 1.三數取中
- 代碼實作
- 2.小區間的優化
- 代碼實作
- 歸并排序
- 遞回實作
- 遞回圖解
- 區間劃分要注意（死遞回）
- 非遞回實作
- 代碼實作
- 遞回圖解
- 計數排序
- 絕對映射和相對映射
- 代碼實作
快速排序
快速排序是公認的排序之王，
其基本思想為： 任取待排序元素序列中的某元素作為基準值，按照該基準值將待排序列分為兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后左右序列重復該程序，直到所有元素都排列在相應位置上為止，
對于如何按斬訓準值將待排序列分為兩子序列，常見的方式有：
1、Hoare版本
2、挖坑法
3、前后指標法
這三種方法并沒有明顯的優缺點，時間復雜度都為O（nlogn）
遞回實作
Hoare版本
Hoare版本單趟排序的基本步驟如下：
1.選一個key作為比較值，一般是最左邊或者最右邊，
2.定義一個left和right，如果key選取的是左邊就讓右邊的先走，直到right找到一個比key小的值，然后讓left從左邊走，直到讓它找到一個比key大的值，然后交換兩者，之后繼續讓right先走，left后走，直到left與right相遇停下來，
3.最終再讓相遇處與key處位置對應的值做交換，這樣就可以達到我們想要的效果了，
4.之后遞回它的左序列和右序列，最終排成升序，
注意：可能有小伙伴會問了，如果你最后key與meet（相遇處）處對應的值交換，萬一meet比key處的值大，那不就達不到我們要的效果了嗎？其實這里并不會出現這個問題，因為這種方法讓right先走了，所以不會出現這種問題，大家可以多去嘗試幾組資料看看，是不是會有這個特點
代碼實作
//快速排序（Hoare版本）
void QuickSort1(int* a, int left, int right)
{
if (left >= right)//當只有一個資料或是序列不存在時，不需要進行操作
return;
int begin = left;//L
int end = right;//R
int key = left;//key的下標
while (left < right)
{
//right先走，找小
while (left < right&&a[right] >= a[key])
{
right--;
}
//left后走，找大
while (left < right&&a[left] <= a[key])
{
left++;
}
if (left < right)
{
swap(&a[left], &a[right]);
}
}
int meet = left;//L和R的相遇點
swap(&a[key], &a[meet]);//交換key和相遇點的值
QuickSort1(a, begin, meet - 1);//key的左序列進行此操作
QuickSort1(a, meet + 1, end);//key的右序列進行此操作
}
注意：
1.這里要保存一下left和right的值，因為你在代碼程序中left和right的值會發生變化，如果你不保存，在遞回時傳參直接傳left和right的話，那時就不是我們想要的值了，
2.這里你key要記錄left的下標，而不是記錄a[left]這個數值，因為如果這樣的話，你在下面交換key位置和meet位置對應的值時就會出問題，你只有記錄下標，才可以做到對應位置值得交換，
遞回圖解
挖坑法
挖坑法的單趟排序的基本步驟如下：
1.先選取一個初始坑位，并讓此位置的值記作key（一般選取最左邊或者最右邊）
2.同樣這里也是right先走，直到找到一個比key小的值，然后將這個值填入坑位，并讓這個位置再來做坑，之后移動left，直到找到一個比key大的值，再將這個位置的值填入坑位，然后讓這個位置來做坑，這樣一直回圈下去，直到left==right，
3.當left與right相遇時，此時將key的值賦值給相遇位置即可，這時就達到我們想要的效果：key左邊的值都小于key，key右邊的值都大于key，
4.然后仍然是遞回其左序列和右序列，最終整個序列升序，
代碼實作
//快速排序 （填坑法）
void QuickSort2(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int begin = left; //保存left的值，為了下面的遞回傳遞
int end = right;//保存right的值，為了下面的遞回傳遞
/*int key = left;*/ //這個地方要記住那個數，因為記下標
//的話，沒用，left已經和其他位置交換過了，那么就不是我們想要的值了
int key = a[left];
int hole = left;
while (left < right)
{
while (left<right&&a[right]>=key)
{
--right;
}
a[hole] = a[right];
hole = right;
while (left<right&&a[left]<=key)
{
++left;
}
a[hole] = a[left];
hole = left;
}
int meet = left;
a[meet] = key;
QuickSort2(a, begin, meet- 1);
QuickSort2(a, meet+ 1, end);
}
注意：
1.這里同樣也要保存下left和right的值，原因同Hoare法的一樣，因為代碼程序中其值發生改變會影響遞回傳遞，
2.這里與Hoare法有所不同，這里key要記錄a[left],而不是下標，因為你在之后的填坑程序中，left下標處的值可能被交換了，不是我們最初想要的值，所以要記錄下來最初的那個值，即a[left]，
遞回圖解
前后指標法
前后指標法的單趟排序的基本步驟如下：
1.選出一個key作為比較值，一般是最左或者最右邊，讓prev指向left，cur指向left+1，
2.之后比較cur位置的值和key的值，首先要保證cur位置的值要小于key，而且++prev！=cur,這時交換prev和cur位置對應的值，不管滿不滿足這兩個條件，cur都要++，這樣才能迭代起來，
3.直到cur越界，此時prev為key應該在的位置，此時交換prev位置的值和key，就可以達到我們想要的效果，
4.仍然是遞回其左序列和右序列，最終整個序列有序，
代碼實作
//快速排序（前后指標法）
void QuickSort3(int *a, int left, int right)
{
if (left >= right)
{
return;
}
//這里沒有必要記錄left和right的值，因為整個代碼中這兩個量一開始是什么值，最終仍然是那個值
//int begin= left;
//int end = right;
int pre = left;
int cur = left + 1;
int key = left; //這里要記住小標，不然值是交換不過去的，一般快排中用到交換的換，都是記錄下標
while (cur <= right)
{
if (a[cur] < a[key] && ++pre != cur)
{
swap(&a[pre], &a[cur]);
}
cur++;
}
int meet = pre;
swap(&a[meet], &a[key]);
QuickSort3(a, left, meet - 1);
QuickSort3(a, meet + 1, right);
}
注意：
1.這里沒有必要再和上面一樣保存left和right的值了，因為整個程序中left和right的值并沒有變化，
2.這里和Hoare法那兒一樣，key要記錄left這個下標，而不是a[left]這個值，因為你之后要交換meet和key位置處對應的值，而你一開始如果記錄a[left]是做不到這一點的，(一般而言如果有swap交換這個需求的話，都要記錄下標，而不是下標處對應的值）
3.這里要注意a[cur] < a[key] && ++pre != cur這兩個條件寫的先后順序，一定要把比較大小寫在前面，如果你的a[cur]都不滿足比a[key]小，那么就不需要++prev這一步的判斷了，
遞回圖解
非遞回實作
當我們需要將一個用遞回實作的演算法改為非遞回時，一般需要借用一個資料結構，那就是堆疊，將Hoare版本、挖坑法以及前后指標法的快速排序改為非遞回版本，其實主體思想一致，只是呼叫的單趟排序的演算法不同而已，
Hoare版本
//快速排序（前后指標法）
void QuickSort3(int *a, int left, int right)
{
if (left >= right)
{
return;
}
//這里沒有必要記錄left和right的值，因為整個代碼中這兩個量一開始是什么值，最終仍然是那個值
//int begin= left;
//int end = right;
int pre = left;
int cur = left + 1;
int key = left;
while (cur <= right)
{
if (a[cur] < a[key] && ++pre != cur)
{
swap(&a[pre], &a[cur]);
}
cur++;
}
int meet = pre;
swap(&a[meet], &a[key]);
QuickSort3(a, left, meet - 1);
QuickSort3(a, meet + 1, right);
}
挖坑法
//挖坑法（單趟排序）
int QuickSort2(int* a, int left, int right)
{
int key = a[left];//在最左邊形成一個坑位
while (left < right)
{
//right向左，找小
while (left < right&&a[right] >= key)
{
right--;
}
//填坑
a[left] = a[right];
//left向右，找大
while (left < right&&a[left] <= key)
{
left++;
}
//填坑
a[right] = a[left];
}
int meeti = left;//L和R的相遇點
a[meeti] = key;//將key拋入坑位
return meeti;//回傳key的當前位置
}
前后指標法
//前后指標法（單趟排序）
int QuickSort3(int* a, int left, int right)
{
int prev = left;
int cur = left + 1;
int keyi = left;
while (cur <= right)//當cur未越界時繼續
{
if (a[cur] < a[keyi] && ++prev != cur)//cur指向的內容小于key
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
int meeti = prev;//cur越界時，prev的位置
Swap(&a[keyi], &a[meeti]);//交換key和prev指標指向的內容
return meeti;//回傳key的當前位置
}
快速排序的非遞回演算法基本思路：
1、先將待排序列的第一個元素的下標和最后一個元素的下標入堆疊，
2、當堆疊不為空時，讀取堆疊中的資訊（一次讀取兩個：一個是L，另一個是R），然后呼叫某一版本的單趟排序，排完后獲得了meet的下標，然后判斷meet的左序列和右序列是否還需要排序，若還需要排序，就將相應序列的L和R入堆疊；若不需排序了（序列只有一個元素或是不存在），就不需要將該序列的資訊入堆疊，
3、反復執行步驟2，直到堆疊為空為止，
非遞回快排代碼實作
//類似于二叉樹的遍歷，根——右子樹——左子樹
void QuickSort4(int* a, int left, int right)
{
ST p;
StackInit(&p);
StackPush(&p, left);
StackPush(&p, right);
while (!StackEmpty(&p))
{
int right= StackTop(&p); //注意堆疊的性質，或進先出，因此先賦值給right
StackPop(&p);
int left= StackTop(&p);
StackPop(&p);
//if (left >= right) 可寫可不寫
//{
// return;
//}
int meet = QuickSort5(a, left, right);
if (left < meet - 1) //左序列還存在時
{
StackPush(&p, left);
StackPush(&p, meet - 1);
}
if (meet + 1 < right) //右序列還存在時
{
StackPush(&p, meet + 1);
StackPush(&p, right);
}
}
StackDestory(&p);
}
注意：這里要注意堆疊的性質后進先出，因此要先賦值給right再賦值給left，
圖解代碼
時間復雜度：O（nlogn）
快速排序的兩個優化
1.三數取中
快速排序的時間復雜度是O(NlogN)，是我們在理想情況下計算的結果，在理想情況下，我們每次進行完單趟排序后，key的左序列與右序列的長度都相同：
?若每趟排序所選的key都正好是該序列的中間值，即單趟排序結束后key位于序列正中間，那么快速排序的時間復雜度就是O(NlogN)，
但是萬一當待排序列本就是一個有序的序列時，我們若是依然每次都選取最左邊或是最右邊的數作為key，那么快速排序的效率將達到最低：
這時的時間復雜度為O（n^2)，其實，對快速排序效率影響最大的就是選取的key，若選取的key越接近中間位置，則則效率越高，
為了避免這種極端情況的發生，于是出現了三數取中：
三數取中，當中的三數指的是：最左邊的數、最右邊的數以及中間位置的數，三數取中就是取這三個數當中，值的大小居中的那個數作為該趟排序的key，這就確保了我們所選取的數不會是序列中的最大或是最小值了，
代碼實作
int GetMidIndex(int* a, int left, int right)
{
int mid = left + (right - left) / 2; //防止整形溢位
if (a[right] > a[mid])
{
if (a[mid] > a[left])
{
return mid;
}
else if (a[right] > a[left])
{
return left;
}
else
{
return right;
}
}
else
{
if (a[left] > a[mid])
{
return mid;
}
else if (a[right] > a[left])
{
return right;
}
else
{
return left;
}
}
}
2.小區間的優化
我們可以看到，就算是上面理想狀態下的快速排序，也不能避免隨著遞回的深入，每一層的遞回次數會以2倍的形式快速增長，
為了減少遞回樹的最后幾層遞回，我們可以設定一個判斷陳述句，當序列的長度小于某個數的時候就不再進行快速排序，轉而使用其他種類的排序，小區間優化若是使用得當的話，會在一定程度上加快快速排序的效率，而且待排序列的長度越長，該效果越明顯，
代碼實作
//快速排序的小區間優化
void QuickSort6(int *a, int left, int right)
{
if (left >= right)
{
return;
}
if (right - left + 1 > 20)
{
int meet = QuickSort5(a, left, right);
QuickSort5(a, left, meet - 1);
QuickSort5(a, meet + 1, right);
}
else
{
ShellSort(a,right-left+1);
}
}
歸并排序
歸并排序是采用分治法的一個非常典型的應用，其基本思想是：先讓每個子序列都有序，然后再合并這些子序列，讓整個序列有序，這其中要注意了：
子序列又可以看成是一個整體又可以分成兩個子序列，要直到分到序列只有一個數時，這時才不能繼續分了，且當只有一個數時，這個序列就是有序的，其實這兒的思想和二叉樹的好像，當你看完代碼和遞回程序后，你還會發現其實這個和二叉樹的后序遍歷很相似，
下面來看個例子：
其實這張圖就相當于是整個遞回的程序，分解的程序相當于遞回的順序執行，合并的程序相當于遞回回傳的程序，
遞回實作
其間我們需要申請一個與待排序列大小相同的陣列用于合并程序兩個有序的子序列，合并完畢后再將資料拷貝回原陣列，
void MergeSort(int* a, int left, int right,int* temp)
{
if (left >= right)
return;
int mid = left + (right - left) / 2;
int begin1 = left, end1 = mid;
int begin2 = mid+1, end2 = right;
int i = left,j=0; //i一定要寫成left不能寫成0，如果是遞回左序列還可以適用，但是遞回到右序列時就不行了
MergeSort(a, left, mid, temp); //這里要注意區間的劃分，不然可能出現死遞回
MergeSort(a, mid + 1, right, temp);
while (begin1 <= end1&&begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
temp[i++] = a[begin1++];
}
else
{
temp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
temp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[i++] = a[begin2++];
}
for (j = left; j < right + 1; j++)
{
a[j] = temp[j];
}
}
時間復雜度 ： O（NlogN） 空間復雜度： O（N）
遞回圖解
區間劃分要注意（死遞回）
在上面的代碼中，我們將區間劃分成了[left,mid]和[mid+1，right],是不是只能這樣分了？帶著這樣的好奇，我嘗試了另一種分法，將區間劃分成[left,mid-1]和[mid,right],這樣劃分是否可以了？經過畫圖分析后，答案是不可以的，在這個問題中，區間只能這么劃分，
如果你是這樣劃分的話，在某些測驗用例中，可能會出現死遞回，其原因是你的mid和right有可能永遠不會相等，也就無法結束掉某個遞回，因此造成了死遞回，
非遞回實作
歸并排序的非遞回并不像快速排序那樣一定要用堆疊來實作，我們只需要控制每次參與合并的元素個數即可，最終便能使序列變為有序
這只是一個理想化的例子，在做這種題目時，我們一定要充分考慮到邊界情況，
情況一：
第二個小區間存在，但是個數不滿，這時我們需要對邊界進行控制，不然會導致序列合并時陣列越界的問題，
情況二：
第二個小區間不存在，第一個小區間存在，這時我們不需要在意第一個小區間有沒有滿，因為這時只有一個區間，無法進行序列的合并，所以直接不管它，即break出去就行，
代碼實作
void _MergeSort(int *a, int begin1,int end1,int begin2,int end2, int * temp)
{
int j = begin1;
int i = begin1;
while (begin1 <= end1&&begin2 <= end2) //用&&鏈接，其中有一個結束就結束了
{
if (a[begin1] < a[begin2])
{
temp[i++] = a[begin1++];
}
else
{
temp[i++] = a[begin2++];
}
}
while (begin1 <= end1) //如果區間一還有則全部賦值過去
{
temp[i++] = a[begin1++];
}
while (begin2 <= end2) //如果區間二還有則全部賦值過去，這時兩個序列合并完成
{
temp[i++] = a[begin2++];
}
for (; j <= end2; j++) //將合并好的序列傳給原陣列
{
a[j] = temp[j];
}
}
void MergeSort2(int *a, int n)
{
int *temp = (int *)malloc(sizeof(int)*n);
if (temp == NULL)
{
printf("malloc failed\n");
exit(-1);
}
int gap = 1; //控制每次元素的個數
int i = 0;
while (gap < n)
{
for (i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + (2 * gap) - 1;
if (begin2 >= n) //此時只有第一個區間，不存在兩個序列合并的需求，因此直接break
{
break;
}
if (end2 >= n) //此時第二個區間元素個數不滿，為了防止合并兩個序列時陣列訪問越界，在這里處理掉
{
end2 =n-1;
}
_MergeSort(a, begin1, end1, begin2, end2, temp);
}
gap *= 2;
}
free(temp);
}
遞回圖解
計數排序
計數排序又叫非比較排序，它不需要比較就可以排序，是不是很神奇了？它主要是利用哈希映射來實作的（這在之后c++部分會詳細介紹），這里大概說下它的思路：
1.首先創建一個陣列，那么這個陣列的大小怎么定了？這取決于原陣列中的最大值和最小值，
2.然后我們遍歷原陣列，遇到哪個值則在創建的陣列中以他為下標的位置++，
3.最后列印創建的陣列的下標，那個下標存放的值為幾，則那個下標就列印幾次，
注意：為什么我們這樣就能保證陣列是有序的了？其實最主要的原因是因為陣列的下標本來就是有序的，其次這其中利用了哈希映射，
絕對映射和相對映射
上列中的映射方法稱為絕對映射，即arr陣列中的元素是幾就在count陣列中下標為幾的位置++，但這樣會造成空間浪費，例如，我們要將陣列：1001,1002,1005，進行排序，難道我們要開辟1006個整型空間嗎？
所以我們使用計數排序時，最好是使用相對映射，下面我們來簡單介紹下相對映射：陣列中的最小值就相對于count陣列中的0下標，陣列中的最大值就相對于count陣列中的最后一個下標，這樣，對于陣列1001,1002,1005我們只需要開辟5個空間即可，即此時count陣列中下標為i的位置，記錄的是1001+i出現的次數，
總的來說：
絕對映射：count陣列中下標為i的位置記錄的是arr陣列中數字i出現的次數，
相對映射：count陣列中下標為i的位置記錄的是arr陣列中數字min+i出現的次數，
這里也要注意：計數排序針對數字較為集中時處理比較高效，如果剛剛那個陣列為1,100,1005則不管使用什么映射，都會存在空間的浪費，
代碼實作
//計數排序
void CountSort(int*a, int sz)
{
int min = a[0], max = a[0];
int i = 0;
int j = 0;
for (i = 1; i < sz; i++)
{
if (a[i] < min)
{
min = a[i];
}
if (a[i]>max)
{
max = a[i];
}
}
int range = max - min + 1;//min和max之間的自然數個數（包括min和max本身）
int *count = (int*)calloc(range, sizeof(int));//min和max之間的自然數個數（包括min和max本身）
if (count == NULL)
{
printf("calloc failed\n");
exit(-1);
}
統計相同元素出現次數（相對映射）
for (i = 0; i < sz; i++)
{
count[a[i]-min]++;
}
根據統計結果將序列回收到原來的序列中
for (i = 0; i < range; i++)
{
while (count[i]--)
{
a[j++] = i+min;
}
}
free(count);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/301522.html
標籤：其他