摘要：排序算法是最基本最常用的算法，不同的排序算法在不同的場景或應用中會有不同的表現(xiàn)，我們需要對各種排序算法熟練才能將它們應用到實際當中，才能更好地發(fā)揮它們的優(yōu)勢。今天，來總結(jié)下各種排序算法。

排序算法是最基本最常用的算法，不同的排序算法在不同的場景或應用中會有不同的表現(xiàn)，我們需要對各種排序算法熟練才能將它們應用到實際當中，才能更好地發(fā)揮它們的優(yōu)勢。今天，來總結(jié)下各種排序算法。

下面這個表格總結(jié)了各種排序算法的復雜度與穩(wěn)定性：

各種排序算法復雜度比較.png

冒泡排序
冒泡排序可謂是最經(jīng)典的排序算法了，它是基于比較的排序算法，時間復雜度為O(n^2)，其優(yōu)點是實現(xiàn)簡單，n較小時性能較好。

算法原理

相鄰的數(shù)據(jù)進行兩兩比較，小數(shù)放在前面，大數(shù)放在后面，這樣一趟下來，最小的數(shù)就被排在了第一位，第二趟也是如此，如此類推，直到所有的數(shù)據(jù)排序完成

c++代碼實現(xiàn)

void bubble_sort(int arr[], int len)
   {
for (int i = 0; i < len - 1; i++)
{
for (int j = len - 1; j > i; j--)
{
if (arr[j] < arr[j - 1])
{
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}

}

選擇排序

算法原理

先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

c++代碼實現(xiàn)

void select_sort(int arr[], int len)
{

for (int i = 0; i < len; i++)
{
int index = i;
for (int j = i + 1; j < len; j++)
{
if (arr[j] < arr[index])
index = j;
}
if (index != i)
{
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp; 
}
}


 }

插入排序

算法原理

將數(shù)據(jù)分為兩部分，有序部分與無序部分，一開始有序部分包含第1個元素，依次將無序的元素插入到有序部分，直到所有元素有序。插入排序又分為直接插入排序、二分插入排序、鏈表插入等，這里只討論直接插入排序。它是穩(wěn)定的排序算法，時間復雜度為O(n^2)

c++代碼實現(xiàn)

 void insert_sort(int arr[], int len)
{
 for (int i = 1; i < len; i ++)
 {
 int j = i - 1;
 int k = arr[i];
 while (j > -1 && k < arr[j] )
 {
 arr[j + 1] = arr[j];
 j --;
 }
 arr[j + 1] = k;


}
}

快速排序

算法原理

快速排序是目前在實踐中非常高效的一種排序算法，它不是穩(wěn)定的排序算法，平均時間復雜度為O(nlogn)，最差情況下復雜度為O(n^2)。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。

c++代碼實現(xiàn)

void quick_sort(int arr[], int left, int right)

{
 if (left < right)
 {
 int i = left, j = right, target = arr[left];
 while (i < j)
 {
 while (i < j && arr[j] > target)
 j--;
 if (i < j)
 arr[i++] = arr[j];
 while (i < j && arr[i] < target)
 i++;
 if (i < j)
 arr[j] = arr[i];
 }
 arr[i] = target;
 quick_sort(arr, left, i - 1);
 quick_sort(arr, i + 1, right);
 }
}

歸并排序

算法原理

歸并排序具體工作原理如下（假設序列共有n個元素）：

將序列每相鄰兩個數(shù)字進行歸并操作（merge)，形成floor(n/2)個序列，排序后每個序列包含兩個元素

將上述序列再次歸并，形成floor(n/4)個序列，每個序列包含四個元素

重復步驟2，直到所有元素排序完畢

歸并排序是穩(wěn)定的排序算法，其時間復雜度為O(nlogn)，如果是使用鏈表的實現(xiàn)的話，空間復雜度可以達到O(1)，但如果是使用數(shù)組來存儲數(shù)據(jù)的話，在歸并的過程中，需要臨時空間來存儲歸并好的數(shù)據(jù)，所以空間復雜度為O(n)

c++代碼實現(xiàn)

void merge(int arr[], int temp_arr[], int start_index, int mid_index, int end_index)
{

int i = start_index, j = mid_index + 1;
int k = 0;
while (i < mid_index + 1 && j < end_index + 1)
{
if (arr[i] > arr[j])
temp_arr[k++] = arr[j++];
else
temp_arr[k++] = arr[i++];
}
while (i < mid_index + 1)
{
temp_arr[k++] = arr[i++];
}
while (j < end_index + 1)
temp_arr[k++] = arr[j++];
for (i = 0, j = start_index; j < end_index + 1; i ++, j ++)
arr[j] = temp_arr[i];

}
void merge_sort(int arr[], int temp_arr[], int start_index, int end_index)
{
 if (start_index < end_index)
 {
 int mid_index = (start_index + end_index) / 2;
 merge_sort(arr, temp_arr, start_index, mid_index);
 merge_sort(arr, temp_arr, mid_index + 1, end_index);
 merge(arr, temp_arr, start_index, mid_index, end_index);
 }


 }

堆排序
二叉堆

二叉堆是完全二叉樹或者近似完全二叉樹，滿足兩個特性

父結(jié)點的鍵值總是大于或等于(小于或等于)任何一個子節(jié)點的鍵值

每個結(jié)點的左子樹和右子樹都是一個二叉堆

當父結(jié)點的鍵值總是大于或等于任何一個子節(jié)點的鍵值時為最大堆。當父結(jié)點的鍵值總是小于或等于任何一個子節(jié)點的鍵值時為最小堆。一般二叉樹簡稱為堆。

堆的存儲

一般都是數(shù)組來存儲堆，i結(jié)點的父結(jié)點下標就為(i – 1) / 2。它的左右子結(jié)點下標分別為2 i + 1和2 i + 2。如第0個結(jié)點左右子結(jié)點下標分別為1和2。存儲結(jié)構(gòu)如圖所示：

堆排序原理

堆排序的時間復雜度為O(nlogn)

算法原理（以最大堆為例）

先將初始數(shù)據(jù)R[1..n]建成一個最大堆，此堆為初始的無序區(qū)

再將關(guān)鍵字最大的記錄R[1]（即堆頂）和無序區(qū)的最后一個記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key

由于交換后新的根R[1]可能違反堆性質(zhì)，故應將當前無序區(qū)R[1..n-1]調(diào)整為堆。

重復2、3步驟，直到無序區(qū)只有一個元素為止。

c++代碼實現(xiàn)

/**

* 將數(shù)組arr構(gòu)建大根堆
* @param arr 待調(diào)整的數(shù)組
* @param i 待調(diào)整的數(shù)組元素的下標
* @param len 數(shù)組的長度

 */
void heap_adjust(int arr[], int i, int len)
{
 int child;
 int temp;
 for (; 2 * i + 1 < len; i = child)
 {
 child = 2 * i + 1; // 子結(jié)點的位置 = 2 * 父結(jié)點的位置 + 1
 // 得到子結(jié)點中鍵值較大的結(jié)點
 if (child < len - 1 && arr[child + 1] > arr[child])
 child ++;
 // 如果較大的子結(jié)點大于父結(jié)點那么把較大的子結(jié)點往上移動，替換它的父結(jié)點
 if (arr[i] < arr[child])
 {
 temp = arr[i];
 arr[i] = arr[child];
 arr[child] = temp;
 }
 else
 break;
 }
}
/**
 * 堆排序算法
 */
void heap_sort(int arr[], int len)
{
 int i;
 // 調(diào)整序列的前半部分元素，調(diào)整完之后第一個元素是序列的最大的元素
 for (int i = len / 2 - 1; i >= 0; i--)
 {
 heap_adjust(arr, i, len);
 }
 for (i = len - 1; i > 0; i--)
 {
 // 將第1個元素與當前最后一個元素交換，保證當前的最后一個位置的元素都是現(xiàn)在的這個序列中最大的
 int temp = arr[0];
 arr[0] = arr[i];
 arr[i] = temp;
 // 不斷縮小調(diào)整heap的范圍，每一次調(diào)整完畢保證第一個元素是當前序列的最大值
 heap_adjust(arr, 0, i);
 }
}