一、插入排序

介紹

插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)。

算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為O(n^2)。

插入排算法是穩(wěn)定的排序方法。

步驟

①?gòu)牡谝粋€(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序

②取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描

③如果該元素（已排序）大于新元素，將該元素移到下一位置

④重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置

⑤將新元素插入到該位置中

⑥重復(fù)步驟2

排序演示

算法實(shí)現(xiàn)

二、冒泡排序

介紹

冒泡排序（Bubble Sort）是一種簡(jiǎn)單的排序算法，時(shí)間復(fù)雜度為O(n^2)。

它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。

這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

原理

循環(huán)遍歷列表，每次循環(huán)找出循環(huán)最大的元素排在后面；

需要使用嵌套循環(huán)實(shí)現(xiàn)：外層循環(huán)控制總循環(huán)次數(shù)，內(nèi)層循環(huán)負(fù)責(zé)每輪的循環(huán)比較。

步驟

①比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

②對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。

③針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

④持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

算法實(shí)現(xiàn)：

三、快速排序

介紹

快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)，借用了分治的思想，由C. A. R. Hoare在1962年提出。

基本思想

快速排序的基本思想是：挖坑填數(shù) + 分治法。

首先選出一個(gè)軸值(pivot，也有叫基準(zhǔn)的)，通過(guò)一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。

實(shí)現(xiàn)步驟

①?gòu)臄?shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）；

②重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）；

③對(duì)所有兩個(gè)小數(shù)列重復(fù)第二步，直至各區(qū)間只有一個(gè)數(shù)。

排序演示

算法實(shí)現(xiàn)

四、希爾排序

介紹

希爾排序（Shell Sort）是插入排序的一種，也是縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法，時(shí)間復(fù)雜度為：O(1.3n)。

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

·插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)， 效率高， 即可以達(dá)到線性排序的效率；

·但插入排序一般來(lái)說(shuō)是低效的， 因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位。

基本思想

①希爾排序是把記錄按下標(biāo)的一定量分組，對(duì)每組使用直接插入算法排序；

②隨著增量逐漸減少，每組包1含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法被終止。

排序演示

算法實(shí)現(xiàn)

五、選擇排序

介紹

選擇排序(Selection sort)是一種簡(jiǎn)單直觀的排序算法，時(shí)間復(fù)雜度為Ο(n2)。

基本思想

選擇排序的基本思想：比較 + 交換。

第一趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；

第二趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；

以此類(lèi)推，第 i 趟，在待排序記錄ri ~ r[n]中選出最小的記錄，將它與r[i]交換,使有序序列不斷增長(zhǎng)直到全部排序完畢。

排序演示

選擇排序的示例動(dòng)畫(huà)。紅色表示當(dāng)前最小值，黃色表示已排序序列，藍(lán)色表示當(dāng)前位置。

算法實(shí)現(xiàn)

六、堆排序

介紹

堆排序（Heapsort）是指利用堆積樹(shù)（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。

利用數(shù)組的特點(diǎn)快速指定索引的元素。

基本思想

堆分為大根堆和小根堆，是完全二叉樹(shù)。

大根堆的要求是每個(gè)節(jié)點(diǎn)的值不大于其父節(jié)點(diǎn)的值，即A[PARENT[i]] >=A[i]。

在數(shù)組的非降序排序中，需要使用的就是大根堆，因?yàn)楦鶕?jù)大根堆的要求可知，最大的值一定在堆頂。

排序演示

算法實(shí)現(xiàn)

七、歸并排序

介紹

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。

基本思想

歸并排序算法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。

算法思想

自上而下遞歸法（假如序列共有n個(gè)元素）

① 將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作，形成 floor(n/2)個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素；

② 將上述序列再次歸并，形成 floor(n/4)個(gè)序列，每個(gè)序列包含四個(gè)元素；

③ 重復(fù)步驟②，直到所有元素排序完畢。

自下而上迭代法

① 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列；

② 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；

③ 比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置；

④ 重復(fù)步驟③直到某一指針達(dá)到序列尾；

⑤ 將另一序列剩下的所有元素直接復(fù)制到合并序列尾。

排序演示

算法實(shí)現(xiàn)

八、基數(shù)排序

介紹

基數(shù)排序（Radix Sort）屬于“分配式排序”，又稱為“桶子法”。

基數(shù)排序法是屬于穩(wěn)定性的排序，其時(shí)間復(fù)雜度為O (nlog(r)m) ，其中 r 為采取的基數(shù)，而m為堆數(shù)。

在某些時(shí)候，基數(shù)排序法的效率高于其他的穩(wěn)定性排序法。

基本思想

將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開(kāi)始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后，數(shù)列就變成一個(gè)有序序列。

基數(shù)排序按照優(yōu)先從高位或低位來(lái)排序有兩種實(shí)現(xiàn)方案：

MSD（Most significant digital） 從最左側(cè)高位開(kāi)始進(jìn)行排序。先按k1排序分組, 同一組中記錄, 關(guān)鍵碼k1相等,再對(duì)各組按k2排序分成子組, 之后, 對(duì)后面的關(guān)鍵碼繼續(xù)這樣的排序分組, 直到按最次位關(guān)鍵碼kd對(duì)各子組排序后. 再將各組連接起來(lái),便得到一個(gè)有序序列。MSD方式適用于位數(shù)多的序列。

LSD （Least significant digital）從最右側(cè)低位開(kāi)始進(jìn)行排序。先從kd開(kāi)始排序，再對(duì)kd-1進(jìn)行排序，依次重復(fù)，直到對(duì)k1排序后便得到一個(gè)有序序列。LSD方式適用于位數(shù)少的序列。

排序效果

算法實(shí)現(xiàn)

九、總結(jié)

各種排序的穩(wěn)定性、時(shí)間復(fù)雜度、空間復(fù)雜度的總結(jié)：

平方階O(n2)排序：各類(lèi)簡(jiǎn)單排序：直接插入、直接選擇和冒泡排序；

從時(shí)間復(fù)雜度來(lái)說(shuō)：

線性對(duì)數(shù)階O(nlog?n)排序：快速排序、堆排序和歸并排序；

O(n1+§))排序，§是介于0和1之間的常數(shù)：希爾排序 ；

線性階O(n)排序：基數(shù)排序，此外還有桶、箱排序。