系列文章目錄
前言
排序是一種非常重要的算法。
排序的概念及其運用
排序的概念
排序：所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。
穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。
外部排序：數(shù)據(jù)元素太多不能同時放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序。
常見的排序算法
常見排序算法的實現(xiàn)
1.直接插入排序
基本思想：把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。 =>打撲克牌
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{//i = n - 1 時已經(jīng)排完了
int end = i;
//指向有序隊列的最后一位
int tmp = a[end + 1];
//要排入有序隊列的數(shù)
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
//放在結(jié)束位置的后一個位置，即要插入的位置
}
}
插入排序在部分或已經(jīng)有序的數(shù)列效率最高。
時間復(fù)雜度：
最壞：逆序——O(N2)
最好：順序有序——O(N)
2. 希爾排序（縮小增量排序）
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數(shù)，把待排序文件中所有記錄分成個組，所有距離為的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進行排序。然后，取，重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_(dá)=1時，所有記錄在統(tǒng)一組內(nèi)排好序。=>優(yōu)化的插入排序
步驟
1. 多次預(yù)排序（分組排序）：對原數(shù)組進行間隔分組，再對分組進行插入排序，使得原數(shù)組變得相對更有序
2. 最有一次插入排序：當(dāng)分組排序的間隔為1時
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{ // gap > 1預(yù)排序
// gap == 1 就是插入排序
gap = gap / 3 + 1;
//gap = gap / 2;
for (int i = 0; i < n - gap; i++)
{//i++gap組并排
//i = n - gap 時已經(jīng)排完了
int end = i;
//指向分組有序部分的最后一位
int tmp = a[end + gap];
//指向分組中要排入有序分組的數(shù)
while (end >= 0)
{
if (tmp > a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
//放在結(jié)束位置的后一個位置，即要插入的位置
}
}
}
1. gap越大，大的數(shù)可以更快到后面，小的可以更快到前面；越不接近有序。
2. gap越小，數(shù)據(jù)跳動越慢，越接近有序
時間復(fù)雜度：
分成gap組，每組N/gap個數(shù)據(jù)
每組最壞情況下挪動次數(shù)：1+2+3+…+N/gap-1 等差數(shù)列
最壞情況：（1+2+3+…+N/gap) * gap
最開始時gap很大 => 一趟排序：N
快結(jié)束時gap很小 => 一趟排序：N
排序次數(shù)：log2N
時間復(fù)雜度：O(N1.3)
3. 直接選擇排序
基本思想：每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完 。
- 在元素集合array[i]–array[n-1]中選擇關(guān)鍵碼最大(小)的數(shù)據(jù)元素
- 若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換
- 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重復(fù)上述步驟，直到集合剩余1個元素
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
//每次遍歷選出最小和最大的數(shù)
int mini = begin;
int max = begin;
for (int i = begin + 1; i <= end; i++)
{
if (a[i] < a[mini])
mini = i;
if (a[i] > a[max])
max = i;
}
swap(&a[mini], &a[begin]);
//如果max位置和mini位置重疊，需要修正一下max的位置
if (max == begin)
max = mini;
swap(&a[max], &a[end]);
//將最小和最大的數(shù)放到左右兩邊的位置
begin++;
end--;
}
}
時間復(fù)雜度：O(N2)
空間復(fù)雜度：O(1)
與直接插入排序比較，插入排序適應(yīng)性更強，對于有序、局部有序，都能效率提升。
而選擇排序在任何情況都是O(N2)。
4. 堆排序
基本思想：堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。
void AdjustDown(int* a, int parent, int size)
{//升序建大堆，降序建小堆
int child = parent * 2 + 1;
while (child < size)
{
//確認(rèn)child指向大的哪個孩子
if (child + 1 < size && a[child + 1] < a[child])
{
++child;
}
if (a[child] > a[parent])
{//孩子大于父親，交換，繼續(xù)向下調(diào)整，建大堆
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{//孩子小于父親
break;
}
}
}
// O(N * logN)
void HeapSort(int* a, int n)
{
//向上調(diào)整堆 -- O(N*logN)
//降序
/*for (int i = 0; i < n; i++)
{
AdjustUp(a, i);
}*/
//向下調(diào)整堆 -- O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, i, n);
}
int end = n - 1;
while (end)
{
//升序 -- O(N * logN)
swap(&a[0], &a[end]);
AdjustDown(a, 0, end);
end--;
}
}
void swap(int* a, int * b)
{
int temp = *a;
*a = *b;
*b = temp;
}
時間復(fù)雜度：O(N*logN)
5. 冒泡排序
基本思想：所謂交換，就是根據(jù)序列中兩個記錄鍵值的比較結(jié)果來對換這兩個記錄在序列中的位置，交換排
序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{//冒泡 n - 1 次
int exchange = 0;
for (int j = 0; j < n - i - 1; j++)
{//每次都是n - i - 1上的位置確定
if (a[j] > a[j + 1])
swap(&a[j], &a[j + 1]);
exchange = 1;
}
if (exchange == 0)
{//沒有交換就說明有序了
break;
}
}
}
冒泡排序在已經(jīng)有序的數(shù)列效率最高。
時間復(fù)雜度：O(N^2)
空間復(fù)雜度：O(1)
6. 快速排序
快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中
的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右
子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。
將區(qū)間按照基準(zhǔn)值劃分為左右兩半部分的常見方式：
1. hoare版本
key:最左邊的值或最右邊的值
單趟排序：左邊比key要小，右邊比key要大
1. 分割出左右區(qū)間，左區(qū)間比key小，右區(qū)間比key大
2. key已經(jīng)落到他的正確的位置，排序后的最終位置
剩下的問題：
3. 左區(qū)間有序，右區(qū)間有序，那么整體就有序了
左邊做key，右邊先走，右邊做key，左邊先走；
左邊做key，右邊先走，保證相遇位置比key??；
右邊做key，左邊先走，保證相遇位置比key大；
相遇的位置：
如果左邊做key，右邊先走
一種是R停住的，L遇到R，相遇位置就是R停住的位置；
一種是L停住的，R遇到L，相遇位置就是L停住的位置；
這兩種位置都比key要小
int PartSort1(int* a, int begin, int end)
{//hoare法
int mid = GetMidIndex(a, begin, end);
swap(a + begin, a + mid);
int left = begin;
int right = end;
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);
}
swap(a + keyi, a + left);
keyi = left;
return keyi;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end) return;
int keyi = PartSort1(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
平均時間復(fù)雜度：O(N*log2N)
最壞時間復(fù)雜度：O(N2)
優(yōu)化版本：三數(shù)取中法選key
//三數(shù)取中
//begin mid end
int GetMidIndex(int* a, int begin, int end)
{
int mid = (begin + end) / 2;
if (a[begin] > a[end])
{
if (a[mid] > a[begin])
return a[begin];
else if (a[mid] > a[end])
return a[mid];
else
return a[end];
}
else
{//a[begin] <= a[end]
if (a[mid] > a[end])
return a[end];
else if (a[mid] > a[begin])
return a[mid];
else
return a[begin];
}
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end) return;
int left = begin;
int right = end;
int keyi = left;
int mid = GetMidIndex(a, begin, end);
swap(a + keyi, a + mid);
while (left < right)
{
while (left < right && a[right] >= a[keyi])right--;
//右邊先走，找小
while (left < right && a[left] <= a[keyi])left++;
//左邊再走，找大
swap(a+left, a+right);
}
swap(a + keyi, a + left);
keyi = left;
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
三數(shù)取中將最壞時間復(fù)雜度降為：O(N*log2N)
優(yōu)化版本：遞歸到小的子區(qū)間時，可以考慮使用插入排序
小區(qū)間優(yōu)化：快排分割到小區(qū)間時，用直接插入排序，節(jié)省大部分遞歸
void QuickSort(int* a, int begin, int end)
{
if (begin >= end) return;
if (end - begin + 1 < 10)
{
// 小區(qū)間用直接插入代替，減少遞歸調(diào)用次數(shù)
InsertSort(a+begin, end - begin + 1);
}
else
{
int left = begin;
int right = end;
int keyi = left;
int mid = GetMidIndex(a, begin, end);
swap(a + keyi, a + mid);
while (left < right)
{
while (left < right && a[right] >= a[keyi])right--;
//右邊先走，找小
while (left < right && a[left] <= a[keyi])left++;
//左邊再走，找大
swap(a + left, a + right);
}
swap(a + keyi, a + left);
keyi = left;
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
}
2. 挖坑版本
int PartSort2(int* a, int begin, int end)
{ //挖坑法
//左挖坑，右填坑，右挖坑，左填坑。
int mid = GetMidIndex(a, begin, end);
swap(a + begin, a + mid);
int left = begin;
int right = end;
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[right] = a[left];
hole = left;
}
a[hole] = key;
return hole;
}
1. 右邊找到一個坑位，要填左邊的坑，再挖該坑位。
2. 左邊找到一個坑位，要填右邊的坑，再挖該坑位。
3. 前后指針版本
int PartSort3(int* a, int begin, int end)
{//把大的推到右邊去，把小的推到左邊去
int mid = GetMidIndex(a, begin, end);
swap(a + begin, a + mid);
int cur = begin + 1;
int prev = begin;
int keyi = begin;
/*for (; cur < end + 1; cur++)
{
if (a[cur] > a[keyi])
{
prev++;
swap(a + prev, a + cur);
}
}*/
while (cur <= end)
{
if (a[cur] > a[keyi] && ++prev != cur)
{
swap(&a[++prev], &a[cur]);
}
cur++;
}
swap(a + prev, a + keyi);
return prev;
}
1. cur找key小，找到后停下來。
2. ++prev,交換prev位置和cur位置。
4. 快速排序非遞歸實現(xiàn)版本
進棧順序圖
void QuickSortNonR(int* a, int begin, int end)
{
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 keyi = PartSort1(a, left, right);
if (keyi + 1 < right)
{
StackPush(&st, keyi + 1);
StackPush(&st, right);
}
if (left < keyi - 1)
{
StackPush(&st, left);
StackPush(&st, keyi - 1);
}
}
}
快速排序的特性總結(jié)：
時間復(fù)雜度：O(N*logN)
空間復(fù)雜度：O(logN)
大量的重復(fù)數(shù)據(jù)，那么key就是這個重復(fù)的數(shù)時，就會導(dǎo)致時間復(fù)雜度上升為O(N2)。
可以用三路劃分來解決重復(fù)數(shù)。
1.a[c] < key 交換a[l]和a[c]的位置，l++，c++ => 比key小的數(shù)甩到左邊
2.a[c] == key c++=> 跟key相等的值，往后推，跟key相等的就會在中間
3.a[c] > key 交換c和r的位置，r–=>比key大的甩到右邊
結(jié)束條件：c > r 結(jié)束
7. 歸并排序
基本思想：歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide andConquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
歸并排序核心步驟：
歸并排序的幾種實現(xiàn)方式
1. 遞歸法
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin >= end) return;
int mid = (begin + end) / 2;
_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;
}
兩端有序區(qū)間，依次得比較小的元素，尾插進新的數(shù)組序列
時間復(fù)雜度：O(N*logN)
空間復(fù)雜度：O(logN)
2. 非遞歸法
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個認(rèn)為是有序的，可以直接歸并
int rangeN = 1;
while (rangeN < n)
{
for (int i = 0; i < n; i += 2 * rangeN)
{
//歸并
int begin1 = i, end1 = i + rangeN - 1;
int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;
if (end1 >= n)
{//end1 begin2 end2 越界
//修正區(qū)間 ->拷貝數(shù)據(jù)
end1 = n - 1;
//不存在區(qū)間
begin2 = n;
end2 = n - 1;
}
else if (begin2 >= n)
{//begin2 end2 越界
begin2 = n;
end2 = n - 1;
}
else if (end2 >= n)
{//end2 越界
end2 = n - 1;
}
int j = i;
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, tmp, sizeof(int)* (n));
rangeN *= 2;
}
free(tmp);
tmp = NULL;
}
8. 計數(shù)排序
思想：計數(shù)排序又稱為鴿巢原理，是對哈希直接定址法的變形應(yīng)用。 操作步驟：
1. 統(tǒng)計相同元素出現(xiàn)次數(shù)
2. 根據(jù)統(tǒng)計的結(jié)果將序列回收到原來的序列中
void CountSort(int* a, int n)
{//計數(shù)排序
int max = a[0], min = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] > max) max = a[i];
if (a[i] < min) min = a[i];
}
int range = max - min + 1;
int* countA = (int*)calloc(range,sizeof(int));
if (countA == NULL)
{
printf("calloc fail");
exit(-1);
}
//1. 統(tǒng)計次數(shù)
for (int i = 0; i < n; i++)
{
countA[a[i] - min]++;
}
//2. 排序
int k = 0;
for (int j = 0; j < range; j++)
{
while (countA[j]--)
a[k++] = j + min;
}
free(countA);
}
時間復(fù)雜度：O(MAX(N,range))
空間復(fù)雜度：O(Range)
適合范圍集中的數(shù)據(jù)，只適合整型
排序算法復(fù)雜度及穩(wěn)定性分析
穩(wěn)定性：相同的數(shù)保證它們的相對順序不變，那么就是穩(wěn)定的。
歸并排序可以是內(nèi)排序或外排序，其他排序是內(nèi)排序。文章來源：http://www.zghlxwxcb.cn/news/detail-532724.html
總結(jié)
排序是非常重要的算法，一定要理解每種算法的原理。
真正的才智是剛毅的志向?！闷苼?/mark>文章來源地址http://www.zghlxwxcb.cn/news/detail-532724.html
到了這里，關(guān)于第11章：C語言數(shù)據(jù)結(jié)構(gòu)與算法初階之排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
