今天我們來(lái)說(shuō)說(shuō)這三個(gè)經(jīng)典的排序，先說(shuō)一下結(jié)論：插入排序最好。

今天講的這三種排序都是適用于小規(guī)模排序的，相對(duì)而言是高效的，之后我再介紹大規(guī)模排序的適用算法!

首先我們來(lái)看看插入排序。

插入排序的思路就是將你要排序的數(shù)組分兩個(gè)區(qū)間，一個(gè)是已排序區(qū)間，一個(gè)是未排序區(qū)間，初始的時(shí)候默認(rèn)第一個(gè)元素是已排序區(qū)間的，后面的所有元素為未排序區(qū)間。然后呢依次取未排序區(qū)間的元素，在已排序區(qū)間找到合適的位置插入。直到未排序區(qū)間空了。

舉個(gè)例子:數(shù)組[3,2,5,1,4]。

注意我們這里的分區(qū)間只是我們主觀分法，實(shí)際上物理空間還是一個(gè)數(shù)組的，沒(méi)有分為兩個(gè)數(shù)組。來(lái)看下代碼

從代碼我們可以看出，插入排序是原地排序，不需要額外的空間！而且是穩(wěn)定排序的算法，時(shí)間的復(fù)雜度最好為O(n),最壞為O(n2),平均為O(n2)。

再來(lái)看看冒泡排序。

冒泡排序的思路就是相鄰的兩個(gè)數(shù)據(jù)進(jìn)行比較，需要交換就交換一下，每一次冒泡都會(huì)至少讓一個(gè)元素放到正確的位置，最多重復(fù)了N次，排序結(jié)束。

還是上面那個(gè)數(shù)組[3,2,5,1,4]。

這樣冒泡下去直到全部有序！以下是代碼。

從代碼我們可以看出，冒泡排序是原地排序，不需要額外的空間！而且是穩(wěn)定排序的算法，時(shí)間的復(fù)雜度最好為O(n),最壞為O(n2),平均為O(n2)。

最后來(lái)看看選擇排序

選擇排序也是分兩個(gè)區(qū)間，已排序區(qū)間和未排序區(qū)間，每次從未排序區(qū)間里面選擇最小的放入已排序區(qū)間尾部。

再來(lái)看一下代碼

從代碼我們可以看出，選擇排序是原地排序，不需要額外的空間！但是是不穩(wěn)定排序的算法！時(shí)間的復(fù)雜度最好,最壞為,平均都為O(n2)。

比如數(shù)組A[3,4,3,2]。第一次找到最小的2和3換了一下，那第一個(gè)3和第二個(gè)3位置順序就變化了所以不穩(wěn)定了！

所以從時(shí)間復(fù)雜度和穩(wěn)定的角度來(lái)說(shuō)，冒泡和插入排序比選擇排序好！

那插入排序?yàn)槭裁幢让芭菖判蚝媚兀?/p>

對(duì)比兩種算法的核心比較代碼，冒泡需要3個(gè)賦值，而排序只要一個(gè)賦值，我們知道每一個(gè)語(yǔ)句執(zhí)行是有時(shí)間的，所以冒泡的總耗時(shí)會(huì)比插入多！

所以插入排序更好！

建議大家看了之后自己代碼實(shí)現(xiàn)以下，加深記憶！