目錄
一、直接插入排序
二、希爾排序
三、選擇排序
?3.1、簡單選擇排序
?3.2、快速選擇排序(Top K問題)
四、堆排序
五、冒泡排序
六、快速排序
??1、遞歸版本
? ? ?1.1 hoare 法
? ? ?1.2 挖坑法
? ? ?1.3 前后指針法
? 2、非遞歸版本
? 3、快速排序的優(yōu)化
? ? ?3.1 三數(shù)取中
? ? ?3.2 小區(qū)間優(yōu)化
七、歸并排序
? 1、遞歸版本
? 2、非遞歸版本
八、計數(shù)排序
九、排序的比較：
一、直接插入排序
動圖演示：
思路：(1)首先先按一趟插入排序編寫，?數(shù)組的最后一個元素為 end，將要插入數(shù)據(jù)就是臨時數(shù)據(jù)tmp = a[end+1]，如果 tmp 小于 end 位置的數(shù)據(jù)，就將 end 位置的數(shù)據(jù)往后挪到 end+1的位置，直到插入到里面；(2)再按整體插入排序，進行插入，假設(shè)第一次數(shù)組里面就一個數(shù)據(jù)，所以 end 位置就是0，然后結(jié)束條件就是小于 n-1，否則就越界。
注意：先保存一下 end+1 位置的數(shù)據(jù)，否則在挪動的時候，就會被覆蓋。
?
上面給出了兩個動圖演示，能更好的理解。
//插入排序 時間復(fù)雜度：O(N^2)
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}二、希爾排序
希爾排序可以縮小增量排序，又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數(shù)，把待排序文件中所有記錄分成 幾個 組，所有距離為的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進行排序。然后，取，重復(fù)上述分組和排序的工 作。當?shù)竭_ gap=1時，所有記錄在統(tǒng)一組內(nèi)排好序。?
希爾排序的特性總結(jié)：
- 希爾排序是對直接插入排序的優(yōu)化。
- 當gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就 會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。
- 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算，因此在好多樹中給出的希爾排序的時間復(fù)雜度都不固定。
//希爾排序 時間復(fù)雜度:O(N^1.3)
void ShellSort(int* a, int n)
{
//gap > 1 預(yù)排序
//gap越大，大的數(shù)可以更快的到后面，小的數(shù)可以更快的到前面。越不接近有序。
//gap越小，數(shù)據(jù)跳動越慢，越接近有序。
//gap == 1 直接插入排序
int gap = n;
while (gap > 1)
{
gap = gap / 2;
//gap = gap / 3 + 1;
for (int j = 0; j < gap; j++)//分gap組排序
{
for (int i = j; i < n - gap; i += 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;
}
}
}
}三、選擇排序
?3.1、簡單選擇排序
動圖演示：
思路：設(shè)兩個變量mini，maxi分別存最小數(shù)據(jù)位置的下標和最大位置數(shù)據(jù)的下標，每次遍歷數(shù)組標記出最大數(shù)據(jù)的下標和最小位置數(shù)據(jù)的下標，分別將其與最后一個數(shù)據(jù)和開頭數(shù)據(jù)進行交換。
//選擇排序 時間復(fù)雜度：O(N^2)
//和直接插入排序相比，插入排序更好
//插入適應(yīng)性很強，對于有序，局部有序，都能效率提升
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin + 1; i <= end; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
//此時，已經(jīng)選出了最大的，和最小的
//位置交換
Swap(&a[begin], &a[mini]);
//begin跟maxi重疊了，第一步交換之后maxi位置變了
if (maxi == begin)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
注意：這種情況是特殊情況，最大值的位置(maxi)在 begin 處，交換完 a[begin] 和 a[mini] 時，此時 ，maxi 位置被交換到 mini 的位置了，所以 maxi 的位置發(fā)生了變化，需要我們處理一下 maxi 的位置。
?3.2、快速選擇排序(Top K問題)
快速選擇排序和快速排序算法有很大的相似之處，將問題的規(guī)模一次次的減小，直到求出最終解，時間復(fù)雜度為：O(N)，且快速選擇排序算法不要求數(shù)據(jù)有序。
目的：找到第K大的數(shù)
- 出口條件為left == right，并返回值;
- 對 left 到 right 區(qū)間進行快排操作，注意分界條件，與快排相同;
- 在遞歸調(diào)用時，我們不需要對左右兩邊都進行調(diào)用，只需要判斷我們選擇的數(shù) k 在左邊還是在右邊，然后只調(diào)用 k 所在的區(qū)間即可。
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100;
int x[N];
int n, k;
int QuickSelect(int a[], int left, int right, int k)
{
if (left >= right)
{
return a[k];
}
int mid = a[(left + right) / 2], i = left - 1, j = right + 1;
while (i < j)
{
while (a[++i] < mid);
while (a[--j] > mid);
if (i < j)
swap(a[i], a[j]);
}
if (j >= k)
{
return QuickSelect(a, left, j, k);
}
else
{
return QuickSelect(a, j + 1, right, k);
}
}
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> x[i];
cout << QuickSelect(x, 0, 9, k - 1) << endl;
}四、堆排序
堆排序是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。本文建的是大堆，排升序。
//堆排序 時間復(fù)雜度：O(N*logN)
//交換
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下調(diào)整
void AdjustDown(int* a, int n, int parent)//n為數(shù)組的大小
{
int child = parent * 2 + 1;//左孩子
while (child < n)
{
//確認child指向大的那個孩子
if (child + 1 < n && a[child + 1] > a[child])//child+1 < n 右孩子存在的情況
{
++child;//默認指向左孩子，++child就指向右孩子
}
//孩子大于父親，交換，繼續(xù)向下調(diào)整
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;//孩子小于父親，跳出循環(huán)
}
}
}
void HeapSort(int* a, int n)
{
//向下調(diào)整建堆--- O(N) --- 好一點
//升序:建大堆
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
//O(N*logN)
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}五、冒泡排序
動圖演示：
思路：前后數(shù)據(jù)進行對比，若前面數(shù)據(jù)大于后面的數(shù)據(jù)就交換，這樣經(jīng)過第一輪的排序，最大值就被換到了最后的位置，然后再進行第二輪排序，這樣以此往復(fù)，第二大的數(shù)據(jù)被放到倒數(shù)第二的位置，直到所有數(shù)據(jù)排序完畢。
//冒泡排序 時間復(fù)雜度：O(N^2)
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;
}
}
}六、快速排序
基本思想為：任取待排序元素序列中 的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右 子序列中所有元素均大于基準值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。
快速排序的階段性結(jié)果特點：第 i 趟完成時，會有 i 個以上的數(shù)據(jù)出現(xiàn)在它最終要出現(xiàn)的位置。
??1、遞歸版本
? ? ?1.1 hoare 法
?動圖演示：
思路：(1)選取key位置，通常選在最開始的left位置(或最后面right位置)。
? ? ? ? ? ? (2)如果key選在left位置，則 right 先走，找到比 key 位置小的數(shù)據(jù)停下。
? ? ? ? ? ? (3)left 再走，找到比 key 位置大的數(shù)據(jù)停下。
? ? ? ? ? ? (4)交換 left 和 right 位置的數(shù)據(jù)，一直重復(fù)以上操作，直到left 和 right 相遇結(jié)束。
? ? ? ? ? ? (5)相遇結(jié)束后，此時交換 key 位置和 left 位置(就是相遇的位置)的數(shù)據(jù)， 這個時候相遇位置的左邊的數(shù)據(jù)小于等于相遇位置的數(shù)據(jù)，右邊的數(shù)據(jù)大于等于相遇位置的數(shù)據(jù)。所以，這個數(shù)據(jù)就調(diào)整到了它的正確位置。
//Hoare
int PartSort1(int* a, int begin, int end)
{
int left = begin, right = end;
int key = left;
while (left < right)
{
//右邊先走，找小
while (left < right && a[right] >= a[key])//left < right條件是防止越界
{
right--;
}
//左邊再走，找大
while (left < right && a[left] <= a[key])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[key]);
key = left;
return key;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
if ((end - begin + 1) < 15)
{
//優(yōu)化方法:小區(qū)間用直接插入替代，減少遞歸調(diào)用次數(shù)
InsertSort(a + begin, end - begin + 1);
}
else
{
int key = PartSort1(a, begin, end);
//[begin,key-1] key [key+1 , end] 三段位置
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
}
? ? ?1.2 挖坑法
?動圖演示：
思路：(1)把數(shù)組 left 位置的數(shù)據(jù)賦值給 key ，形成了第一個坑位 hole 就是 left 位置，要保存 key 位置的值。
? ? ? ? ? ?(2)right 先走，找到比 key 位置數(shù)據(jù)小的值，就停下，將此處的數(shù)據(jù)放到坑位 hole 中，此時right 位置就形成了新的坑位。
? ? ? ? ? ?(3)然后 left 再走，找到比 key 位置數(shù)據(jù)大的值，就停下，將此處的數(shù)據(jù)放到坑位 hole 中，此時，left 位置就形成新的坑位。
? ? ? ? ? ?(4)當 left 和 right 相遇時，將 key 位置的數(shù)據(jù)放入到坑位中，此時，key 數(shù)據(jù)就放到了正確的位置。
//挖坑法
int PartSort2(int* a, int begin, int end)
{
int left = begin, right = end;
int key = left;
int hole = left;
while (left < right)
{
//右邊找小，填到左邊的坑里面
if (left < right && a[right] >= a[key])
{
right--;
}
a[hole] = a[right];
hole = right;
//左邊找大，填到右邊的坑里面
if (left < right && a[left] <= a[key])
{
left++;
}
a[hole] = a[left];
hole = left;
}
a[hole] = a[key];
return hole;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
if ((end - begin + 1) < 15)
{
//優(yōu)化方法:小區(qū)間用直接插入替代，減少遞歸調(diào)用次數(shù)
InsertSort(a + begin, end - begin + 1);
}
else
{
int key = PartSort2(a, begin, end);
//[begin,key-1] key [key+1 , end] 三段位置
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
}? ? ?1.3 前后指針法
?動圖演示：
思路：(1)首先假設(shè) key 是數(shù)組最開始位置，然后用前后指針法，prev 指向第一個元素，cur 指向第二個元素。
? ? ? ? ? ?(2)cur 先移動，找到比 key 位置數(shù)據(jù)小的停下。
? ? ? ? ? ?(3)++prev，交換 prev 與 cur 位置的數(shù)據(jù)。
? ? ? ? ? ?(4)當 cur 指向數(shù)組最后一個位置的下一個位置時，循環(huán)停止。
? ? ? ? ? ?(5)交換 key 下標與 prev 下標的數(shù)據(jù)。
//前后指針法
int PartSort3(int* a, int begin, int end)
{
int prev = begin;
int cur = begin + 1;
int key = begin;
while (cur <= end)
{
//找到比key小的值時，跟++prev位置交換，小的往前翻，大的往后翻
while (a[cur] < a[key] && ++prev != cur)
{
//滿足條件，進行交換
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[key], &a[prev]);
key = prev;
return key;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
if ((end - begin + 1) < 15)
{
//優(yōu)化方法:小區(qū)間用直接插入替代，減少遞歸調(diào)用次數(shù)
InsertSort(a + begin, end - begin + 1);
}
else
{
int key = PartSort3(a, begin, end);
//[begin,key-1] key [key+1 , end] 三段位置
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
}? 2、非遞歸版本
思路：通過非遞歸的方式實現(xiàn)的話，我們要借助棧的內(nèi)存結(jié)構(gòu)讓先入的后出，所以要先進?begin 再進 end，出的順序就是先出右再出左再先排右邊再排左邊。
//非遞歸版本
void QuickSortNonR(int* a, int begin, int end)
{
//借助棧實現(xiàn)非遞歸
ST st;
StackInit(&st);
StackPush(&st, begin);
StackPush(&st, end);
while (!StackEmpty(&st))
{
int right = StackTop(&st);
StackPop(&st);
int left = StackTop(&st);
StackPop(&st);
int key = PartSort1(a, left, right);
//[left,key-1] key [key+1,right]
if (key + 1 < right)
{
StackPush(&st, key + 1);
StackPush(&st, right);
}
if (left < key - 1)
{
StackPush(&st, left);
StackPush(&st, key - 1);
}
}
StackDestory(&st);
}? 3、快速排序的優(yōu)化
? ? ?3.1 三數(shù)取中
三數(shù)取中是一種優(yōu)化算法，為了防止 key 位置的數(shù)據(jù)是該數(shù)組中的最小值，進行一趟快速排序后，沒有什么變化，我們采用的三數(shù)取中的方法，在一個數(shù)組中選取一個中間值作為 key ，來進行快速排序，這樣的效率會大大的提升。
int GetMidIndex(int* a, int begin, int end)
{
int mid = (begin + end) / 2;
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
{
return mid;
}
else if (a[begin] > a[end])
{
return begin;
}
else
{
return end;
}
}
else //a[begin] > a[mid]
{
if (a[mid] > a[end])
{
return mid;
}
else if (a[begin] > a[end])
{
return end;
}
else
{
return begin;
}
}
}? ? ?3.2 小區(qū)間優(yōu)化
快排的思想就是不斷地分割小序列，然后再遞歸實現(xiàn)，它的每一層的遞歸次數(shù)以2倍的次數(shù)進行增長。當元素較多時以遞歸的方法實現(xiàn)是不錯的，但是當序列元素較少時，再使用遞歸就沒有必要了，我們可以選擇使用其他的排序方法來實現(xiàn)小序列的排序。
void QuickSort1(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
if ((end - begin + 1) < 10)
{
InsertSort(a, (end - begin + 1));
}
int mid = GetMidIndex(a, begin, end);
swep(&a[begin], &a[mid]);
int keyi = PartSort3(a, begin, end);
QuickSort1(a, begin, keyi - 1);
QuickSort1(a, keyi+1, end);
}
七、歸并排序
? 1、遞歸版本
?動圖演示：
歸并的思想：
? ? ? ? 歸并排序是建立在?歸并操作上的一種有效的排序算法,該算法是采用分治法的一個非常典型的應(yīng)用。
? ? ? ? 將已有序的子序列合并，得到完全有序的序列；
????????即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
//歸并排序 時間復(fù)雜度：O(N*logN) 空間復(fù)雜度：O(N)
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin >= end)
{
return;
}
int mid = (begin + end) / 2;
//[begin,mid] [mid+1,end] 遞歸讓子區(qū)間有序
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid + 1, end, tmp);
//歸并
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
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++];
}
memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}? 2、非遞歸版本
?我們就控制每個區(qū)間就可以歸并了，因為歸并是二分。
rangeN 表示：每組歸并的數(shù)據(jù)個數(shù)。
//非遞歸歸并排序
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
//歸并每組數(shù)據(jù)個數(shù)，從1開始，因為1個認為是有序的，可以直接歸并
int rangeN = 1;
while (rangeN < n)
{
for (int i = 0; i < n; i += rangeN * 2)
{
//[begin1,end1] [begin2,end2] 歸并
int begin1 = i, end1 = i + rangeN - 1;
int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;
int j = i;
//end1 begin2 end2越界
if (end1 >= n)
{
break;
}
else if (begin2 >= n)//begin2 end2 越界
{
break;
}
else if (end2 >= n)//end2 越界
{
//修正區(qū)間
end2 = n - 1;
}
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
//歸并一部分，拷貝一部分
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
rangeN *= 2;
}
free(tmp);
tmp = NULL;
}注意：寫代碼時，需要嚴密的控制區(qū)間，要不然會發(fā)生溢出，導(dǎo)致程序崩潰。
有以下三種情況：(1)end1越界，begin2越界，end2越界;(2)begin2越界，end2越界;(3)end2越界
八、計數(shù)排序
計數(shù)排序的核心思想：其實就是映射，將待排序的數(shù)據(jù)通過映射，放到輔助空間相對應(yīng)的位置，然后通過統(tǒng)計出現(xiàn)的次數(shù)，最后再放回原先的數(shù)組。
//計數(shù)排序
void CountSort(int* a, int n)
{
assert(a);
int min = a[0];
int max = a[0];
for (int i = 1; i < n; ++i)
{
//求最大值和最小值
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int range = max - min + 1;
int* countArr = (int*)malloc(sizeof(int) * range);
memset(countArr, 0, sizeof(int) * range);
//統(tǒng)計次數(shù)
for (int i = 0; i < n; ++i)
{
countArr[a[i] - min]++;
}
//排序
int index = 0;
for (int j = 0; j < range; ++j)
{
while (countArr[j]--)
{
//相對位置
a[index++] = j + min;
}
}
free(countArr);
}九、排序的比較：
| 排序方法 | 時間復(fù)雜度 | 空間復(fù)雜度 | 穩(wěn)定性 |
| 冒泡排序 | 穩(wěn)定 | ||
| 選擇排序 | 不穩(wěn)定 | ||
| 插入排序 | 穩(wěn)定 | ||
| 希爾排序 | 不穩(wěn)定 | ||
| 堆排序 | 不穩(wěn)定 | ||
| 歸并排序 | 穩(wěn)定 | ||
| 快速排序 | 不穩(wěn)定 | ||
| 計數(shù)排序 | 不穩(wěn)定 |
本文要是有不足的地方，歡迎大家在下面評論，我會在第一時間更正。文章來源：http://www.zghlxwxcb.cn/news/detail-490744.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-490744.html
?老鐵們，記著點贊加關(guān)注!!!??
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】八大排序算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
