個人主頁~

堆排序看這篇~
還有這篇~

---

一、排序的概念及應用

1、概念

排序就是按照某一關鍵字遞增和遞減排列起來的操作
排序在生活中非常常用，成績、排行等等一切跟數(shù)字字母等有關的都能夠排序

2、常見的排序算法

常見的排序算法有
插入排序：直接插入排序，希爾排序
選擇排序：選擇排序，堆排序
交換排序：冒泡排序、快速排序
歸并排序：歸并排序

二、常見排序的實現(xiàn)

1、直接插入排序

（1）基本思想

把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列

（2）代碼實現(xiàn)

//我們看做一個一個插入
void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){//從0到end都有序，tmp插入排序int end = i - 1;//end存儲插入前的最后一個元素的下標，也就是第i-1個數(shù)據(jù)int tmp = a[i];//tmp是插入的數(shù)據(jù)，也就是第i個數(shù)據(jù)while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}//如果前邊比后邊大，就交換并且--end，繼續(xù)向前比較else{break;//直到后邊比前邊大}}a[end + 1] = tmp;//將此時end+1下標的位置賦值tmp，后邊的數(shù)據(jù)全都往后移了一位}
}

封裝一個打印數(shù)組的函數(shù)

void ArrPrint(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}
}

（3）時間復雜度

如果按照最壞的情況：
第一次排不需要比較
第二次需要比較一次
第三次需要比較兩次
…
第N次需要比較N-1次
F(N)=0+1+2+3+…+N-1 = (N-1)*(N)/2
所以直接插入排序的最壞時間復雜度為O(N^2)
最好時間復雜度就是有序數(shù)組O(N)
所以直接插入排序是介于它們之間的，這才有了希爾排序這種優(yōu)化算法，降低了時間復雜度

（4）空間復雜度

沒有占用額外空間，O(1)

2、希爾排序

（1）基本思想

希爾排序可以說是高級的直接插入排序，它是希爾通過觀察和實踐在直接插入排序的基礎上進行算法優(yōu)化，將時間復雜度降低
希爾排序分為兩步：
第一步：預排序，是將無序的數(shù)組排序至接近有序
第二步：直接插入排序
當gap越小越接近有序，gap越大預排序的速度會更快
當gap為1時，就是直接插入排序
簡單來說希爾排序就是粗排后細排

（2）代碼實現(xiàn)

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//分為三組，最后加一可以保證最后一次的while循環(huán)gap等于1，相當于直接插入排序for (int i = 0; i < n - gap; i++){int end = i;
//每組的最后一個數(shù)字（這里的最后一個是指一個一個往里面插的最后一個數(shù)字，并不是真正的最后一個數(shù)字）int tmp = a[end + gap];//記錄待插入數(shù)字while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}elsebreak;}//同直接插入排序，差別是分了組，每次要對比的數(shù)字的下標差了gapa[end + gap] = tmp;}}
}

（3）時間復雜度

希爾排序的時間復雜度并不好計算，因為gap的取值很多，我們沒辦法通過簡單的計算來得出結果，這是一個數(shù)學上的難以解答的問題，資料中顯示，它的時間復雜度在O(n^1.25)到O(1.6*n ^1.25)之間，我們粗略表示成O(n ^1.3)

（4）空間復雜度

沒有占用額外空間，O(1)

3、選擇排序

（1）基本思想

遍歷數(shù)組，每一次將最大和最小的數(shù)據(jù)挑出來放到數(shù)列的起始和末尾位置，知道所有元素全部排完
這是一種超級慢的排序方式，實際使用中很少用

（2）代碼實現(xiàn)

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;}void SelectSort(int* a, int n)
{int right= n - 1;//定位到數(shù)組最后一個元素下標int left = 0;//定位到數(shù)組第一個元素下標while (left < right){int min = left;//先將left作為最開始的最小值int max = right;//先將right作為最開始的最大值for (int i = left; i <= right; i++){if (a[i] < a[min])min = i;if (a[i] > a[max])max = i;}//在left和right之間選出最大和最小的數(shù)Swap(&a[left], &a[min]);//交換a[left]與a[min]if (left == max)max = min;//這里注意，當最大值與left重疊時，將位置修正再交換Swap(&a[right], &a[max]);left++;right--;}
}

（3）時間復雜度

它的時間復雜度就是等差數(shù)列求和，可以很容易的看出來它的時間復雜度為O(N^2)

（4）空間復雜度

沒有占用額外空間，O(1)

4、堆排序

在之前的文章中有詳細的解釋，我們可以來到二叉樹-堆文章中來詳細了解

（1）基本思想

利用堆的特性，即小堆堆頂最小，大堆堆頂最大的性質，來進行升序或降序排序

（2）代碼實現(xiàn)

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void AdjustDown(int* a, int n,int parent)
{int child = parent * 2 + 1;while(child < n){if (child + 1 < n && a[child] < a[child + 1]){child++;}//調出值較大的那個孩子if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}//交換后讓孩子當?shù)?#xff0c;使其跟它的孩子比較elsebreak;}
}void HeapSort(int* a, int n)
{//parent = (child-1) / 2，i的初始值是最后一個元素的父節(jié)點for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//調整出一個大堆int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);//交換首尾元素AdjustDown(a, end, 0);end--;}
//每次調整都會將最大的一個數(shù)放在當前調整范圍的最后一個位置，而調整范圍的最后一個位置每次都會向前一個，直到成為升序數(shù)組
}

（3）時間復雜度

在前面鏈接中的文章中我們計算過它的時間復雜度，O(N*log?N)

（4）空間復雜度

沒有額外申請空間，O(1)

5、冒泡排序

（1）基本思想

冒泡排序是我們初識C語言時的接觸到的第一個排序方式，也可以說是最雞肋的排序方式，簡單易懂但效率很低，就是兩兩元素相互比較，大的往后移動，遍歷一遍下來最大的就到最后了，以此類推實現(xiàn)排序
這里我就不過多解釋了

（2）代碼實現(xiàn)

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void BubbleSort(int* a, int n)
{for (int i = 0; i < n; i++){for (int j = 0; j < n - i - 1; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);}}}
}

（3）時間復雜度

相當于等差數(shù)組求和，n-1 + n-2 + … + 1
F(N) = (N-1+1)/2 * N/2
時間復雜度為O(N^2)

（4）空間復雜度

沒有占用額外空間，空間復雜度為O(1)

6、快速排序

（1）基本思想

任取待排序序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素小于基準值，右子序列中所有元素大于基準值，然后在左右子序列中重復該過程，直到排序完成
這里我們每一次取的基準值都是左數(shù)第一個元素

（2）代碼實現(xiàn)

①hoare版本

int PartSort1(int* a, int left, int right)
{int keyi = left;//將最左邊的元素作為關鍵元素，即基準值，記錄它的下標while (left < right){while (left < right && a[keyi] <= a[right]){right--;}while (left < right && a[keyi] >= a[left]){left++;}Swap(&a[left], &a[right]);
//左右兩邊向中間逼近，在右邊找到小于基準值的數(shù)字，在左邊找到大于基準值的數(shù)字，兩者交換}Swap(&a[keyi], &a[left]);//循環(huán)出來之后，說明left與right相遇了，也就是說此時的這個位置左邊的數(shù)字全部比基準值小，右邊的數(shù)字都比基準值大，將這個位置的數(shù)字與基準值位置的數(shù)字交換位置return left;//將此時的基準值返回
}void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = PartSort1(a, left, right);//將區(qū)間分成三個部分：keyi，keyi左，keyi右QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);//對剩下的區(qū)間繼續(xù)排序
}

②挖坑法版本

int PartSort2(int* a, int left, int right)
{int key = a[left];//存下坑里的數(shù)字int hole = left;//把最左邊的位置作為坑while (left < right){while (left < right && a[right] >= key)right--;//找到a[right] < key的位置跳出循環(huán)a[hole] = a[right];hole = right;//把這個位置挖新坑，將坑里的值存起來while (left < right && a[left] <= key)left++;a[hole] = a[left];hole = left;//右邊挖完左邊挖，左邊找大于基準值的}a[hole] = key;//將最開始存下來的基準值填到此時剩下的坑里return hole;
}void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = PartSort2(a, left, right);//將區(qū)間分成三個部分：keyi，keyi左，keyi右QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);//對剩下的區(qū)間繼續(xù)排序
}

③前后指針版本

int PartSort3(int* a, int left, int right)
{int prev = left;//初始前指針為最左邊的元素int cur = left + 1;//初始后指針為前指針的后一個元素int keyi = left;//存下前指針的下標作為基準值下標while (cur <= right){while (a[cur] < a[keyi] && ++prev != cur)Swap(&a[cur], &a[prev]);
//如果后指針指向的數(shù)字大小小于基準值，并且前指針的后一個指針不為后指針，那么前后指針指向位置的值交換
//當后指針指向的值小于基準值時，前指針都會往后走（這里的知識涉及到邏輯語句的短路）cur++;//后指針往后走}Swap(&a[prev], &a[keyi]);keyi = prev;//最后前指針所指向元素的大小一定大于基準值，將他們交換，此時的基準值左邊除了第一個都比它小，右邊都比它大return keyi;
}void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = PartSort3(a, left, right);//將區(qū)間分成三個部分：keyi，keyi左，keyi右QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);//對剩下的區(qū)間繼續(xù)排序
}

（3）時間復雜度

快速排序是一種類二叉樹類型的排序，所以它的時間復雜度為O(N*log?N)，計算方法同二叉樹

（4）空間復雜度

遞歸創(chuàng)建類二叉樹，空間復雜度為O(log?N)

---

下期再見~