2、選擇排序（Selection Sort）

選擇排序(Selection-sort)是一種簡(jiǎn)單直觀的排序算法。它的工作原理：首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類(lèi)推，直到所有元素均排序完畢。 

2.1 算法描述

n個(gè)記錄的直接選擇排序可經(jīng)過(guò)n-1趟直接選擇排序得到有序結(jié)果。具體算法描述如下：

• 初始狀態(tài)：無(wú)序區(qū)為R[1..n]，有序區(qū)為空；
• 第i趟排序(i=1,2,3…n-1)開(kāi)始時(shí)，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當(dāng)前無(wú)序區(qū)中-選出關(guān)鍵字最小的記錄 R[k]，將它與無(wú)序區(qū)的第1個(gè)記錄R交換，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)；
• n-1趟結(jié)束，數(shù)組有序化了。

2.2 動(dòng)圖演示

2.3 代碼實(shí)現(xiàn)

2.4 算法分析

表現(xiàn)最穩(wěn)定的排序算法之一，因?yàn)闊o(wú)論什么數(shù)據(jù)進(jìn)去都是O(n²)的時(shí)間復(fù)雜度，所以用到它的時(shí)候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。理論上講，選擇排序可能也是平時(shí)排序一般人想到的最多的排序方法了吧。

3、插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

3.1 算法描述

一般來(lái)說(shuō)，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：

• 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序；
• 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；
• 如果該元素（已排序）大于新元素，將該元素移到下一位置；
• 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；
• 將新元素插入到該位置后；
• 重復(fù)步驟2~5。

3.2 動(dòng)圖演示

3.2 代碼實(shí)現(xiàn)

3.4 算法分析

插入排序在實(shí)現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。

4、希爾排序（Shell Sort）

1959年Shell發(fā)明，第一個(gè)突破O(n²)的排序算法，是簡(jiǎn)單插入排序的改進(jìn)版。它與插入排序的不同之處在于，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序又叫縮小增量排序。

4.1 算法描述

先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，具體算法描述：

• 選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；
• 按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；
• 每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。

4.2 動(dòng)圖演示

4.3 代碼實(shí)現(xiàn)

4.4 算法分析

希爾排序的核心在于間隔序列的設(shè)定。既可以提前設(shè)定好間隔序列，也可以動(dòng)態(tài)的定義間隔序列。動(dòng)態(tài)定義間隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的?！?/p>