排序的概念
排序：所謂排序，就是使一串記錄，按照其中的某個或某些關(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)
一、直接插入排序
直接插入排序是一種簡單的插入排序法，其基本思想是：
把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。
實際中我們玩撲克牌時，就用了插入排序的思想
當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移。
代碼如下：
void InsertSort(int* a, int n)
{
assert(a);
for (int i = 0; i < n - 1; ++i)
{
// 將x插入[0, end]有序區(qū)間
int end = i;
int x = a[end+1];
while (end >= 0)
{
if (a[end] > x)
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = x;
}
}
直接插入排序是一種比較好理解的排序，在此不多贅述。
直接插入排序的特性總結(jié)：
- 元素集合越接近有序，直接插入排序算法的時間效率越高
- 時間復雜度：O(N^2)
- 空間復雜度：O(1)，它是一種穩(wěn)定的排序算法
- 穩(wěn)定性：穩(wěn)定
二、希爾排序
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數(shù)，把待排序文件中所有記錄分成個組，所有距離為的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進行排序。然后，取，重復上述分組和排序的工作。當?shù)竭_=1時，所有記錄在統(tǒng)一組內(nèi)排好序。
代碼如下：
void ShellSort(int* a, int n)
{
// 按gap分組數(shù)據(jù)進行預排序
int gap = 3;
for (int j = 0; j < gap; ++j)
{
for (int i = j; i < n - gap; i += gap)
{
int end = i;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = x;
}
}
}
或
void ShellSort(int* a, int n)
{
// 多次預排序(gap > 1) +直接插入 (gap == 1)
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; ++i)
{
int end = i;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = x;
}
}
}
兩種寫法一個是給定gap值但有缺陷，而第二種則能夠根據(jù)需要調(diào)整gap值，可以看到，當gap=1時，他就是直接插入排序，可以說，希爾排序就是直接插入排序的一種優(yōu)化。
希爾排序的特性總結(jié)：
- 希爾排序是對直接插入排序的優(yōu)化。
- 當gap > 1時都是預排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。
- 希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算。大概是在O(n^1.25) 到 O(1.6*n^1.25)。
- 穩(wěn)定性：不穩(wěn)定
三、選擇排序
選擇排序基本思想：每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完
直接選擇排序：
★在元素集合array[i]–array[n-1]中選擇關(guān)鍵碼最大(小)的數(shù)據(jù)元素
★若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換
★在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重復上述步驟，直到集合剩余1個元素
在這先寫一個交換函數(shù)，下面的排序也會用到：
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
排序代碼如下：
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin; i <= end; ++i)
{
if (a[i] < a[mini])
mini = i;
if (a[i] > a[maxi])
maxi = i;
}
Swap(&a[begin], &a[mini]);
if (begin == maxi)
maxi = mini;
Swap(&a[end], &a[maxi]);
++begin;
--end;
}
}
直接選擇排序的特性總結(jié)：
- 直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用
- 時間復雜度：O(N^2)
- 空間復雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
四、堆排序
**堆排序(Heapsort)**是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數(shù)據(jù)。
代碼如下：
void AdjustDown(int* a, int n, int parent)//向下調(diào)整
{
int child = parent * 2 + 1;
while (child < n)
{
// 選出左右孩子中小的那一個
if (child + 1 < n && a[child + 1] > a[child])
{
++child;
}
// 如果小的孩子小于父親，則交換，并繼續(xù)向下調(diào)整
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
// 堆排序 -- O（N*logN）
void HeapSort(int* a, int n)
{
// 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;
}
}
需要注意的是排升序要建大堆，排降序建小堆，這里的寫法是升序。
直接選擇排序的特性總結(jié)：
- 堆排序使用堆來選數(shù)，效率就高了很多。
- 時間復雜度：O(N*logN)
- 空間復雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
五、冒泡排序
交換排序基本思想：所謂交換，就是根據(jù)序列中兩個記錄鍵值的比較結(jié)果來對換這兩個記錄在序列中的位置
交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動
冒泡排序：
代碼如下：
void BubbleSort(int* a, int n)
{
int end = n;
while (end > 0)
{
int exchange = 0;
for (int i = 1; i < end; ++i)
{
if (a[i - 1] > a[i])
{
exchange = 1;
Swap(&a[i - 1], &a[i]);
}
}
--end;
if (exchange == 0)
{
break;
}
}
}
冒泡排序的特性總結(jié)：
- 冒泡排序是一種非常容易理解的排序
- 時間復雜度：O(N^2)
- 空間復雜度：O(1)
- 穩(wěn)定性：穩(wěn)定
六、快速排序
快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。
1.遞歸寫法
①三位取中函數(shù)
代碼如下：
int GetMidIndex(int* a, int left, int right)
{
int mid = left + ((right - left) >> 1);
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
三位取中的目的是為了防止面對有序最壞情況，變成選中位數(shù)做key，變成最好情況。
②hoare版本
代碼如下：
int Partion1(int* a, int left, int right)
{
int mini = GetMidIndex(a, left, right);
Swap(&a[mini], &a[left]);
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[left], &a[keyi]);
return left;
}
這里的主體思路是先指定首元素為key，先從數(shù)組尾部開始與key值比大小，直到找到比key小的元素再從左開始找比key大的元素，依次遞歸進行交換，直到left和right指針相遇中止，最后將key值與中間值交換，完成快排第一輪，再進入循環(huán)將中間值兩邊的值再操作，最終完成排序。需要注意的是，這里的三種寫法都進行了三位取中優(yōu)化。
③挖坑法
代碼如下：
int Partion2(int* a, int left, int right)
{
int mini = GetMidIndex(a, left, right);
Swap(&a[mini], &a[left]);
int key = a[left];
int pivot = left;
while (left < right)
{
// 右邊找小, 放到左邊的坑里面
while (left < right && a[right] >= key)
{
--right;
}
a[pivot] = a[right];
pivot = right;
// 左邊找大，放到右邊的坑里面
while (left < right && a[left] <= key)
{
++left;
}
a[pivot] = a[left];
pivot = left;
}
a[pivot] = key;
return pivot;
}
該思路是先將首位元素賦給key值，將首元素位置指定為坑位，同樣是從右邊開始進行比大小，找到比key值小，將該值賦給首元素位置（即坑位），此元素初始位置設為新坑位，再從左邊找比key大的值，找到后放進右邊坑位，以此往復，最后留下的坑位填補為key存放的值，最后的遞歸步驟同上。
④前后指針版本
代碼如下：
int Partion3(int* a, int left, int right)
{
int mini = GetMidIndex(a, left, right);
Swap(&a[mini], &a[left]);
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
++cur;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
此算法的基本思路為：先指定第一個元素為key值，再指定cur與prev兩個指針，prev指針指向第一個元素，cur指針指向第二個元素，cur指針先走找到比key小的元素停止，prev再向前走，找到比key大的元素停止，prev與cur的值進行交換，cur指針繼續(xù)向前尋找比key小的值，以此遞歸，直到cur指針越界停止循環(huán)，將首元素值與此時的prev指向的值進行交換，key此時為樞軸，后遞歸同上。
⑥快排主函數(shù)
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
{
int keyi = Partion1(a, left, right);
//int keyi = Partion2(a, left, right);
//int keyi = Partion3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}
遞歸程序的缺陷：
- 針對早期編譯器相比循環(huán)程序，性能差；
- 遞歸深度太深，會導致棧溢出。（比如數(shù)組中都是相同數(shù)字的情況下）。
2.非遞歸寫法
非遞歸寫法是利用了棧，在C語言中，棧是需要自己寫代碼實現(xiàn)的，這里我套用的是之前寫的關(guān)于棧的博客代碼：
棧的介紹及接口實現(xiàn)
代碼如下：
void QuickSortNonR(int* a, int left, int right)
{
ST st;
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while (!StackEmpty(&st))
{
int end = StackTop(&st);
StackPop(&st);
int begin = StackTop(&st);
StackPop(&st);
int keyi = Partion3(a, begin, end);
if (keyi + 1 < end)
{
StackPush(&st, keyi+1);
StackPush(&st, end);
}
if (begin < keyi-1)
{
StackPush(&st, begin);
StackPush(&st, keyi-1);
}
}
StackDestroy(&st);
}
快速排序的特性總結(jié)：
- 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
- 時間復雜度：O(N*logN)
- 空間復雜度：O(logN)
- 穩(wěn)定性：不穩(wěn)定
七、歸并排序
歸并排序基本思想：
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and
Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有
序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。 歸并排序核心步驟：
1.遞歸寫法
代碼如下：
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
int begin1 = left, end1 = mid;
int begin2 = mid+1, end2 = right;
int i = left;
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++];
}
for (int j = left; j <= right; ++j)
{
a[j] = tmp[j];
}
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}
2.非遞歸寫法
代碼如下：
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
if (end1 >= n || begin2 >= n)
{
break;
}
// end2 越界，需要歸并，修正end2
if (end2 >= n)
{
end2 = n- 1;
}
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++];
}
// 把歸并小區(qū)間拷貝回原數(shù)組
for (int j = i; j <= end2; ++j)
{
a[j] = tmp[j];
}
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
歸并排序的特性總結(jié)：
- 歸并的缺點在于需要O(N)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
- 時間復雜度：O(N*logN)
- 空間復雜度：O(N)
- 穩(wěn)定性：穩(wěn)定
八、非比較排序
思想：計數(shù)排序又稱為鴿巢原理，是對哈希直接定址法的變形應用。 操作步驟：
- 統(tǒng)計相同元素出現(xiàn)次數(shù)
- 根據(jù)統(tǒng)計的結(jié)果將序列回收到原來的序列中
1.基數(shù)排序
基數(shù)排序的思路由最大值的位數(shù)與基數(shù)的定義，比如這里我們是給數(shù)組排序，最大位數(shù)為3，將0-9定為基數(shù)，則基數(shù)是10，拿（278，109，63，930，589，184，505，269，8，83）這個數(shù)組來講，排序過程如下圖，首先從數(shù)組從左至右個位開始，0-9依次插入相應位置，再從0-9依次取出，需要注意的是，先取先放進去的，在進行十位排序，過程同上，后同理。
最后排序結(jié)果為（8，63，83，109，184，269，278，505，589，930）
這里采用的是C++的寫法，方便調(diào)用隊列，想用C語言寫的小伙伴可以參考博主之前關(guān)于隊列的博客，進行調(diào)用修改，步驟相差無幾。
代碼如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;
#define K 3
#define RADIX 10
//定義基數(shù)
queue<int>Q[RADIX];
int GetKey(int value, int k)
{
int key = 0;
while (k >= 0)
{
key = value % 10;
value /= 10;
k--;
}
return key;
}
void Distribute(int arr[], int left, int right, int k)
{
for (int i = left; i < right; ++i)
{
int key = GetKey(arr[i], k);
Q[key].push(arr[i]);
}
}
void Collect(int arr[])
{
int k = 0;
for (int i = 0; i < RADIX; ++i)
{
while (!Q[i].empty())
{
arr[k++] = Q[i].front();
Q[i].pop();
}
}
}
void RadixSort(int arr[], int left, int right)//[left,right)
{
for (int i = 0; i < K; ++i)
{
//分發(fā)數(shù)據(jù)
Distribute(arr, left, right, i);
//回收數(shù)據(jù)
Collect(arr);
}
}
基數(shù)排序的特性總結(jié)：
- 時間復雜度：O(關(guān)鍵字位數(shù)d*n)
- 空間復雜度：O(關(guān)鍵字位數(shù)d*n)
- 穩(wěn)定性：穩(wěn)定
2.計數(shù)排序
計數(shù)排序的思路是基于基數(shù)排序的一種變形，我們先參考下圖，假定數(shù)組值范圍為1-9，基數(shù)為絕對映射，思路同基數(shù)排序，如果是某個范圍內(nèi)，則為相對映射，基數(shù)起始值為數(shù)組最小值，最終值為最大值。
代碼如下：
void CountSort(int* a, int n)
{
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* count = (int*)malloc(sizeof(int)*range);
memset(count, 0, sizeof(int)*range);
if (count == NULL)
{
printf("malloc fail\n");
exit(-1);
}
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ù)排序的特性總結(jié)：文章來源：http://www.zghlxwxcb.cn/news/detail-427271.html
- 計數(shù)排序在數(shù)據(jù)范圍集中時，效率很高，但是適用范圍及場景有限。
- 時間復雜度：O(MAX(N,范圍d))
- 空間復雜度：O(范圍d)
- 穩(wěn)定性：穩(wěn)定
排序算法復雜度及穩(wěn)定性分析
| 排序方法 | 平均情況 | 最好情況 | 最壞情況 | 輔助空間 | 穩(wěn)定性 |
|---|---|---|---|---|---|
| 選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩(wěn)定 |
| 希爾排序 | O(nlogn)~O(n^2) | O(n^1.3) | O(n^2) | O(1) | 不穩(wěn)定 |
| 插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩(wěn)定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) | 不穩(wěn)定 |
| 歸并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 穩(wěn)定 |
| 基數(shù)排序 | O(d*n) | O(d*n) | O(d*n) | O(n) | 穩(wěn)定 |
| 計數(shù)排序 | O(d+n) | O(d+n) | O(d+n) | O(d) | 穩(wěn)定 |
結(jié)語
有興趣的小伙伴可以關(guān)注作者，如果覺得內(nèi)容不錯，請給個一鍵三連吧，蟹蟹你喲?。?！
制作不易，如有不正之處敬請指出
感謝大家的來訪，UU們的觀看是我堅持下去的動力
在時間的催化劑下，讓我們彼此都成為更優(yōu)秀的人吧?。?！文章來源地址http://www.zghlxwxcb.cn/news/detail-427271.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)入門（C語言版）一篇文章教會你手撕八大排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
