2、選擇排序（Selection Sort）

選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理：首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。 

2.1 算法描述

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

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

2.2 動圖演示

2.3 代碼實現(xiàn)

2.4 算法分析

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

3、插入排序（Insertion Sort）

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

3.1 算法描述

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

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

3.2 動圖演示

3.2 代碼實現(xiàn)

3.4 算法分析

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

4、希爾排序（Shell Sort）

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

4.1 算法描述

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

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

4.2 動圖演示

4.3 代碼實現(xiàn)

4.4 算法分析

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