2、選擇排序（Selection Sort）

選擇排(pai)(pai)序(xu)(xu)(Selection-sort)是一種簡單直觀(guan)的(de)(de)(de)排(pai)(pai)序(xu)(xu)算(suan)法。它的(de)(de)(de)工作原理(li)：首先在(zai)未排(pai)(pai)序(xu)(xu)序(xu)(xu)列中找(zhao)到最小(xiao)（大(da)）元(yuan)素(su)，存放到排(pai)(pai)序(xu)(xu)序(xu)(xu)列的(de)(de)(de)起(qi)始位(wei)置，然(ran)后，再從剩余未排(pai)(pai)序(xu)(xu)元(yuan)素(su)中繼續尋找(zhao)最小(xiao)（大(da)）元(yuan)素(su)，然(ran)后放到已排(pai)(pai)序(xu)(xu)序(xu)(xu)列的(de)(de)(de)末尾。以此類推，直到所(suo)有元(yuan)素(su)均排(pai)(pai)序(xu)(xu)完畢。 

2.1 算法描述

n個記錄的(de)直接(jie)選(xuan)擇排序(xu)可經過n-1趟直接(jie)選(xuan)擇排序(xu)得到有序(xu)結果。具(ju)體算法(fa)描(miao)述如下：

• 初始狀態：無序區為R[1..n]，有序區為空；
• 第i趟排序(i=1,2,3…n-1)開始時，當前有序區和無序區分別為R[1..i-1]和R(i..n）。該趟排序從當前無序區中-選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R[i+1..n)分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區；
• n-1趟結束，數組有序化了。

2.2 動圖演示

2.3 代碼實現

2.4 算法分析

表現最穩定的排序算法之一，因為無論什么數據進去都是O(n²)的(de)(de)時間復雜度，所(suo)以用到(dao)它的(de)(de)時候，數(shu)據規模越小越好。唯一(yi)的(de)(de)好處(chu)可能(neng)就是不占(zhan)用額外的(de)(de)內(nei)存空間了吧。理(li)論(lun)上講，選擇排序可能(neng)也是平(ping)時排序一(yi)般人想到(dao)的(de)(de)最多的(de)(de)排序方法了吧。

3、插入排序（Insertion Sort）

插(cha)入排序(xu)（Insertion-Sort）的算法描述(shu)是(shi)一種簡單直觀的排序(xu)算法。它的工作原理(li)是(shi)通過(guo)構建有序(xu)序(xu)列，對于(yu)未排序(xu)數據，在已排序(xu)序(xu)列中從后向前掃描，找到(dao)相(xiang)應位置并插(cha)入。

3.1 算法描述

一般來說，插(cha)入排序都采用in-place在(zai)數組(zu)上實現。具體算(suan)法(fa)描(miao)述如下：

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

3.2 動圖演示

3.2 代碼實現

3.4 算法分析

插入排序在(zai)實現上(shang)，通常采(cai)用(yong)in-place排序（即(ji)只(zhi)需用(yong)到O(1)的額外(wai)空間(jian)的排序），因而在(zai)從后(hou)向(xiang)前掃描過程中，需要反復把已排序元(yuan)素逐步(bu)向(xiang)后(hou)挪位(wei)，為最新元(yuan)素提供插入空間(jian)。

4、希爾排序（Shell Sort）

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

4.1 算法描(miao)述

先將整個待排(pai)序的記(ji)錄(lu)序列分割成(cheng)為若干(gan)子(zi)序列分別(bie)進行直接插入排(pai)序，具體算法(fa)描述：

• 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
• 按增量序列個數k，對序列進行k 趟排序；
• 每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

4.2 動圖演示

4.3 代碼實現

4.4 算法分析

希爾排序的(de)(de)核心在于間(jian)隔(ge)序列的(de)(de)設(she)(she)定。既(ji)可以(yi)(yi)提前設(she)(she)定好(hao)間(jian)隔(ge)序列，也可以(yi)(yi)動(dong)態的(de)(de)定義(yi)間(jian)隔(ge)序列。動(dong)態定義(yi)間(jian)隔(ge)序列的(de)(de)算法是(shi)《算法（第4版）》的(de)(de)合著(zhu)者Robert Sedgewick提出的(de)(de)。