本文主要對七種排序算法做宏觀上的總結(jié)，沒有死扣代碼細(xì)節(jié)，意在充分理解各種排序算法的思想。
I、 上帝視角看排序
排序算法常出現(xiàn)在各種面試題中，對于算法時(shí)間空間復(fù)雜度的分析，穩(wěn)定性要求等都需要靈活掌握。
1.1 冒泡排序
基本思想：兩兩比較相鄰的關(guān)鍵字，如果反序則交換。
時(shí)間復(fù)雜度：最好是O(n)，最壞的情況是O(n^2)。
改進(jìn)思路：
1、設(shè)置標(biāo)志位，明顯如果有一趟沒有發(fā)生交換（flag=false），說明已經(jīng)有序；
2、記錄下一輪下來標(biāo)記的最后位置，下次從頭部遍歷到這個(gè)位置就OK。
1.2 簡單選擇排序
基本思想：通過n-i次關(guān)鍵字之間的比較，從n-i+1個(gè)元素中選擇關(guān)鍵字最小的元素，并和第i(1<=i<=n)個(gè)元素交換。
時(shí)間復(fù)雜度：為O(n^2)，但簡單選擇排序的性能略優(yōu)于冒泡排序。
1.3 直接插入排序
基本思想： 將一個(gè)元素插入到已經(jīng)排好序的有序表中，從而得到一個(gè)新的，元素?cái)?shù)新增1的有序表。
時(shí)間復(fù)雜度：為O(n^2)，但是比冒泡排序和選擇排序的性能要更好一些。
1.4 希爾排序
基本思想：先將整個(gè)待排序元素序列分割成若干個(gè)序列（由相隔某個(gè)“增量”的元素組成），分別進(jìn)行直接插入排序，然后依次縮減增量在進(jìn)行排序，待整個(gè)序列中元素基本有序（增量足夠?。r(shí)，在對全體元素進(jìn)行一次直接插入排序（增量為1）。
時(shí)間復(fù)雜度：其時(shí)間復(fù)雜度為O(n^1.5)。
1.5 歸并排序
基本思想：假設(shè)初始序列含有n個(gè)元素，則可以看成n個(gè)有序的子序列，每個(gè)子序列長度為1，然后兩兩歸并，得到（不小于n/2的最小整數(shù)）個(gè)長度為2或1的有序子序列，然后在兩兩歸并，...如此重復(fù)，直到得到一個(gè)長度為n的有序序列為止。
時(shí)間復(fù)雜度：時(shí)間復(fù)雜度為O(nlgn)，空間復(fù)雜度為O(n+lgn)，如果非遞歸實(shí)現(xiàn)歸并，則避免了遞歸時(shí)深度為lgn的?？臻g，空間復(fù)雜度為O(n)。
1.6 堆排序
關(guān)于堆排序的詳細(xì)說明見wenmingxing 堆排序初探
時(shí)間復(fù)雜度：堆排序的時(shí)間復(fù)雜度為O(nlgn)。
1.7 快速排序
關(guān)于快速排序的詳細(xì)說明見wenmingxing 深入理解快排
時(shí)間復(fù)雜度：快排的時(shí)間復(fù)雜度為O(nlgn)。
II、七種排序算法比較
III、參考代碼
下面參考代碼中沒有堆排序和快速排序的代碼，可以見上面的鏈接文章。
#include<iostream>
using namespace std;
void swap1(int *left, int *right)
{
int temp = *left;
*left = *right;
*right = temp;
}
void swap2(int &left, int &right)
{
int temp = left;
left = right;
right = left;
}
void swap3(int &left, int &right)
{
if (&left != &right)
{
left ^= right;
right ^= left;
left ^= right;
}
}
/*****************************************************************/
/* 冒泡排序時(shí)間復(fù)雜度最好的情況為O(n),最壞的情況是O(n^2)
* 基本思想是:兩兩比較相鄰記錄的關(guān)鍵字,如果反序則交換 */
void BubbleSort1(int arr[], int num)
{
int i, j;
for (i = 0; i < num; i++)
{
for (j = 1; j < num - i; j++)
{
if (arr[j - 1] > arr[j])
swap1(&arr[j - 1], &arr[j]);
}
}
}
// 改進(jìn)思路：設(shè)置標(biāo)志位，明顯如果有一趟沒有發(fā)生交換（flag = flase)，說明排序已經(jīng)完成.
void BubbleSort2(int arr[], int num)
{
int k = num;
int j;
bool flag = true;
while (flag)
{
flag = false;
for (j = 1; j < k; j++)
{
if (arr[j - 1] > arr[j])
{
swap1(&arr[j - 1], &arr[j]);
flag = true;
}
}
k--;
}
}
//改進(jìn)思路：記錄一輪下來標(biāo)記的最后位置，下次從頭部遍歷到這個(gè)位置就Ok
void BubbleSort3(int arr[], int num)
{
int k, j;
int flag = num;
while (flag > 0)
{
k = flag;
flag = 0;
for (j = 1; j < k; j++)
{
if (arr[j - 1] > arr[j])
{
swap1(&arr[j - 1], &arr[j]);
flag = j;
}
}
}
}
/*************************************************************************/
/**************************************************************************/
/*插入排序: 將一個(gè)記錄插入到已經(jīng)排好序的有序表中, 從而得到一個(gè)新的,記錄數(shù)增1的有序表
* 時(shí)間復(fù)雜度也為O(n^2), 比冒泡法和選擇排序的性能要更好一些 */
void InsertionSort(int arr[], int num)
{
int temp;
int i, j;
for (i = 1; i < num; i++)
{
temp = arr[i];
for (j = i; j > 0 && arr[j - 1] > temp; j--)
arr[j] = arr[j - 1];
arr[j] = temp;
}
}
/****************************************************************************/
/*希爾排序:先將整個(gè)待排元素序列分割成若干子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行
直接插入排序，然后依次縮減增量再進(jìn)行排序，待整個(gè)序列中的元素基本有序（增量足夠小）時(shí)，
再對全體元素進(jìn)行一次直接插入排序（增量為1）。其時(shí)間復(fù)雜度為O(n^3/2),要好于直接插入排序的O(n^2) */
void ShellSort(int *arr, int N)
{
int i, j, increment;
int tmp;
for (increment = N / 2; increment > 0; increment /= 2)
{
for (i = increment; i < N; i++)
{
tmp = arr[i];
for (j = i; j >= increment; j -= increment)
{
if (arr[j - increment] > tmp)
arr[j] = arr[j - increment];
else
break;
}
arr[j] = tmp;
}
}
}
/**************************************************************************/
/* 簡單選擇排序(simple selection sort) 就是通過n-i次關(guān)鍵字之間的比較,從n-i+1
* 個(gè)記錄中選擇關(guān)鍵字最小的記錄,并和第i(1<=i<=n)個(gè)記錄交換之
* 盡管與冒泡排序同為O(n^2),但簡單選擇排序的性能要略優(yōu)于冒泡排序 */
void SelectSort(int arr[], int num)
{
int i, j, Mindex;
for (i = 0; i < num; i++)
{
Mindex = i;
for (j = i + 1; j < num; j++)
{
if (arr[j] < arr[Mindex])
Mindex = j;
}
swap1(&arr[i], &arr[Mindex]);
}
}
/********************************************************************************/
/*假設(shè)初始序列含有n個(gè)記錄,則可以看成n個(gè)有序的子序列,每個(gè)子序列的長度為1,然后
* 兩兩歸并,得到(不小于n/2的最小整數(shù))個(gè)長度為2或1的有序子序列,再兩兩歸并,...
* 如此重復(fù),直至得到一個(gè)長度為n的有序序列為止,這種排序方法稱為2路歸并排序
* 時(shí)間復(fù)雜度為O(nlogn),空間復(fù)雜度為O(n+logn),如果非遞歸實(shí)現(xiàn)歸并,則避免了遞歸時(shí)深度為logn的棧空間
* 空間復(fù)雜度為O(n) */
/*lpos is the start of left half, rpos is the start of right half*/
void merge(int a[], int tmp_array[], int lpos, int rpos, int rightn)
{
int i, leftn, num_elements, tmpos;
leftn = rpos - 1;
tmpos = lpos;
num_elements = rightn - lpos + 1;
/*main loop*/
while (lpos <= leftn && rpos <= rightn)
if (a[lpos] <= a[rpos])
tmp_array[tmpos++] = a[lpos++];
else
tmp_array[tmpos++] = a[rpos++];
while (lpos <= leftn) /*copy rest of the first part*/
tmp_array[tmpos++] = a[lpos++];
while (rpos <= rightn) /*copy rest of the second part*/
tmp_array[tmpos++] = a[rpos++];
/*copy array back*/
for (i = 0; i < num_elements; i++, rightn--)
a[rightn] = tmp_array[rightn];
}
void msort(int a[], int tmp_array[], int left, int right)
{
int center;
if (left < right)
{
center = (right + left) / 2;
msort(a, tmp_array, left, center);
msort(a, tmp_array, center + 1, right);
merge(a, tmp_array, left, center + 1, right);
}
}
void merge_sort(int a[], int n)
{
int *tmp_array;
tmp_array = (int *)malloc(n * sizeof(int));
if (tmp_array != NULL)
{
msort(a, tmp_array, 0, n - 1);
free(tmp_array);
}
else
printf("No space for tmp array!\n");
}
【參考】
[1] 《大話數(shù)據(jù)結(jié)構(gòu)》
[2] 十種排序算法總結(jié)
