本文分析冒泡、選擇了赵、插入潜支、希爾、快速柿汛、歸并和堆排序冗酿，為不影響閱讀體驗(yàn)埠对，將關(guān)于時(shí)間、空間復(fù)雜度和穩(wěn)定性的概念放在博文后半部分裁替，建議在閱讀每種算法指標(biāo)分析前先理解這些概念项玛。為了對(duì)以下各個(gè)算法進(jìn)行方便的測(cè)試，測(cè)試主方法體如下（Java實(shí)現(xiàn)）：
public class Sort {
public static void main(String[] args) {
int[] input = {5, 4, 7, 1, 6, 2, 8, 9, 10};
//此處調(diào)用方法弱判，以調(diào)用冒泡排序?yàn)槔? bubbleSort(input);
for (int i = 1; i <= input.length; i++) {
System.out.println(input[i - 1]);
}
}
}
本篇博文所有排序?qū)崿F(xiàn)均默認(rèn)從小到大襟沮。
冒泡排序（Bubble Sort）
每一次通過兩兩比較找到最大（小）的元素放在未排序序列的最后昌腰，直至有序开伏。
步驟
- 比較兩個(gè)相鄰的元素。如果前面比后面?zhèn)€大（性馍獭）固灵，就交換順序。
- 從第1個(gè)數(shù)與第2個(gè)數(shù)開始比較劫流，直到第n-1個(gè)數(shù)與第n個(gè)數(shù)結(jié)束巫玻。到最后，最大（徐艋恪）的數(shù)就"浮"在了最上面仍秤。
- 持續(xù)每次對(duì)前面越來越少的未排序元素重復(fù)上面的步驟，直到所有元素有序可很。
排序演示
源代碼（Java實(shí)現(xiàn)）
public static void bubbleSort(int[] input) {
for (int i = 1; i <= input.length; i++) {
for (int j = 1; j <= input.length - i; j++) {
if (input[j - 1] > input[j]) {
int temp = input[j - 1];
input[j - 1] = input[j];
input[j] = temp;
}
}
}
}
算法指標(biāo)分析
優(yōu)化1的最好時(shí)間復(fù)雜度：當(dāng)序列有序時(shí)诗力。第一個(gè)for循環(huán)中，第2/3/11/12行語句執(zhí)行1次根穷，即頻度為1姜骡；第二個(gè)for循環(huán)中，第4屿良、5圈澈、9行語句執(zhí)行n-1次，即頻度為n-1尘惧。T(n) = 3*(n-1)+4 = 3n+1 = O(n)康栈。所以最好時(shí)間復(fù)雜度為O(n)。
最壞時(shí)間復(fù)雜度：當(dāng)序列為逆序時(shí)喷橙。第一個(gè)for循環(huán)的頻度為n啥么；第二個(gè)for循環(huán)中，j可以取 1,2,...,n-1贰逾，所以第3/4/6/7/8語句悬荣，頻度均為(1+n-1)(n-1)/2。T(n) = n(n-1)/2+n = O(n2)疙剑。所以最壞時(shí)間復(fù)雜度為O(n2)氯迂。
我們可以看出在嵌套層數(shù)多的循環(huán)語句中践叠，由最內(nèi)層語句的頻度f(n)決定時(shí)間復(fù)雜度。
平均時(shí)間復(fù)雜度：O((n+n^2)/2) = O(n^2)嚼蚀。
輔助空間：不需要額臨時(shí)的存儲(chǔ)空間來運(yùn)行算法禁灼，所以為O(1)。
穩(wěn)定性：因?yàn)榕判蚍绞绞窍噜彅?shù)比較后交換轿曙，如果序列中有相等的兩個(gè)數(shù)弄捕，待兩數(shù)相鄰時(shí)，不會(huì)交換兩者的位置导帝，所以穩(wěn)定守谓。
冒泡排序的兩種優(yōu)化方式
優(yōu)化1：某一趟遍歷如果沒有元素交換，flag標(biāo)記依舊為true舟扎。說明已經(jīng)排好序了分飞，結(jié)束迭代悴务。
public static void bubbleSort2(int[] input) {
for (int i = 1; i <= input.length; i++) {
boolean flag = true;
for (int j = 1; j <= input.length - i; j++) {
if (input[j - 1] > input[j]) {
int temp = input[j - 1];
input[j - 1] = input[j];
input[j] = temp;
}
flag = false;
}
if (flag)
break;
}
}
優(yōu)化2：記錄某次遍歷時(shí)最后發(fā)生元素交換的位置（LastExchange）睹限，這個(gè)位置之后的數(shù)據(jù)顯然已經(jīng)有序，不用再排序了讯檐。因此通過記錄最后發(fā)生元素交換的位置就可以確定下次循環(huán)的范圍羡疗。
public static void bubbleSort3(int[] input) {
int LastExchange = input.length;
boolean flag = true;
for (int i = 1; i <= input.length; i++) {
int k = LastExchange;
for (int j = 1; j <= k - 1; j++) {
if (input[j - 1] > input[j]) {
int temp = input[j - 1];
input[j - 1] = input[j];
input[j] = temp;
}
LastExchange = j;
flag = false;
}
if (flag)
break;
}
}
選擇排序（Selection Sort）
每一次通過選擇找到未排序序列的最小（大）元素放在已排序序列的末尾（交換位置）别洪，直至有序叨恨。
步驟
- 未排序序列中找到最小（大）元素挖垛，存放到序列的起始位置痒钝。
- 再從剩余未排序元素中繼續(xù)找到最小（大）元素痢毒，放到已排序序列的末尾送矩。
- 以此類推，直到所有元素均排序完畢哪替。
排序演示
源代碼（Java實(shí)現(xiàn)）
public static void selectionSort(int[] input) {
for (int i = 1; i <= input.length; i++) {
int minIndex = i - 1;
for (int j = i; j < input.length; j++) {
if (input[minIndex] > input[j])
minIndex = j;
}
if (minIndex != i - 1) {
int temp = input[minIndex];
input[minIndex] = input[i - 1];
input[i - 1] = temp;
}
}
}
算法指標(biāo)分析
不管序列有序還是逆序栋荸，第二個(gè)for循環(huán)的頻度為n*(n-1)/2。所以最壞時(shí)間復(fù)雜度和最好時(shí)間復(fù)雜度均為O(n^2)凭舶。
平均時(shí)間復(fù)雜度：O(n^2)
輔助空間：不需要額臨時(shí)的存儲(chǔ)空間來運(yùn)行算法晌块，所以為O(1)。
穩(wěn)定性：不穩(wěn)定帅霜。舉例匆背，5、7身冀、5钝尸、2蜂大、9，找到最小2時(shí)蝶怔，2與5交換奶浦，此時(shí)兩個(gè)5的相對(duì)位置發(fā)生改變。
插入排序（Insertion Sort）
對(duì)于每個(gè)未排序元素踢星，在已排序序列中從后向前掃描澳叉，找到相應(yīng)位置并插入。
步驟
- 第1個(gè)元素視為已經(jīng)被排序
- 取未排序的第1個(gè)元素沐悦，在已排序序列中從后向前掃描
- 如果被掃描的元素大于新元素成洗，將該元素后移一位
- 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復(fù)步驟2~5
- 如果全部有序藏否，結(jié)束迭代
排序演示
源代碼(Java實(shí)現(xiàn))
public static void insertionSort(int[] input) {
for (int i = 1; i < input.length; i++) {
for (int j = i; j > 0; j--) {
if (input[j] < input[j - 1]) {
int temp = input[j];
input[j] = input[j - 1];
input[j - 1] = temp;
}
else break;
}
}
}
算法指標(biāo)分析
最好時(shí)間復(fù)雜度：當(dāng)序列有序時(shí)瓶殃。當(dāng)?shù)谝粋€(gè)for循環(huán)運(yùn)行時(shí)，在第二個(gè)for循環(huán)中副签，因?yàn)樾蛄杏行蛞４唬灾粫?huì)相鄰比較1次，就跳出循環(huán)淆储。所以兩個(gè)循環(huán)的頻度均為n-1冠场，所以最好時(shí)間復(fù)雜度均為O(n)。
最壞時(shí)間復(fù)雜度：當(dāng)序列逆序時(shí)本砰。第二個(gè)for循環(huán)的頻度為n(n-1)/2碴裙。所以最壞時(shí)間復(fù)雜度均為O(n^2)。
平均時(shí)間復(fù)雜度：O((n+n^2)/2) = O(n^2)点额。
輔助空間：不需要額臨時(shí)的存儲(chǔ)空間來運(yùn)行算法舔株，所以為O(1)。
穩(wěn)定性：因?yàn)榕判蚍绞绞莾蓛杀容^还棱，序列中如果相鄰兩個(gè)數(shù)相等载慈，不會(huì)交換兩者的位置，所以穩(wěn)定诱贿。
希爾排序（Shell Sort）
希爾排序娃肿，也稱遞減增量排序算法，實(shí)質(zhì)上是一種分組插入排序算法珠十。是插入排序的一種更高效的改進(jìn)版本料扰。
希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
- 插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高焙蹭，即可以達(dá)到線性排序的效率
- 但插入排序一般來說是低效的晒杈，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位
步驟
- 假設(shè)數(shù)組為
{5, 4, 7, 1, 6, 2, 8, 9, 10}，如果我們以步長為4開始進(jìn)行排序孔厉，我們可以通過將這列表放在有4列的表中來更好地描述算法拯钻，這樣他們就應(yīng)該看起來是這樣：
5, 4, 7, 1
6, 2, 8, 9
10
- 將數(shù)組列在一個(gè)表中并對(duì)列分別進(jìn)行插入排序
5, 2, 7, 1
6, 4, 8, 9
10
- 重復(fù)這過程帖努，不過每次用更長的列（步長更小，列數(shù)更少）來進(jìn)行粪般，如下步長為2拼余。
5, 2
7, 1
6, 4
8, 9
10
- 最后整個(gè)表就只有一列了（ 再進(jìn)行插入排序）
5, 1, 6, 2, 7, 4, 8, 9, 10
源代碼（Java實(shí)現(xiàn)）
public static void shellSort(int[] input) {
int len = input.length, j;
int gap = Math.round(len / 2);
for (; gap > 0; gap /= 2) //步長每次就減少一倍
for (int i = gap; i < len; i++) {
int temp = input[i];
for (j = i - gap; j >= 0 && temp < input[j]; j -= gap) {//列排序
input[j + gap] = input[j];
input[j] = temp;
}
}
}
算法指標(biāo)分析
最好時(shí)間復(fù)雜度：當(dāng)序列有序時(shí)。最好時(shí)間復(fù)雜度均為O(n^s)亩歹，1<s<2匙监，跟算法步長有關(guān)。
最壞時(shí)間復(fù)雜度：當(dāng)序列逆序時(shí)小作。最壞時(shí)間復(fù)雜度均為O(n^2)亭姥。
平均時(shí)間復(fù)雜度：O(n log n)~O(n^2)。
輔助空間：不需要額臨時(shí)的存儲(chǔ)空間來運(yùn)行算法顾稀，所以為O(1)达罗。
穩(wěn)定性：不穩(wěn)定。解釋如下：
假設(shè)静秆，序列為5,5,7,3,2粮揉，取步長為3分組為
5,5,7
3,6
3和5交換位置后，兩個(gè)5的相對(duì)順序發(fā)生改變诡宗，所以不穩(wěn)定
堆排序（HeapSort）
使用到二叉堆這種數(shù)據(jù)結(jié)構(gòu)滔蝉，二叉堆是平衡二叉樹。它具有以下性質(zhì)：
- 父節(jié)點(diǎn)的值大于等于左右節(jié)點(diǎn)的值塔沃，為最大堆（大頂堆）；父節(jié)點(diǎn)的值小于于等于左右節(jié)點(diǎn)的值阳谍，為最小堆（大頂堆）
- 每個(gè)父節(jié)點(diǎn)的左右節(jié)點(diǎn)都是二叉堆（大頂堆或小頂堆）
本質(zhì)上堆排序是由數(shù)組實(shí)現(xiàn)蛀柴。
步驟
- 調(diào)用構(gòu)造大頂堆方法，將數(shù)組構(gòu)造成大頂堆矫夯。葉子節(jié)點(diǎn)相當(dāng)于大頂堆鸽疾，假設(shè)數(shù)組下標(biāo)范圍為0~n-1，則從下標(biāo)n/2開始的元素（葉子節(jié)點(diǎn)）均為大頂堆训貌。所以從下標(biāo)n/2-1開始的元素（父節(jié)點(diǎn)）開始制肮，向前依次（下標(biāo)減1）構(gòu)造大頂堆。
- 堆排序：由于堆是用數(shù)組模擬的递沪。構(gòu)造的大頂堆相當(dāng)于在數(shù)組中無序豺鼻。因此需要將數(shù)組有序化。思想是循環(huán)將根節(jié)點(diǎn)與最后一個(gè)未排序元素交換款慨，再調(diào)用構(gòu)造大頂堆方法儒飒。循環(huán)結(jié)束后，整個(gè)數(shù)組就是有序的了檩奠。
- 構(gòu)造大頂堆方法：調(diào)整節(jié)點(diǎn)桩了，使得左右子節(jié)點(diǎn)小于父節(jié)點(diǎn)附帽，保證根節(jié)點(diǎn)是當(dāng)前堆中最大的元素。
排序演示：
第一次將數(shù)組構(gòu)造成大頂堆時(shí)井誉，跟此演示稍有不同蕉扮，默認(rèn)按數(shù)組順序放入二叉堆，沒有邊放邊構(gòu)造颗圣。
源代碼（Java實(shí)現(xiàn)）
public static void heapSort(int[] input) {
int i = input.length / 2 - 1;//最后一個(gè)非葉子節(jié)點(diǎn)
//將數(shù)組構(gòu)造成大頂堆
for (; i >= 0; i--)
maxHeapify(input, i, input.length - 1);
//堆排慢显，將大頂堆轉(zhuǎn)換成有序數(shù)組
for (i = input.length - 1; i >= 0; i--) {
int temp = input[0];
input[0] = input[i];
input[i] = temp;
maxHeapify(input, 0, i - 1);
}
}
//構(gòu)造大頂堆
public static void maxHeapify(int[] input, int start, int end) {
int child;
int root = start;
//父節(jié)點(diǎn)不是葉子節(jié)點(diǎn)時(shí)循環(huán)；只有一個(gè)根節(jié)點(diǎn)時(shí)不再比較
for (; root <= (end - 1) / 2 && end > 0; ) {
child = root * 2 + 1;//調(diào)整子節(jié)點(diǎn)
//取較大的子節(jié)點(diǎn)
if (child + 1 <= end && input[child] < input[child + 1])
child += 1;
if (input[root] < input[child]) {
//交換較小父節(jié)點(diǎn)和較大子節(jié)點(diǎn)的位置
int temp = input[root];
input[root] = input[child];
input[child] = temp;
root = child;//較大的子節(jié)點(diǎn)成為父節(jié)點(diǎn)
} else
break;
}
}
算法指標(biāo)分析
最好時(shí)間復(fù)雜度：當(dāng)序列有序時(shí)欠啤。最好時(shí)間復(fù)雜度均為O(n log n)荚藻，跟算法步長有關(guān)。
最壞時(shí)間復(fù)雜度：當(dāng)序列逆序時(shí)洁段。最壞時(shí)間復(fù)雜度均為O(n log n)应狱。
平均時(shí)間復(fù)雜度：O(n log n)。
輔助空間：不需要額臨時(shí)的存儲(chǔ)空間來運(yùn)行算法祠丝，所以為O(1)疾呻。
穩(wěn)定性：不穩(wěn)定。
二分歸并排序（MergeSort）
先遞歸分解序列写半，再合并序列岸蜗。也采用了分治法的思想。
步驟
- 合并：合并的條件是兩個(gè)序列都有序叠蝇，當(dāng)序列中只有1個(gè)元素時(shí)我們認(rèn)為也是有序的璃岳；合并的方法是通過比較將較小元素先放入臨時(shí)數(shù)組，再將左悔捶、右序列剩余元素放入铃慷。
- 分解：先將源序列從中位數(shù)（中數(shù)）分開為左右序列，遞歸分解左序列蜕该，中數(shù)不斷減小犁柜，直到為1。此時(shí)左堂淡、右序列中只有一個(gè)元素馋缅，通過比較將左、右序列合并為左序列后绢淀，再遞歸分解右序列（也分解到只有一個(gè)元素）萤悴。
排序演示
此圖主要思想一致，但代碼實(shí)現(xiàn)過程中更啄，6531合并完成時(shí)稚疹，8724還沒分解。
源代碼（Java實(shí)現(xiàn)）
public static void mergeSort(int[] input) {
merge_sort(input, 0, input.length - 1);
}
public static void merge_sort(int[] input, int start, int end) {
int middle;
//當(dāng)序列中只有一個(gè)元素時(shí)，結(jié)束當(dāng)前遞歸
if (start < end) {
middle = (start + end) / 2;//找出中位數(shù)（中數(shù)）内狗，中數(shù)越來越小
merge_sort(input, start, middle);//中數(shù)左側(cè)序列二分
merge_sort(input, middle + 1, end);//中數(shù)右側(cè)序列二分
merge(input, start, middle, end);//合并成源序列
}
}
//合并成源序列
public static void merge(int[] input, int left, int middle, int right) {
int[] temp = new int[right - left + 1];//用于存放新排好序的序列
int i = left;//左序列的起始下標(biāo)
int j = middle + 1;//右序列的起始下標(biāo)
int n = 0;//temp[]數(shù)組的起始下標(biāo)
//通過比較將較小元素先放入temp數(shù)組
while (i <= middle && j <= right) {
if (input[i] < input[j]) {
temp[n] = input[i];
i++;
} else {
temp[n] = input[j];
j++;
}
n++;
}
//將第一個(gè)序列的剩余元素放入temp[]
while (i <= middle) {
temp[n] = input[i];
i++;
n++;
}
//將第二個(gè)序列的剩余元素放入temp[]
while (j <= right) {
temp[n] = input[j];
j++;
n++;
}
//將num[]中的元素復(fù)制到數(shù)組input
for (int x = 0, y = left; x <= n && y <= right; x++, y++)
input[y] = temp[x];
}
算法指標(biāo)分析
最好時(shí)間復(fù)雜度：當(dāng)序列有序時(shí)怪嫌。最好時(shí)間復(fù)雜度均為O(n log n)。
最壞時(shí)間復(fù)雜度：當(dāng)序列逆序時(shí)柳沙。最壞時(shí)間復(fù)雜度均為O(n log n)岩灭。
平均時(shí)間復(fù)雜度：O(n log n)。
輔助空間：需要新建額外臨時(shí)的存儲(chǔ)空間來存儲(chǔ)新排好序的序列赂鲤，每一次歸并都需要重新新建噪径，新建頻度為n，所以輔助空間為O(n)数初。
穩(wěn)定性：穩(wěn)定找爱。因?yàn)閮蓛杀容^。
快速排序（Quick Sort）
又稱劃分交換排序（partition-exchange sort）泡孩。采用了分治法的思想车摄，通常明顯比同為Ο(n log n)的其他算法更快。
步驟
- 將數(shù)組區(qū)塊的第n個(gè)素設(shè)為中數(shù)（中位值）仑鸥；第1個(gè)元素設(shè)為左數(shù)吮播；第n-1個(gè)元素設(shè)為右數(shù)。
- 左數(shù)下標(biāo)遞增眼俊，右數(shù)下標(biāo)遞減意狠。將大于等于中數(shù)的左數(shù)和小于等于中數(shù)的右數(shù)交換，直到左數(shù)和右數(shù)下標(biāo)相等疮胖。如果左(右)數(shù)大于等于中數(shù)环戈，交換位置，否則加左數(shù)下標(biāo)1获列。
- 對(duì)中數(shù)的左右數(shù)組區(qū)間遞歸執(zhí)行第1,2步谷市，直至各數(shù)組區(qū)間只有一個(gè)數(shù)。
排序演示
此演示的第1次選擇3作為中數(shù)击孩，與題意稍有出入，其他均相同鹏漆。
源代碼（Java實(shí)現(xiàn)）
public static void quickSort(int[] input) {
quick_sort(input, 0, input.length - 1);
}
private static void quick_sort(int[] input, int start, int end) {
if (start >= end) {
return;
}
int left = start, right = end - 1;
int mid = input[end];
while (left < right) {
while (input[left] <= mid && left < right) {
left++;
}
while (input[right] >= mid && left < right) {
right--;
}
int temp = input[left];
input[left] = input[right];
input[right] = temp;
}
if (input[left] >= input[end]) {
int temp = input[left];
input[left] = input[end];
input[end] = temp;
} else
left++;
quick_sort(input, start, left - 1);
quick_sort(input, left, end);
}
算法指標(biāo)分析
最好時(shí)間復(fù)雜度：當(dāng)序列有序時(shí)巩梢。所以，最好時(shí)間復(fù)雜度均為O(n log n)艺玲。
最壞時(shí)間復(fù)雜度：當(dāng)序列逆序時(shí)括蝠。所以，最壞時(shí)間復(fù)雜度均為O(n^2)饭聚。
平均時(shí)間復(fù)雜度：O(n log n)忌警。
輔助空間：需要額臨時(shí)的存儲(chǔ)空間來運(yùn)行算法，所以為O(n log n)~O(n)秒梳。
穩(wěn)定性：不穩(wěn)定法绵。
時(shí)間復(fù)雜度
時(shí)間頻度：一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例箕速，哪個(gè)算法中語句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多朋譬。一個(gè)算法中的語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度盐茎。記為T(n)。
時(shí)間復(fù)雜度：在剛才提到的時(shí)間頻度中徙赢，n稱為問題的規(guī)模字柠，當(dāng)n不斷變化時(shí)，時(shí)間頻度T(n)也會(huì)不斷變化狡赐。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律窑业。為此，我們引入時(shí)間復(fù)雜度概念枕屉。 一般情況下常柄，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T(n)表示搀庶，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時(shí)拐纱，T(n)/f(n)的極限值為不等于零的常數(shù)C，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)哥倔。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度秸架，簡稱時(shí)間復(fù)雜度。
雖然對(duì)f(n)沒有規(guī)定咆蒿，但是一般都是取盡可能簡單的函數(shù)东抹。例如，O(2n^2+n+1) = O(3n^2+n+3) = O(7n^2 + n) = O(n^2) 沃测，一般都只用O(n^2)表示就可以了缭黔。注意到大O符號(hào)里隱藏著一個(gè)常數(shù)C，所以f(n)里一般不加系數(shù)蒂破。如果把T(n)當(dāng)做一棵樹馏谨，那么O(f(n))所表達(dá)的就是樹干，只關(guān)心其中的主干附迷，其他的細(xì)枝末節(jié)全都拋棄不管惧互。
由上圖可見，常見的算法時(shí)間復(fù)雜度由小到大依次為：Ο(1)＜Ο(log n)＜Ο(n)＜Ο(nlog n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n)＜Ο(n!)喇伯。
分析以下代碼的時(shí)間復(fù)雜度喊儡。
i=1;
while (i<=n)
i=i*2;
第1行語句的頻度為1
設(shè)第3行語句的時(shí)間頻度為f(n)k，2f(n) = n; -->f(n) = log n
第2行語句跟第2三行的頻度一樣稻据，為log n
以上代碼的T(n) = 2log n+1 = O(log n)
由此可見艾猜，T(n)由最大的f(n)決定。在嵌套層數(shù)多的循環(huán)語句中，由最內(nèi)層語句的頻度f(n)決定T(n)匆赃。
注：log n = log?n = lg n淤毛；復(fù)雜度中以2為底，不是數(shù)學(xué)中以10為底炸庞。
空間復(fù)雜度
一個(gè)算法的空間復(fù)雜度(Space Complexity)定義為該算法所耗費(fèi)的存儲(chǔ)空間钱床，它也是問題規(guī)模n的函數(shù)。漸近空間復(fù)雜度也常常簡稱為空間復(fù)雜度埠居。
一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間查牌，包括：
- 存儲(chǔ)算法本身所占用的存儲(chǔ)空間
- 算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間
- 算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間
我們將算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間稱為輔助空間，它隨算法的不同而異滥壕，另外兩種存儲(chǔ)空間與算法本身無關(guān)纸颜。
如當(dāng)一個(gè)算法的空間復(fù)雜度為一個(gè)常量，即不隨被處理數(shù)據(jù)量n的大小而改變時(shí)绎橘，輔助空間可表示為O(1)胁孙；當(dāng)一個(gè)算法的空間復(fù)雜度與以2為底的n的對(duì)數(shù)成正比時(shí)，輔助空間可表示為O(1og?n)称鳞；當(dāng)一個(gè)算法的空間復(fù)雜度與n成線性比例關(guān)系時(shí)涮较，輔助空間可表示為O(n)。
穩(wěn)定性
在排序過程中冈止，具有相同數(shù)值的對(duì)象的相對(duì)順序被不被打亂狂票。如果可以保證不被打亂就是穩(wěn)定的，如果不能保證就是不穩(wěn)定的熙暴。
總結(jié)
根據(jù)每個(gè)排序算法關(guān)于穩(wěn)定性的指標(biāo)分析闺属，可以得出以下結(jié)論：
- 如果每次變換都只是交換相鄰的兩個(gè)元素，那么就是穩(wěn)定的周霉。
- 如果每次都有某個(gè)元素和比較遠(yuǎn)的元素的交換操作掂器，那么就是不穩(wěn)定的。
以上算法博主親測(cè)都能正確運(yùn)行俱箱。以下是上述七種算法的性能指標(biāo)分析對(duì)比情況国瓮。
| 排序方式 | 平均時(shí)間復(fù)雜度 | 最好時(shí)間復(fù)雜度 | 最壞時(shí)間復(fù)雜度 | 空間復(fù)雜度 （輔助空間） |
穩(wěn)定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
| 選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩(wěn)定 |
| 插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
| 希爾排序 | O(n log n)~O(n^2) | O(n^s) （0<s<1臊泌，跟步長有關(guān)） |
O(n^2) | O(1) | 不穩(wěn)定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不穩(wěn)定 |
| 二分歸并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 穩(wěn)定 |
| 快速排序 | O(n log n) | O(n log n) | O(n^2) | O(log n)~O(n) | 不穩(wěn)定 |
參考資料
- 維基百科：希爾排序 剧浸、快速排序
- 經(jīng)典排序算法總結(jié)與實(shí)現(xiàn) ---Python實(shí)現(xiàn)
- 白話經(jīng)典算法系列之一 冒泡排序的三種實(shí)現(xiàn)
- 幾種經(jīng)典排序算法
- 算法的時(shí)間復(fù)雜度和空間復(fù)雜度-總結(jié)
- 排序算法的穩(wěn)定性
