一、排序簡介
生活中，我們經(jīng)常能看到排序的應(yīng)用。例如，我們在網(wǎng)購商品的時候，經(jīng)常按銷量從高到低排序。
常見的排序算法有：
先來介紹一下關(guān)于排序算法的幾個概念。
穩(wěn)定性：相等的元素排序之后相對次序不變
內(nèi)部排序：數(shù)據(jù)全在內(nèi)存中的排序
外部排序：數(shù)據(jù)太多不能同時在內(nèi)存中
下面所有排序算法都以排升序為例。
二、直接插入排序
直接插入排序類似我們平時玩撲克牌的洗牌過程。
基本思想：把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。
如圖所示，我們手上已經(jīng)洗好了 2、4、5、10 四張牌。再拿到一張 7，先跟 10 比，比 10 小，所以再往前比對。跟 5 比，比 5 大，就把 7 挨著插到 5 的后面。這樣我們手上的牌就從四張有序的牌變成五張有序的牌了。
我們來看一個動圖：
該動圖完整展現(xiàn)了插入排序的過程。
在代碼實現(xiàn)中，我們把牌插到哪個位置，這個位置后面的所有元素就要后挪一位。而后挪會覆蓋我們拿出來的那張牌原本位置的元素，所以應(yīng)該先保存待插元素的值。
完整代碼如下：
void InsertSort(int* a, int n)
{
for(int i = 1; i < n; i++)
{
int tmp = a[i];
int j = i - 1;
while(j >= 0 && tmp < a[j])
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = tmp;
}
}
//小區(qū)間優(yōu)化常用插入排序
因此，我們可以發(fā)現(xiàn)：
- 一開始越接近有序，插入排序的效率就越高。
- 插入排序后，相等元素的相對次序是不變的，故插入排序具有
穩(wěn)定性。
時間復(fù)雜度：
最壞情況 O(N^2)
最好情況 O(N)
空間復(fù)雜度：O(1)
三、希爾排序
希爾排序，又稱縮小增量排序。
上文提到，對于直接插入排序，一開始越接近有序，排序的效率越高。所以，希爾排序的優(yōu)化方式就是先讓數(shù)組接近有序。
希爾排序包括兩個過程：預(yù)排序和直接插入排序。
- 預(yù)排序：讓數(shù)組先接近有序。
按照間隔gap分組，進(jìn)行直接插入排序，可以一組排完再排另一組，也可以多組一起排。 - 直接插入排序
在代碼實現(xiàn)中，預(yù)排序其實就是gap > 1時進(jìn)行排序的過程，直接插入排序也就是gap == 1時的排序過程。
完整代碼如下：
void ShellSort(int* a, int n)
{
int gap = n / 2;
while (gap > 0)
{
for (int i = gap; i < n; i++)
{
int tmp = a[i];
int j = i;
while (j >= gap && tmp < a[j - gap])
{
a[j] = a[j - gap];
j -= gap;
}
a[j] = tmp;
}
gap /= 2;
}
}
//對于接近有序的序列，直接插入排序最快
//對于無序的序列，希爾排序能大幅優(yōu)化插入排序的效率
希爾排序的具體效率很難計算，我們暫且認(rèn)為時間復(fù)雜度大約在O(N^1.3)。
空間復(fù)雜度：O(1)
另外，在預(yù)排序中，相等元素的相對次序可能會發(fā)生變化，所以希爾排序是不穩(wěn)定的。
四、選擇排序
選擇排序的思想其實非常簡單，以升序為例，就是每次選出最小的換到左邊。
思路非常簡單，來看看代碼怎么寫。
void SelectSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int mini = i;
for (int j = i; j < n; j++)
{
if (a[j] < a[mini]) mini = j;
}
swap(&a[i], &a[mini]);
}
}
時間復(fù)雜度：O(N^2)
空間復(fù)雜度：O(1)
選擇排序是不穩(wěn)定的。
五、堆排序
堆排序是選擇排序的一種，就是把原數(shù)組看成一個堆，利用堆的性質(zhì)，對數(shù)組進(jìn)行處理，達(dá)到排序的效果。
需要注意的是：排升序要建大堆，排降序建小堆。
具體過程如下：
完整代碼如下：
//向下調(diào)整時間復(fù)雜度 O(logN)
void adjustDown(int a[], int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
{
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)
{
//建堆時間復(fù)雜度 O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
adjustDown(a, i, n);
}
//排序時間復(fù)雜度 O(NlogN)
for (int i = n - 1; i >= 0; i--)
{
swap(&a[0], &a[i]);
adjustDown(a, 0, i);
}
}
時間復(fù)雜度：O(NlogN)
空間復(fù)雜度：O(1)
由于存在堆頂與末尾元素交換的過程，所以堆排序是不穩(wěn)定的。
六、冒泡排序
以排升序為例，從前到后依次比較相鄰兩個元素，如果第一個比第二個大，就兩兩交換。第一趟把最大的元素推到最右邊，第二趟把次大的元素放到倒數(shù)第二個位置，以此類推。
整個過程就像冒泡一樣，每趟都把當(dāng)前區(qū)間最大的元素往右邊推，最后只剩第一個元素的時候本身有序。
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)//n-1趟
{
bool flag = false;//檢查是否交換
for (int j = 0; j < n - 1 - i; j++)//每趟比較n-1-i次
{
if (a[j] > a[j + 1])
{
swap(&a[j], &a[j + 1]);
flag = true;
}
}
if (!flag)//如果沒交換，說明已經(jīng)有序
{
break;
}
}
}
由于比較相鄰元素時，相等不會交換位置，所以冒泡排序具有穩(wěn)定性。
時間復(fù)雜度：
最壞情況 O(N^2)
最好情況 O(N)
空間復(fù)雜度：O(1)
可以發(fā)現(xiàn)，冒泡排序的時間復(fù)雜度無論最壞情況還是最好情況，都和直接插入排序相同。
因此我們可以比較一下二者的效率。
七、冒泡排序與直接插入排序效率對比
數(shù)組有序時：一樣
接近有序時：冒泡慢一些
數(shù)組局部有序：冒泡慢很多
所以，雖然冒泡排序可能是我們最早接觸的一種排序算法，但是它的效率真的很一般，甚至不如直接插入排序。文章來源：http://www.zghlxwxcb.cn/news/detail-426401.html
測試函數(shù)：文章來源地址http://www.zghlxwxcb.cn/news/detail-426401.html
void TestOP()
{
srand(time(0));
const int N = 50000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);
int* a8 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
a8[i] = a1[i];
}
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
BubbleSort(a5, N);
int end5 = clock();
int begin6 = clock();
quicksort(a6, 0, N - 1);
int end6 = clock();
int begin7 = clock();
MergeSort(a7, N);
int end7 = clock();
int begin8 = clock();
CountSort(a8, N);
int end8 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("BubbleSort:%d\n", end5 - begin5);
printf("QuickSort:%d\n", end6 - begin6);
printf("MergeSort:%d\n", end7 - begin7);
printf("CountSort:%d\n", end8 - begin8);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
free(a8);
}
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】圖解八大排序（上）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
