「@Author：Runsen」

插入排序

插入排序（英語(yǔ)：Insertion Sort）是一種簡(jiǎn)單直觀的排序算法。

一個(gè)有序的數(shù)組，我們往里面添加一個(gè)新的數(shù)據(jù)后，如何繼續(xù)保持?jǐn)?shù)據(jù)有序呢？很簡(jiǎn)單，我們只要遍歷數(shù)組，找到數(shù)據(jù)應(yīng)該插入的位置將其插入即可。

通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

插入排序在實(shí)現(xiàn)上，在從后向前掃描過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。

因此，代碼編寫(xiě)需要判斷插入元素和當(dāng)前元素的大小關(guān)系，遍歷時(shí)需要從數(shù)組的第二個(gè)數(shù)開(kāi)始。

如果插入元素大于當(dāng)前元素，則將待插入元素插入到當(dāng)前元素的后一位。

如果插入元素小于當(dāng)前元素，則將當(dāng)前元素后移一位。直到找到一個(gè)當(dāng)前元素小于插入元素。

因此，在for循環(huán)遍歷時(shí)，又有一個(gè)while內(nèi)循環(huán)的條件，條件的內(nèi)容是插入元素的索引減一和零進(jìn)行對(duì)比。如果插入元素小于當(dāng)前元素，同時(shí)對(duì)索引進(jìn)行減一操作。如果出現(xiàn)了索引等于零的情況，那么表示插入元素等于當(dāng)前元素。

下面是插入排序的具體Python代碼。

def?insert_sort(a):
????length?=?len(a)
????if?length?<=?1:
????????return?a
????#?從數(shù)組的第二個(gè)數(shù)開(kāi)始
????for?i?in?range(1,?length):
????????#?從后向前掃描
????????j?=?i?-?1
????????#?value指的是插入元素
????????value?=?a[i]
????????while?j?>=?0:
????????????if?a[j]?????????????????#?插入元素大于當(dāng)前元素，則將待插入元素插入到當(dāng)前元素的后一位
????????????????a[j?+?1]?=?value
????????????????break
????????????else:
????????????????#?插入元素小于當(dāng)前元素，則將當(dāng)前元素后移一位
????????????????a[j?+?1]?=?a[j]
????????????????if?j?==?0:
????????????????????a[j]?=?value
????????????j?-=?1
????return?a


def?insertionSort(arr):
????#?對(duì)上面的代碼進(jìn)行簡(jiǎn)單化
????for?i?in?range(len(arr)):
????????preIndex?=?i?-?1
????????current?=?arr[i]
????????while?preIndex?>=?0?and?arr[preIndex]?>?current:
????????????arr[preIndex?+?1]?=?arr[preIndex]
????????????preIndex?-=?1
????????arr[preIndex?+?1]?=?current
????return?arr

if?__name__?==?'__main__':
????nums?=?[54,?26,?93,?17,?77,?31,?44,?55,?20]
????insert_sort(nums)
????print(nums)?#?[17,?20,?26,?31,?44,?54,?55,?77,?93]

下面對(duì)Python代碼改為Java代碼。代碼來(lái)自菜鳥(niǎo)教程。

//?Java
import?java.util.Arrays;

public?class?Solution?{
????public?static?void?main(String[]?args)?{
????????InsertSort(new?int[]?{?9?,20?,?10,?13?,?12});
????}
????public?static?void?InsertSort(int?[]?arr){
????????int?value;?//待插入元素
????????int?index;?//初始值為待插入元素前一個(gè)元素的索引

????????for(int?i=?1?;?i????????????//i從第二個(gè)元素開(kāi)始，默認(rèn)第一個(gè)元素是有序的
????????????//循環(huán)條件是小于數(shù)組長(zhǎng)度，因?yàn)橐惨獙⒆詈笠粋€(gè)元素插入到前面的序列
????????????value?=?arr[i];
????????????index?=?i?-?1;//初始為前一個(gè)元素
????????????while(index?>=0?&&?value?????????????????//需要保證index合法
????????????????//每當(dāng)前面的元素比待插入元素大，就向后移動(dòng)
????????????????arr[index?+?1]?=?arr[index];
????????????????//不用怕覆蓋，因?yàn)関alue保存著待插入的值
????????????????index--;
????????????}
????????????//當(dāng)退出循環(huán)，表明已經(jīng)找到了待插入位置，即index?+?1
????????????arr[index?+?1]?=?value;
????????}

????????System.out.println(Arrays.toString(arr));
????}
}

下面對(duì)Python代碼改為JavaScript代碼。代碼來(lái)自菜鳥(niǎo)教程。

//?JavaScript
function?insertionSort(arr)?{
????var?len?=?arr.length;
????//?JavaScript需要聲明變量先
????var?preIndex,?current;
????for?(var?i?=?1;?i?????????preIndex?=?i?-?1;
????????current?=?arr[i];
????????while(preIndex?>=?0?&&?arr[preIndex]?>?current)?{
????????????arr[preIndex+1]?=?arr[preIndex];
????????????preIndex--;
????????}
????????arr[preIndex+1]?=?current;
????}
????return?arr;
}

對(duì)于不同的查找插入點(diǎn)方法（從頭到尾、從尾到頭），元素的比較次數(shù)是有區(qū)別的。但對(duì)于一個(gè)給定的初始序列，移動(dòng)操作的次數(shù)總是固定的，就等于逆序度。

在插入排序中，對(duì)于值相同的元素，我們可以選擇將后面出現(xiàn)的元素，插入到前面出現(xiàn)元素的后面，這樣就可以保持原有的前后順序不變，所以插入排序是穩(wěn)定的排序算法。

對(duì)于插入排序來(lái)說(shuō)，每次插入操作都相當(dāng)于在數(shù)組中插入一個(gè)數(shù)據(jù)，循環(huán)執(zhí)行 n 次插入操作，所以平均時(shí)間復(fù)雜度為 O(n2)。

如果輸入數(shù)組已經(jīng)是排好序的話，插入排序出現(xiàn)最佳情況，其運(yùn)行時(shí)間是輸入規(guī)模的一個(gè)線性函數(shù)，其時(shí)間代價(jià)是O(n)。

如果輸入數(shù)組是逆序排列的，將出現(xiàn)最壞情況。平均情況與最壞情況一樣，其時(shí)間代價(jià)是 O(n2)。

參考：https://www.runoob.com/w3cnote/insertion-sort.html

選擇排序

選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。

選擇排序算法的實(shí)現(xiàn)思路有點(diǎn)類似插入排序，也分已排序區(qū)間和未排序區(qū)間。但是選擇排序每次會(huì)從未排序區(qū)間中找到最小的元素，將其放到已排序區(qū)間的末尾。

它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

選擇排序：首先搜索整個(gè)列表，找到最小項(xiàng)的位置，如果該位置不是列表的第1項(xiàng)，就交換這兩個(gè)位置的元素。然后從列表的第2個(gè)元素開(kāi)始，重復(fù)上述過(guò)程，直到算法達(dá)到整個(gè)過(guò)程的最后一個(gè)位置，圖形解釋如下

選擇排序還有一種代碼的形式是將最大值逐一選擇到后面，因此遍歷的時(shí)候需要逆序遍歷。

def?selection_sort1(nums):
????#?思路是將最小值逐一選擇到前面
????n?=?len(nums)
????#?第一層for表示循環(huán)選擇的遍數(shù)

????for?i?in?range(n?-?1):
????????min_index?=?i??#?記錄最小值的位置
????????#?第二層for表示最小元素和后面的元素逐個(gè)比較

????????for?j?in?range(i?+?1,?n):
????????????if?nums[j]?????????????????min_index?=?j
????????if?min_index?!=?i:
???????????#?查找一遍后將最小元素與起始元素互換
????????????nums[i],?nums[min_index]?=?nums[min_index],?nums[i]

def?selection_sort2(nums):
????#?思路是將最大值逐一選擇到后面
????n?=?len(nums)
????for?i?in?range(n?-?1,?0,?-1):
????????max_index?=?i??#?記錄最大值的位置
????????for?j?in?range(i):
????????????if?nums[j]?>?nums[max_index]:
????????????????max_index?=?j
????????if?max_index?!=?i:
????????????nums[i],?nums[max_index]?=?nums[max_index],?nums[i]

下面對(duì)Python代碼改為Java代碼。代碼來(lái)自菜鳥(niǎo)教程，選擇第一種思路。

下面對(duì)Python代碼改為JavaScript代碼。代碼來(lái)自菜鳥(niǎo)教程。

function?selectionSort(arr)?{
????var?len?=?arr.length;
????var?minIndex,?temp;
????for?(var?i?=?0;?i?????????minIndex?=?i;
????????for?(var?j?=?i?+?1;?j?????????????if?(arr[j]?????????????????minIndex?=?j;?????????????????//?將最小數(shù)的索引保存
????????????}
????????}
????????temp?=?arr[i];
????????arr[i]?=?arr[minIndex];
????????arr[minIndex]?=?temp;
????}
????return?arr;
}

選擇排序是一種不穩(wěn)定的排序算法。選擇排序每次都要找剩余未排序元素中的最小值，并和前面的元素交換位置，這樣破壞了穩(wěn)定性。

當(dāng)出現(xiàn)幾個(gè)值相同的時(shí)候，比如 5，8，5，2，9這樣一組數(shù)據(jù)，使用選擇排序算法來(lái)排序的話，第一次找到最小元素 2，與第一個(gè) 5 交換位置，那第一個(gè) 5 和中間的 5 順序就變了，所以就不穩(wěn)定了。

選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)。如果某個(gè)元素位于正確的最終位置上，則它不會(huì)被移動(dòng)。選擇排序每次交換一對(duì)元素。

它們當(dāng)中至少有一個(gè)將被移到其最終位置上，因此對(duì)n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換。在所有的完全依靠交換。

無(wú)論數(shù)列初始狀態(tài)怎樣，在第 i 趟排序中選出最小關(guān)鍵字的記錄，需做n-i次比較，因此，總的比較次數(shù)為：n(n-1)/2=O(n2)。

因此直接選擇排序的平均時(shí)間復(fù)雜度為 O(n2)。直接選擇排序是一個(gè)就地排序，空間復(fù)雜度為S(n)=O(1)。

參考：https://www.runoob.com/w3cnote/selection-sort.html

參考：極客時(shí)間王爭(zhēng)算法專欄

?

本文已收錄 GitHub，傳送門~^[1] ，里面更有大廠面試完整考點(diǎn)，歡迎 Star。

?

Reference