本章重點
排序的概念及其運用
常見排序算法的實現(xiàn)
排序算法復雜度及穩(wěn)定性分析
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ù)的排序。
1.2排序運用
1.3 常見的排序算法
2.常見排序算法的實現(xiàn)
2.1 插入排序
2.1.1基本思想：
直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。
實際中我們玩撲克牌時，就用了插入排序的思想
2.1.2直接插入排序：
????????當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經排好序，此時用array[i]的排序碼與 array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移。
插入過程：如果end+1位置的值小于end位置，就將end位置的值挪到end+1位置處，否則，直接插入到end+1位置。注意，這里需要保存end+1位置的值，因為end位置的值挪到end+1位置時，會覆蓋end+1位置的值。
結束條件：當end+1位置的值小于當前有序序列所有的值時，此時end的值為-1，也就是排序的終止條件
單趟插入排序代碼：單趟[0,end]有序，把end+1位置的值插入到前面序列，控制[0，end+1]序列有序。
// 插入排序
void InsertSort(int* a, int n)
{
int end = ;
//保存要排序的值，防止數(shù)據(jù)被覆蓋找不到數(shù)據(jù)
int temp = a[end + 1];
while (end >= 0)
{
if (temp < a[end])
{
a[end + 1] = a[end];
}
else
{
break;
}
}
//將temp的值賦給end+1位置，這樣就插入有序了
a[end + 1] = temp;
}整趟插入排序：我們默認第一個數(shù)有序，第二個數(shù)插入到有序序列中，調整有序，那么end就是0，如下圖，當最后一個元素插入有序系列中，此時end的值時n-2。
#include <stdio.h>
// 插入排序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
//保存要排序的值，防止數(shù)據(jù)被覆蓋找不到數(shù)據(jù)
int temp = a[end + 1];
while (end >= 0)
{
if (temp < a[end])
{
a[end + 1] = a[end];
}
else
{
break;
}
end--;
}
//將temp的值賦給end+1位置，這樣就插入有序了
a[end + 1] = temp;
}
}
int main()
{
int a[] = { 1,4,2,7,6,9 };
InsertSort(a, 6);
for (int i = 0; i < 6; i++)
{
printf("%d ", a[i]);
}
return 0;
}
直接插入排序的特性總結：
1. 元素集合越接近有序，直接插入排序算法的時間效率越高
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)，它是一種穩(wěn)定的排序算法
4. 穩(wěn)定性：穩(wěn)定
2.1.3 希爾排序( 縮小增量排序 )
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數(shù)，把待排序文件中所有記錄分成個組，所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序。然后，取，重復上述分組和排序的工作。當?shù)竭_=1時，所有記錄在統(tǒng)一組內排好序。
思想：
- 預排序：間接為gap為一組進行排序
- 直接插入排序
單趟排序：將gap為一組的數(shù)據(jù)進行排序，希爾排序和上面的直接插入排序方法相同，只是希爾排序是將gap間距的數(shù)據(jù)進行直接插入排序，若gap==1時，希爾排序和直接插入排序相同。
// 希爾排序
void ShellSort(int* a, int n)
{
int gap = 5;
for (int i = 0; i < n - gap; i+=gap)
{
int end = i;
int temp = a[end + gap];
while (end >= 0)
{
if (a[end] > temp)
{
a[end + gap] = a[end];
}
else
{
break;
}
end -= gap;
}
a[end + gap] = temp;
}
}多趟排序：通過gap將一組數(shù)據(jù)分割，依次將分割的數(shù)據(jù)直接插入排序，每組的數(shù)據(jù)都將有序。
// 希爾排序
void ShellSort(int* a, int n)
{
int gap = 5;
for (int j = 0; j < gap; j++)
{
for (int i = j; i < n - gap; i += gap)
{
int end = i;
int temp = a[end + gap];
while (end >= 0)
{
if (a[end] > temp)
{
a[end + gap] = a[end];
}
else
{
break;
}
end -= gap;
}
a[end + gap] = temp;
}
}
}上面的代碼將gap組數(shù)據(jù)進行直接插入排序，是一組數(shù)據(jù)排完后再排下一組數(shù)據(jù)，下面我們來看一個更厲害的代碼，它在上面的基礎上省略了一個for循環(huán)。
// 希爾排序
void ShellSort(int* a, int n)
{
int gap = 5;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int temp = a[end + gap];
while (end >= 0)
{
if (a[end] > temp)
{
a[end + gap] = a[end];
}
else
{
break;
}
end -= gap;
}
a[end + gap] = temp;
}
}????????上面的代碼不是一組數(shù)據(jù)排完后再排下一組數(shù)據(jù)，它不用跳到下一組數(shù)據(jù)排序，而是不跨組排序，多組并排，比剛剛的代碼更簡潔。經過上面的排序，我們只是使得每組數(shù)據(jù)有序，并沒有使得全部的數(shù)據(jù)有序。上面的排序使得大的數(shù)據(jù)更快的移動到后面，小的數(shù)據(jù)更快的移動到前面，gap越大跳的越快，越不接近有序，gap越小跳的越慢，越接近有序。gap為1，該數(shù)據(jù)就有序了。所有要想數(shù)據(jù)有序，就要讓gap為1。gap>1時就是預排序，gap==1時就是有序。
// 希爾排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap /= 2;//gap等于1，數(shù)據(jù)有序
for (int i = 0; i < n - gap; i++)
{
int end = i;
int temp = a[end + gap];
while (end >= 0)
{
if (a[end] > temp)
{
a[end + gap] = a[end];
}
else
{
break;
}
end -= gap;
}
a[end + gap] = temp;
}
}
}
int main()
{
int a[] = { 1,4,2,7,6,9 };
ShellSort(a, 6);
for (int i = 0; i < 6; i++)
{
printf("%d ", a[i]);
}
return 0;
}我們上面定義的gap是每次除2，這樣排序的次數(shù)還是有點多，所以我們定義的gap是每次除3，但是除3不一定能保證最后一次是1，比如gap為8，除3是2，再除3就是0，所以我們只需要除3后加1就可以滿足最后一次gap為0。
// 希爾排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;//gap等于1，數(shù)據(jù)有序
for (int i = 0; i < n - gap; i++)
{
int end = i;
int temp = a[end + gap];
while (end >= 0)
{
if (a[end] > temp)
{
a[end + gap] = a[end];
}
else
{
break;
}
end -= gap;
}
a[end + gap] = temp;
}
}
}
希爾排序的特性總結：
- 希爾排序是對直接插入排序的優(yōu)化。
- 當gap > 1時都是預排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。
- 希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些樹中給出的希爾排序的時間復雜度都不固定：因為咋們的gap是按照Knuth提出的方式取值的，而且Knuth進行了大量的試驗統(tǒng)計，我們暫時就按照：
2.2 選擇排序
2.2.1基本思想
每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的 數(shù)據(jù)元素排完 。
2.2.2 直接選擇排序
- 在元素集合array[i]--array[n-1]中選擇關鍵碼最大(小)的數(shù)據(jù)元素
- 若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換
- 在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重復上述步驟，直到集合剩余1個元素
// 選擇排序
void SelectSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
//假設下標為0的數(shù)據(jù)最小
int mini = i;
for (int j = mini + 1; j < n; j++)
{
if (a[mini] > a[j])
{
mini = j;
}
}
//此時a[mini]是數(shù)組中最小的值
Swap(&a[i], &a[mini]);
}
}但是上面的每次都是找最小值，然后再放到正確的位置，效率太低，我們是不是可以每次找出一個最大值，再找出一個最小值，然后各自放到正確的位置上，這樣效率就提高了很多。
// 選擇排序
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while(begin < end)
{
int mini = begin;
int maxi = begin;
for (int i = begin + 1; i <= end; i++)
{
if (a[mini] > a[i])
{
mini = i;
}
if (a[maxi] < a[i])
{
maxi = i;
}
}
//此時a[mini]是數(shù)組中最小的值
//此時a[maxi]是數(shù)組中最大的值
Swap(&a[begin], &a[mini]);
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}
為什么結果不對呢？我們上面的代碼出現(xiàn)了什么問題？
很明顯，按照上圖的情況，maxi和begin下標相同，當begin和minx下標的數(shù)據(jù)交換之后，maxi的下標的值就發(fā)生變化了，此時end和maxi交換就不正確了，所以上面的程序是有問題的。我們只需要更新一下maxi的位置就行啦。
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
// 選擇排序
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while(begin < end)
{
int mini = begin;
int maxi = begin;
for (int i = begin + 1; i <= end; i++)
{
if (a[mini] > a[i])
{
mini = i;
}
if (a[maxi] < a[i])
{
maxi = i;
}
}
//此時a[mini]是數(shù)組中最小的值
//此時a[maxi]是數(shù)組中最大的值
Swap(&a[begin], &a[mini]);
//maxi如果被換走就要修正一下
if (maxi == begin)
maxi = mini;
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}
int main()
{
int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
SelectSort(a, 17);
for (int i = 0; i < 17; i++)
{
printf("%d ", a[i]);
}
}
2.2.3 堆排序
????????堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結構所設計的一種排序算法，它是選擇排序的一種。它是 通過堆來進行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。
? ? ? ?所以我們可以建大堆，將堆頂?shù)臄?shù)據(jù)和最后一個葉子結點交換，由于此時的堆結構沒有破壞，左子樹和右子樹仍然是堆，使用堆的向下調整去調整堆，然后在縮小下次向下調整的范圍，也就是把最大的那個數(shù)不算做堆的范圍了，這樣最大的數(shù)據(jù)就保存在了下標最大的位置處，滿足了升序的要求。
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
// 堆排序
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child] < a[child+1])
{
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);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
堆排序的特性總結：
- 堆排序使用堆來選數(shù)，效率就高了很多。
- 時間復雜度：O(N*logN)
- 空間復雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
2.3 交換排序
2.3.1基本思想
所謂交換，就是根據(jù)序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置，交換排 序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。
2.3.2冒泡排序
冒泡排序是數(shù)據(jù)兩兩比較，將小的交換到前面，每趟排序將最大的排序到最后面，假設有n個數(shù)據(jù)，只用進行n-1趟排序，同時我們還要注意每趟排序的比較次數(shù)是不同的，第一輪，所有數(shù)據(jù)都要排序，就是n-1輪比較，第二輪比較的時候，最大的數(shù)據(jù)已經到了正確的位置，所以第二輪就只有n-2個數(shù)據(jù)比較。
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//冒泡排序
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)//比較的趟數(shù)
{
for (int j = 0; j < n - i - 1; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
}
}
}
}上面的代碼就是我們的冒泡排序，但是如果經過第一輪交換后，數(shù)據(jù)就已經有序了，但是我們的程序還在上面一輪一輪比較，這樣效率較低，我們可以設置一個標志，如果經過一輪排序沒有數(shù)據(jù)交換，那就說明數(shù)據(jù)已經有序了。
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//冒泡排序
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1 ; i++)//比較的趟數(shù)
{
int flag = 1;//默認數(shù)據(jù)有序
for (int j = 0; j < n - i - 1; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
flag = 0;//數(shù)據(jù)無序
}
}
if (flag == 1)
break;
}
}冒泡排序的特性總結：
- 冒泡排序是一種非常容易理解的排序
- 時間復雜度：O(N^2)
- 空間復雜度：O(1)
- 穩(wěn)定性：穩(wěn)定
2.3.2快速排序
快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值key，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。
// 假設按照升序對array數(shù)組中[left, right)區(qū)間中的元素進行排序
void QuickSort(int array[], int left, int right)
{
//= 代表只剩下一個值
if (left >= right)
return;
// 按照基準值對array數(shù)組的 [left, right)區(qū)間中的元素進行劃分
int div = PartSort(array, left, right);
// 劃分成功后以div為邊界形成了左右兩部分 [left, div-1) 和 [div+1, right)
// 遞歸排[left, div-1)
QuickSort(array, left, div-1);
// 遞歸排[div+1, right)
QuickSort(array, div + 1, right);
}上述為快速排序遞歸實現(xiàn)的主框架，發(fā)現(xiàn)與二叉樹前序遍歷規(guī)則非常像，同學們在寫遞歸框架時可想想二叉樹前序遍歷規(guī)則即可快速寫出來，后序只需分析如何按照基準值來對區(qū)間中數(shù)據(jù)進行劃分的方式即可。
單趟排序
//1. hoare版本
int PartSort(int* a, int left, int right)
{
int key = a[left];
while (left < right)
{
//右邊找小
while (a[right] > key)
{
right--;
}
//左邊找大
while (a[left] < key)
{
left++;
}
Swap(&a[left], &a[right]);
}
//key和相遇位置交換
Swap(&key, &a[left]);
return left;
}我們看看上面的代碼有問題沒？我們來看看下面的圖。
很明顯，根據(jù)我們上面的代碼，當key和a[left]、a[right]相等的時候，程序是不是就卡死啦。所以我們需要修改上面的循環(huán)條件key和a[left]、a[right]相等的時候，left和right的值都要改變。
//1. hoare版本
int PartSort(int* a, int left, int right)
{
int key = a[left];
while (left < right)
{
//右邊找小
while (a[right] >= key)
{
right--;
}
//左邊找大
while (a[left] <= key)
{
left++;
}
Swap(&a[left], &a[right]);
}
//key和相遇位置交換
Swap(&key, &a[left]);
return left;
}我們再看看上面的代碼還有問題沒？我們來看看下面的圖。
如果a[right]的值都大于key，那么right會一直減，最后就會越界的問題；同樣a[left]的值都大于key，那么left會一直加，最后就會越界的問題。
//1. hoare版本
int PartSort(int* a, int left, int right)
{
int key = a[left];
while (left < right)
{
//右邊找小
while (left < right && a[right] >= key)
{
right--;
}
//左邊找大
while (left < right && a[left] <= key)
{
left++;
}
Swap(&a[left], &a[right]);
}
//key和相遇位置交換
Swap(&key, &a[left]);
return left;
}我們再看看上面的代碼還有問題沒？我們來看看下面的圖。
當最后right和left相遇的時候，此時執(zhí)行Swap(&key, &a[left])，但是只是和key這個局部變量交換，并不是和數(shù)組里面的內容交換，數(shù)組里面的那個key值元素沒有變化，我們可以通過下標去實現(xiàn)數(shù)組內容的交換。
//1. hoare版本
int PartSort(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
//右邊找小
while (left < right && a[right] >= a[keyi])
{
right--;
}
//左邊找大
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
//key和相遇位置交換
Swap(&a[keyi], &a[left]);
return left;
}這里有一個疑問？為什么相遇的地方的值比key值一定小呢？怎么做到的呢？？？右邊先走才能做到相遇的地方的值比key值一定小。
相遇情況：
- 如果左邊先走，相遇位置是R的位置，L和R在上一輪交換過，交換后R的位置一定比key大，此時和key交換沒有意義。
- 如果R先走找到比key小的值停下來了，然后L再走，找比key大的值，沒有找到和R相遇了，相遇位置比key小，交換之后滿足左邊值比key小，右邊比key大。
上面的hoare版本有很多的坑，下面我們來換一種寫法：挖坑法
//挖坑法
int PartSort1(int* a,int left,int right)
{
int key = a[left];//保存key值，形成第一個坑位
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;
}
//相遇的位置放key
a[hole] = key;
return hole;
}除了上面的這種寫法，我們還有一張前后指針法。cur找小，找到之后讓prev加加，再交換cur和prev處的值，prev在這里有兩種情況，在cur還沒遇到比key大的值得時候，此時prev緊跟cur，在cur遇到比key大的值的時候，prev在比key大的一組值得前面。本質是：把一段大于key的區(qū)間往右推，同時把小的甩到左邊。
//前后指針版本
int PartSort(int* a,int left,int right)
{
int cur = left + 1;
int prev = left;
int keyi = left;
while(cur < right + 1)
{
if(a[cur] < a[keyi] && cur != prev)
{
Swap(&a[cur],&a[++prev]);
}
cur++;
}
Swap(&a[keyi],&a[prev]);
return prev;
}其實我們上面的三種快速排序遇到有一種情況就會對時間的消耗巨大，在利扣上運行就會出現(xiàn)超出時間限制的錯誤，什么情況呢？如果我們要排序的數(shù)是一組數(shù)據(jù)量極大的重復數(shù)字，此時的三數(shù)取中就沒有任何意義，且上面三個版本的寫法都不能處理這個問題，拿上面的hoare版本來說，如果是一組重復數(shù)據(jù)，hoare每次都是從右邊先開始以此往左邊找比keyi小的值，但是此時數(shù)組中的值都是一樣的，找不到比keyi小的值，只能keyi就只能和right交換，我們想想，如果是一組數(shù)據(jù)重復極大的值，每次都要這樣，消耗的時間是非常巨大的。因此這里可以使用第四種寫法，三路劃分：把小于key往左推，等于key換到中間，大于key的往右推。
三路劃分：
- 1.cur小于key時，交換cur和left位置的值，然后再++cur，++left。
- 2.cur等于key時，直接++cur。
- 3.cur大于key時，交換cur和right位置的值，這里不能直接++cur，因為交換cur和right位置的值之后，此時不清楚cur位置與key位置值得大小關系，需要先--right，然后再比較cur位置與key位置值得大小關系。
結束條件：cur > right
根據(jù)上面的算法，要排序的數(shù)是一組數(shù)據(jù)量極大的重復數(shù)字，此時就是上面的第二種寫法，此時一直++cur就可以排序好這個數(shù)組，時間復雜度就是O(N)。
void PartSort(int *a,int left,int right)
{
if(left >= left)
return;
// 三數(shù)取中
int midi = GetMidi(a,left,right);
Swap(&a[midi],&a[left]);
int begin = left;
int end = right;
int key = left;
int cur = left;
while(cur <= right)
{
if(a[key] > a[cur])
{
Swap(&a[key],&a[left]);
++cur;
++left;
}
else if(a[key == a[cur])
{
++cur;
}
else
{
Swap(&a[key],&a[right]);
--right;
}
}
// [begin,left-1][left,right][right+1,end]
PartSort(a,begin,left-1);
PartSort(a,right+1,end);
}我們現(xiàn)在再來想一下快排的效率，當數(shù)組的數(shù)據(jù)每次交換后，key就是中間位置，那么此時的時間復雜度就是O(N*logN)，但是當數(shù)組數(shù)據(jù)有序的時候，key每次就是第一個位置，那么此時的時間復雜度就是O(N^2)，那么此時怎么優(yōu)化呢？？？
1. 三數(shù)取中法選key
2. 遞歸到小的子區(qū)間時，可以考慮使用插入排序
三數(shù)取中法選key：有了三數(shù)取中，快排就不會出現(xiàn)最壞情況。
//三數(shù)取中
int GetMidi(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] < a[mid])
{
if (a[right] > a[mid])
{
return mid;
}
else if(a[right] < a[left]) //mid最大
{
return left;
}
else
{
return right;
}
}
else //a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] > a[right]) //mid最小
{
return right;
}
else
{
return left;
}
}
}
int PartSort(int* a, int left, int right)
{
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
......//三種PartSort任意一種
}根據(jù)完全二叉樹的特點，最后一層的節(jié)點個數(shù)占總數(shù)的50%。對比到快速排序的遞歸而言，遞歸層數(shù)越深，每層遞歸的次數(shù)變多，消耗也是越大的。我們拿10個數(shù)據(jù)對比一下：
?我們要快速排序10個數(shù)，就要遞歸3層，消耗太多，非常的不劃算。因此遞歸到小的子區(qū)間時，可以考慮使用插入排序。該小區(qū)間就可以設置為只剩下10個數(shù)時候開始使用直接插入排序，最后一層的節(jié)點個數(shù)占總數(shù)的50%，倒數(shù)第二層的節(jié)點個數(shù)占總數(shù)的25%，倒數(shù)第三層的節(jié)點個數(shù)占總數(shù)的12.5%，根據(jù)上面的計算，能優(yōu)化87.5%遞歸算法。
遞歸到小的子區(qū)間時，可以考慮使用直接插入排序。
// 假設按照升序對array數(shù)組中[left, right)區(qū)間中的元素進行排序
void QuickSort(int array[], int left, int right)
{
//= 代表只剩下一個值
if (left >= right)
return;
//將剩下的10個元素進行直接插入排序
if ((right - left + 1) > 10)
{
// 按照基準值對array數(shù)組的 [left, right)區(qū)間中的元素進行劃分
int div = PartSort(array, left, right);
// 劃分成功后以div為邊界形成了左右兩部分 [left, div-1) 和 [div+1, right)
// 遞歸排[left, div-1)
QuickSort(array, left, div - 1);
// 遞歸排[div+1, right)
QuickSort(array, div + 1, right);
}
else
{
//指針+-跳過指向類型大小
InsertSort(array + left, right - left + 1);
}
}掌握了遞歸思路的快速排序，我們再來掌握一下非遞歸思路的快速排序，非遞歸的快速排序需要使用棧來解決。我們先處理左邊數(shù)據(jù)，再處理右邊數(shù)據(jù)，根據(jù)棧先進后出的特點，因此右邊數(shù)據(jù)先入棧，左邊數(shù)據(jù)再入棧。這里也可以使用隊列實現(xiàn)，不過隊列不是先處理左邊數(shù)據(jù)，再處理右邊數(shù)據(jù)而是是一層一層處理，所以這里我們不用隊列，使用棧能更好體現(xiàn)非遞歸的思路。
//導入之前寫的棧實現(xiàn)接口
#include "Stack.h"
void QuickSortNonR(int* a, int left, int right)
{
Stack st;
StackInit(&st);
//先進后出，先入右，再入左
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
int left = StackTop(&st);
StackPop(&st);
int right = StackTop(&st);
StackPop(&st);
int keyi = PartSort(a, left, right);
//分為三個區(qū)間：[left,keyi-1] keyi [keyi+1，right]
//先入右區(qū)間，再入左區(qū)間
if (keyi + 1 < right)
{
StackPush(&st, right);
StackPush(&st, keyi + 1);
}
if (left < keyi - 1)
{
StackPush(&st, keyi - 1);
StackPush(&st, left);
}
}
StackDestroy(&st);
}這里提出一個問題：遞歸是使用的系統(tǒng)棧，而上面的棧是使用的人工棧，棧的深度不是一樣的嘛，有什么區(qū)別？？？
人工棧是通過數(shù)組實現(xiàn)，是在堆上開辟的，而遞歸使用的系統(tǒng)棧，系統(tǒng)會自動為每個函數(shù)調用分配一幀。遞歸的棧深度受系統(tǒng)棧的限制，通常比人工棧小得多，系統(tǒng)棧很容易滿棧。
#include <stdio.h>
int Func(int n)
{
if (n == 0)
return 0;
return Func(n - 1) + n;
}
int main()
{
printf("%d\n", Func(10000));
return 0;
}
我們可以看到當n為5215時，我們的系統(tǒng)棧就滿了，遞歸是由消耗的，所以掌握非遞歸的快速排序是非常有意義的。
快速排序的特性總結：
- 1.快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
- 2.時間復雜度：O(N*logN)
- 3.空間復雜度：O(logN)
- 4.穩(wěn)定性：不穩(wěn)定
2.4 歸并排序
2.4.1基本思想
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。 歸并排序核心步驟：
2.4.2歸并排序
我們這里的歸并是讓小區(qū)間數(shù)據(jù)有序，先將數(shù)組分為若干小區(qū)間，然后將小區(qū)間的數(shù)按照從小到大的順序尾插到tmp數(shù)組中，再拷貝回原數(shù)組，之后再讓兩個小區(qū)間的數(shù)尾插插到tmp數(shù)組中，再拷貝回原數(shù)組......依次，直至整個數(shù)組有序。
//為防止每次遞歸調用都會malloc空間，這里寫一個子函數(shù)
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (right <= left)
return;
int mid = (right + left) / 2;
//分割
//[left,mid] [mid+1,right]
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
//歸并到tmp數(shù)組，再拷貝回去
// a->[left,mid] [mid+1,right]->tmp
int begin1= left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = left;
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++];
}
//把tmp的數(shù)組歸并到原數(shù)組上
memcpy(a + left, tmp + left, (right - left + 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, 0, n - 1, tmp);
free(tmp);
}遞歸圖：
上面的快速排序我們寫了非遞歸的寫法，它是一種很明顯的前序方法，左邊排完序就不需要再管了，而這里的歸并是否也有非遞歸的寫法呢？很明顯，歸并排序當人也有非遞歸的寫法，但是我們這里的歸并是一種后序，排完左邊的序列還需要回到根，比如上面的 10 6 7 1，左邊排序完是 6 10，右邊排序完是 1 7，其序列還未有序，需要回到根后再排序，比較麻煩，這里我們就不使用棧的方法呢？這里我們可以借鑒一下斐波那契數(shù)列的非遞歸的方法。
我們怎么才能實現(xiàn)上面的歸并呢？我們可以定義一個gap，通過gap確定每次排序的區(qū)間。我們先來實現(xiàn)一下一一歸并的寫法。
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1;
//i的位置依次是0，2，4......
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;//[0,0]
int begin2 = i + gap,end2 = i + 2 * gap - 1;//[1,1]
//第一次一一歸并的兩個區(qū)間[0,0] [1,1]
//第二次一一歸并的兩個區(qū)間[2,2] [3,3]
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++];
}
//拷貝回原數(shù)組
memcpy(a + i, tmp + i, 2 * gap * sizeof(int));
}
free(tmp);
}所以我們只需要控制gap就可以實現(xiàn)非遞歸的歸并排序。gap的取值是1，2，4.......當gap小于數(shù)組的元素就停止。
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)
{
//i的位置依次是0，2，4......
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;//[0,0]
int begin2 = i + gap, end2 = i + 2 * gap - 1;//[1,1]
//第一次一一歸并的兩個區(qū)間[0,0] [1,1]
//第二次一一歸并的兩個區(qū)間[2,2] [3,3]
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++];
}
//拷貝回原數(shù)組
memcpy(a + i, tmp + i, 2 * gap * sizeof(int));
}
gap *=2;
}
free(tmp);
}上面的數(shù)據(jù)剛好是2的整個倍，可是如果數(shù)據(jù)是9個呢？
此時我們再進行歸并就會出現(xiàn)越界的問題。數(shù)據(jù)個數(shù)為9，下標為9及以上的都是越界。
此時每次歸并上都出現(xiàn)了越界的問題，越界的問題都出現(xiàn)再end1,begin2和end2上面。這里我們需要想一個問題，我們每次排序的數(shù)據(jù)必須成對出現(xiàn)才能歸并嘛？其實，如果數(shù)據(jù)不成對出現(xiàn)，我們就不要歸并這數(shù)據(jù)，因為它本身就是獨自出現(xiàn)，本身就可以當作有序。所以我們只用加下面的代碼就可以了。如果越界了，這組數(shù)據(jù)就不用管了，直接退出即可。但是當只有end2越界的時候，此時需要歸并，因為此時有兩組數(shù)據(jù)需要歸并。
//如果第二組不存在，這一組就不用歸并了
if (end1 >= n)
{
break;
}
//如果第二組的右邊界越界，修正下標
if (end2 >= n)
{
//此時需要歸并,只用修改下標即可
end2 = n - 1;
}同時我們還需要改一下memcpy拷貝的個數(shù)
memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));歸并排序的特性總結：
- 1. 歸并的缺點在于需要O(N)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
- 2. 時間復雜度：O(N*logN)
- 3. 空間復雜度：O(N)
- 4. 穩(wěn)定性：穩(wěn)定
2.5 非比較排序
思想：計數(shù)排序又稱為鴿巢原理，是對哈希直接定址法的變形應用。 操作步驟：
- 1. 統(tǒng)計相同元素出現(xiàn)次數(shù)
- 2. 根據(jù)統(tǒng)計的結果將序列回收到原來的序列中
上面的這種就是我們的計數(shù)排序，如果我們的數(shù)據(jù)是101、105、199，我們再通過上面的方法就要開辟200個空間大小的數(shù)組，就會存在很大的空間浪費，所以我們就要不能使用絕對映射（一個數(shù)據(jù)存在對應的下標下面），這里需要使用我們的相對映射（最大值-最小值獲取區(qū)間）（根據(jù)a[i] - min）就只用開辟相對較少的空間。
void CountSort(int* a, int n)
{
int max = a[0];
int min = 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);
if (count == NULL)
{
perror("malloc fail");
return;
}
memset(count, 0, sizeof(int) * range);
//統(tǒng)計數(shù)據(jù)出現(xiàn)的次數(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++] = i + min;
}
}
}計數(shù)排序的特性總結：
- 1. 計數(shù)排序在數(shù)據(jù)范圍集中時，效率很高，但是適用范圍及場景有限。
- 2. 時間復雜度：O(MAX(N,范圍))
- 3. 空間復雜度：O(范圍)?
- 4. 穩(wěn)定性：穩(wěn)定
- 5.局限性：只能排序整型數(shù)據(jù)
2.6內排序和外排序
內排序和外排序是計算機科學中與排序算法相關的兩個重要概念。
內排序（In-Place Sorting）：
- 內排序是指在排序過程中，所有數(shù)據(jù)都存儲在計算機的內存中進行排序的方法。
- 這意味著排序算法不需要使用外部存儲（如硬盤或其他存儲設備）來存儲數(shù)據(jù)。
- 內排序的優(yōu)點是速度較快，因為內存訪問通常比外部存儲快得多。
- 常見的內排序算法包括冒泡排序、選擇排序、插入排序、快速排序、歸并排序等。
外排序（External Sorting）：
- 外排序是指排序的數(shù)據(jù)量太大，無法完全放入計算機的內存中，因此需要使用外部存儲設備來輔助排序的方法。
- 外排序通常涉及到將大量數(shù)據(jù)分割成較小的塊，分別在內存和外部存儲之間進行排序，然后再將這些排序好的塊合并起來以獲得最終的有序結果。
- 外排序的主要應用場景是處理大型數(shù)據(jù)集，如數(shù)據(jù)庫排序、外部存儲設備上的大文件排序等。
- 常見的外排序算法包括歸并排序、多路歸并排序等。
假設我們當前的內存是1G，當我們要排序一個10億個整型數(shù)據(jù)的時候，要怎么排序呢？
- 10億個整型數(shù)據(jù)?= 1024 * 1024 *1024 Byte * 4 = 4G > 內存1G，在內存中無法排序。
- 4G的整型數(shù)據(jù)太大而無法一次性加載到內存中，需要使用外排序。
- 外排序通常涉及將數(shù)據(jù)分成多個小塊，每個小塊可以適應內存大小。
- 首先，將數(shù)據(jù)分塊并逐塊加載到內存中，對每個塊使用內排序算法進行排序。
- 排序后的塊可以寫回磁盤或者合并成更大的塊。
- 最后，進行塊之間的合并操作，以獲得最終排序結果。
3.排序算法復雜度及穩(wěn)定性分析?
穩(wěn)定性：相同的數(shù)據(jù)進行排序后，其相對位置沒有發(fā)生變化，就說明該排序具有穩(wěn)定性。
4.選擇題練習
1. 快速排序算法是基于（ ）的一個排序算法。
A分治法
B貪心法
C遞歸法
D動態(tài)規(guī)劃法
解析：快速排序是基于分治法的一個排序算法。
2.對記錄（54,38,96,23,15,72,60,45,83）進行從小到大的直接插入排序時，當把第8個記錄45插入到有序表時，為找到插入位置需比較（ ）次？（采用從后往前比較）
A 3
B 4
C 5
D 6
解析：第8個記錄45插入到有序表時，前7個數(shù)據(jù)已經有序（15,23,38,54,60,72,96)，次數(shù)依次向前比較，需要比較5次。
3.以下排序方式中占用O（n）輔助存儲空間的是
A 簡單排序
B 快速排序?
C 堆排序
D 歸并排序
解析：歸并排序需要將小區(qū)間排序的結果保存下來，然后再拷貝到原數(shù)組上
4.下列排序算法中穩(wěn)定且時間復雜度為O(n2)的是（ ）
A 快速排序
B 冒泡排序
C 直接選擇排序
D 歸并排序
5.關于排序，下面說法不正確的是
A 快排時間復雜度為O(N*logN)，空間復雜度為O(logN)
B 歸并排序是一種穩(wěn)定的排序,堆排序和快排均不穩(wěn)定
C 序列基本有序時，快排退化成冒泡排序，直接插入排序最快
D 歸并排序空間復雜度為O(N), 堆排序空間復雜度的為O(logN)
6.下列排序法中，最壞情況下時間復雜度最小的是（ ）
A 堆排序
B 快速排序
C 希爾排序
D 冒泡排序
7.設一組初始記錄關鍵字序列為(65,56,72,99,86,25,34,66)，則以第一個關鍵字65為基準而得到的一趟快速排序結果是（）
A 34，56，25，65，86，99，72，66
B 25，34，56，65，99，86，72，66
C 34，56，25，65，66，99，86，72
D 34，56，25，65，99，86，72，66
解析：這里采用的是挖坑法，右邊先找小，左邊再找到，最后將關鍵字65放到坑位。
文章來源：http://www.zghlxwxcb.cn/news/detail-712981.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-712981.html
到了這里，關于【探索排序算法的魅力：優(yōu)化、性能與實用技巧】的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
