下圖是常用排序算法的時(shí)間復(fù)雜度，可以看到冒泡、選擇、插入排序的時(shí)間復(fù)雜度相當(dāng)，但選擇排序不穩(wěn)定，冒泡、插入排序勝出。快速排序的更快，更適合數(shù)據(jù)量大的情況，冒泡和插入更適合數(shù)據(jù)本身相對(duì)有序的情況?？焖倥判蛞彩遣环€(wěn)定的。這里n代表數(shù)據(jù)規(guī)模及數(shù)據(jù)量大?。籌n-place: 不占用額外內(nèi)存，只占用常數(shù)內(nèi)存；Out-place: 占用額外內(nèi)存。

1. 冒泡排序

冒泡排序是排序算法中較為簡單的一種，英文稱為Bubble Sort。它遍歷所有的數(shù)據(jù)，每次對(duì)相鄰元素進(jìn)行兩兩比較，如果順序和預(yù)先規(guī)定的順序不一致，則進(jìn)行位置交換；這樣一次遍歷會(huì)將最大或最小的數(shù)據(jù)上浮到頂端，之后再重復(fù)同樣的操作，直到所有的數(shù)據(jù)有序。

2. 選擇排序

選擇排序簡單直觀，英文稱為Selection Sort，先在數(shù)據(jù)中找出最大或最小的元素，放到序列的起始；然后再從余下的數(shù)據(jù)中繼續(xù)尋找最大或最小的元素，依次放到排序序列中，直到所有數(shù)據(jù)樣本排序完成。

3. 插入排序

它通過構(gòu)建有序序列，對(duì)于未排序的數(shù)據(jù)序列，在已排序序列中從后向前掃描，找到相應(yīng)的位置并插入，類似打撲克牌時(shí)的碼牌。

基本思路是先將待排序序列的第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列；然后從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置，直到所有數(shù)據(jù)都完成排序；如果待插入的元素與有序序列中的某個(gè)元素相等，則將待插入元素插入到相等元素的后面。

4. 歸并排序

歸并排序采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。它首先將數(shù)據(jù)樣本拆分為兩個(gè)子數(shù)據(jù)樣本, 并分別對(duì)它們排序, 最后再將兩個(gè)子數(shù)據(jù)樣本合并在一起; 拆分后的兩個(gè)子數(shù)據(jù)樣本序列, 再繼續(xù)遞歸的拆分為更小的子數(shù)據(jù)樣本序列, 再分別進(jìn)行排序, 直到最后數(shù)據(jù)序列為1，而不再拆分，此時(shí)即完成對(duì)數(shù)據(jù)樣本的最終排序。

歸并排序嚴(yán)格遵循從左到右或從右到左的順序合并子數(shù)據(jù)序列, 它不會(huì)改變相同數(shù)據(jù)之間的相對(duì)順序, 因此歸并排序是一種穩(wěn)定的排序算法.

5. 快速排序

快速排序使用分治法（Divide and conquer）策略來把一個(gè)序列（list）分為兩個(gè)子序列（sub-lists）。首先從數(shù)列中挑出一個(gè)元素，并將這個(gè)元素稱為「基準(zhǔn)」，英文pivot。重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。之后，在子序列中繼續(xù)重復(fù)這個(gè)方法，直到最后整個(gè)數(shù)據(jù)序列排序完成。