資料結構：排序演算法
前言
本文總結了常用的九種內部排序演算法，因作者水平有限，多有謬誤，歡迎批評指正，
注：文中陣列皆從1開始，沒有用0，默認升序排列，
另：轉載請注明出處，
分類
按時間復雜度
-
普通演算法 \(O(n^2)\)
- 直接插入排序
- 二分插入排序
- 冒泡排序
- 直接選擇排序
-
先進演算法 \(O(n\log n)\)
- 快速排序
- 堆排序
- 選擇排序
-
特例
- 希爾排序，\(O(n^{1.3 \sim 2})\)
- 基數排序，\(O(dn)\)，其中\(d\)為元素的最大位數
按排序種類
- 插入排序
- 直接插入排序
- 二分插入排序
- 希爾排序
- 交換排序
- 冒泡排序
- 快速排序
- 選擇排序
- 直接選擇排序
- 堆排序
- 歸并排序
- 基數排序
按演算法穩定性
- 穩定演算法
- 直接插入排序
- 二分插入排序
- 冒泡排序
- 歸并排序
- 基數排序
- 不穩定演算法
- 希爾排序
- 快速排序
- 直接選擇排序
- 堆排序
直接插入排序
演算法思想
設待排序序列為\(T\)，排序序列為\(S\)，
從\(T\)中依次選取，加入\(S\)中，
設選取元素為\(T_i\in T\)，將\(x\)與\(S\)中的元素\(S_j\)依次比較，
如果\(T_i\)大于\(S_j\)，則\(j=j+1\)；否則將\(S_j\)以及往后的元素后移一位，\(T_i\)作為新的\(S_j\)，
代碼
//優化寫法
void StraightInsertionSort()
{
for (int i = 2; i <= n; i++)
{
for (int j = i - 1; j >= 1 && a[j] > a[j + 1]; j--)
{
swap(a[j], a[j + 1]);
}
}
}
二分插入排序
演算法思想
在直接插入排序中，\(S_j\)是依次選取的，而\(S\)本來已經是有序序列，那么就可以用二分查找的方式，確定\(T_i\)應該插入到的位置，
代碼
void BinaryInsertionSort()
{
for (int i = 2; i <= n; i++)
{
int l = 1, r = i, m;
while (l <= r)
{
m = (l + r) / 2;
if (a[i] > a[m])
{
l = m + 1;
}
else
{
r = m - 1;
}
}
for (int j = i - 1; j > r; j--)
{
swap(a[j], a[j + 1]);
}
}
}
希爾排序
演算法思想
希爾排序作為直接插入排序的改進，其思想是，將序列\(T\)進行分組，或者說，按一定的增量選取元素，而不是依次選取，將分組的元素進行排序，不斷細分分組再排序，最終得到整體有序序列，
由于分組方法/增量的選取不同，希爾排序的演算法時間復雜度也會相應改變，通常選取的為希爾增量，即開始選取序列長度的一半，每次排序后都折半，
可見希爾增量為1時的特殊情況，就是直接插入排序，
代碼
//加增量后，分組直接插入排序，
void ShellSort()
{
printf("Mark: Here we use the Shell Increment.\n");
for (int d = n / 2; d >= 1; d /= 2)
{
/*
* for (int i = 1; i <= d; i++)
* {
* for (int j = i + d; j <= n; j += d)
* {
* for (int k = j - d; k >= 1 && a[k] > a[k + d]; k -= d)
* {
* swap(a[k], a[k + d]);
* }
* }
* }
*/
//寫法優化，少一個回圈，
for (int i = d + 1; i <= n; i++)
{
for (int j = i - d; j >= d && a[j] > a[j + d]; j -= d)
{
swap(a[j], a[j + d]);
}
}
}
}
冒泡排序
演算法思想
將無序序列\(T\)兩兩進行交換，進行多次（最多\(n-1\)次）即可得到有序序列\(S\)，
加個標志符判斷已經有序，就不用再排了，
代碼
//簡簡單單冒泡排序的優化版本，
void BubbleSort()
{
for (int i = 1; i <= n - 1; i++)
{
bool flg = 0;
for (int j = 1; j <= n - 1; j++)
{
if (a[j] > a[j + 1])
{
swap(a[j], a[j + 1]);
flg = 1;
}
else
{
continue;
}
}
if (!flg)
{
break;
}
else
{
continue;
}
}
}
快速排序
演算法思想
快速排序是對冒泡排序的一種改進，通常選取序列的第一個數作為一個標準值，大于它的放到右邊，小于它的放到左邊，這時候標準值在序列中的位置就是有序排列后的位置，再分別將左右子列進行同樣操作即可，
代碼運用遞推式寫法，
不具有演算法穩定性的原因是，標準值的選取是不一定的，這里只是方便起見選取了第一個，
代碼
void QuickSort(int l, int r)
{
if (l < r)
{
int tmp = a[l];
int il = l, ir = r;
while (l < r)
{
while (l < r && a[r] >= tmp)
{
r--;
}
if (a[r] < tmp)
{
swap(a[l], a[r]);
}
while (l < r && a[l] <= tmp)
{
l++;
}
if (a[l] > tmp)
{
swap(a[l], a[r]);
}
}
QuickSort(il, l - 1);
QuickSort(l + 1, ir);
}
else
{
return;
}
}
直接選擇排序
演算法思想
遍歷\(T\)，每次選取\(T_{i+1}\)到\(T_n\)之間最小的，將其與\(T_i\)交換，
代碼
//很簡單，
void SelectionSort()
{
for (int i = 1; i <= n - 1; i++)
{
int p = i;
for (int j = i + 1; j <= n; j++)
{
if (a[j] < a[p])
{
p = j;
}
}
swap(a[p], a[i]);
}
}
堆排序
演算法思想
先將無序序列構成一顆二叉樹，選取非葉子節點，將其調整成一個大根堆，此時將根節點與最后一個元素互換，再進行調整堆的結構，如此反復，
整個排序是利用了大根堆的性質，即根節點一定是整個堆中最大的元素，
代碼
void my_Heap(int A[], int len)
{
for (int i = len % 2 == 0?len / 2:len / 2 + 1; i >= 1; i--)
{
ajust_My_Heap(A, i, len);
}
for (int i = len; i > 1; i--)
{
swap(a[1], a[i]);
ajust_My_Heap(A, 1, i - 1);
//debug用
/*for(int j= 1;j<=len;j++)
* {
* j==len?printf("%d\n",a[j]):printf("%d ",a[j]);
* }
*/
}
}
void ajust_My_Heap(int A[], int i, int len)
{
int tmp = A[i];
for (int k = i * 2; k <= len; k = k * 2)
{
if (k + 1 <= len && A[k] < A[k + 1])
{
k++;
}
if (A[k] > tmp)
{
A[i] = A[k];
i = k;
}
else
{
break;
}
}
A[i] = tmp;
}
void HeapSort()
{
//STL寫法
//make_heap(&a[1], &a[n+1]);
//sort_heap(&a[1], &a[n+1]);
//或用手寫堆來進行操作
my_Heap(a, n);
}
歸并排序
演算法思想
兩路歸并排序是運用了分治思想，是將無序序列先進行分割，然后區域調整，然后合并，
合并的時候，如有\(S^1\)和\(S^2\)為兩個有序序列，要將其合并成有序序列\(S\)，\(S_1=\min\{S^1_1,S^2_1\}\)，如果\(S_1\)選取了\(S^1_1\)，那么\(S_2=\min\{S^1_2,S^2_1\}\)，如此進行下去，即可得到\(S\)，運用了\(S^1\)和\(S^2\)的有序性質，
代碼
void Two_MergeSort(int l, int r)
{
if (l == r)
{
return;
}
int m = (l + r) / 2;
Two_MergeSort(l, m);
Two_MergeSort(m + 1, r);
if ((r - l) == 1 && a[l] > a[r])
{
swap(a[l], a[r]);
}
else
{
int i = l, j = m + 1, p = l;
int b[n];
memset(b, 0, sizeof(b));
//核心代碼要好好理解寫法，即便知道了具體的演算法思想
while (i <= m && j <= r)
{
b[p++] = a[i] <= a[j] ? a[i++] : a[j++];
}
while (i <= m)
{
b[p++] = a[i++];
}
while (j <= r)
{
b[p++] = a[j++];
}
for (int k = l; k <= r; k++)
{
a[k] = b[k];
}
}
}
基數排序
演算法思想
對于很多個位數相同的數進行排序時，效率很高，
LSD基數排序是按照最低位優先法，將序列從低位開始，安排到十個佇列當中，十個佇列分別記錄他們的這一位數字，利用佇列的FIFO性質，進行收集，再將收集的序列，按更高一位，重復上述方法，一直進行到最高位，收集出來便是有序序列，
注意，一定是佇列，如果從最高位開始，應用佇列的性質是得不到逆序的，即MSD基數排序，應該換為用堆疊存盤，
代碼
void RadixSort()
{
//找出最大數位
int maxData = https://www.cnblogs.com/xsbzlx/p/a[1];
for (int i = 2; i <= n; i++)
{
if (a[i] > maxData)
{
maxData = a[i];
}
}
int l = 1;
int tmp = 10;
while (maxData >= tmp)
{
tmp *= 10;
l++;
}
int cnt[10];
int b[n];
int r = 1;
int k;
for (int i = 1; i <= l; i++, r *= 10)
{
memset(cnt, 0, sizeof(cnt));
for (int j = 1; j <= n; j++)
{
k = (a[j] / r) % 10;
cnt[k]++;
}
//前綴和來確定b[j]的位置，非常巧妙
for (int j = 1; j < 10; j++)
{
cnt[j] = cnt[j - 1] + cnt[j];
}
for (int j = n; j >= 1; j--)
{
k = (a[j] / r) % 10;
b[cnt[k]] = a[j];
cnt[k]--;
}
for (int j = 1; j <= n; j++)
{
a[j] = b[j];
}
}
return;
}
結語
完整代碼請戳此處，
點個關注不迷路，后續會有更多內容，不限于資料結構，更有PDE、Complex Analysis等重磅內容，
謝謝朋友們！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/228738.html
標籤：其他
上一篇：線性表結構：單向鏈表