排序算法概述

排序就是將一組對(duì)象按照某種邏輯順序重新排列的過(guò)程。比如，訂單按照日期排序的——這種排序很可能使用了某種排序算法。在計(jì)算時(shí)代早期，大家普遍認(rèn)為30% 的計(jì)算周期都用在了排序上。如果今天這個(gè)比例降低了，可能的原因之一是如今的排序算法更加高效，而并非排序的重要性降低了?，F(xiàn)在計(jì)算機(jī)的廣泛使用使得數(shù)據(jù)無(wú)處不在，而整理數(shù)據(jù)的第一步通常就是進(jìn)行排序。幾乎所有的計(jì)算機(jī)系統(tǒng)都實(shí)現(xiàn)了各種排序算法以供系統(tǒng)和用戶(hù)使用。

即使你只是使用標(biāo)準(zhǔn)庫(kù)中的排序函數(shù)，學(xué)習(xí)排序算法仍然有三大實(shí)際意義：

IT從業(yè)人員必備技能，也是互聯(lián)網(wǎng)公司面試的必考點(diǎn)；

類(lèi)似的技術(shù)也能有效解決其他類(lèi)型的問(wèn)題；

排序算法常常是我們解決其他問(wèn)題的第一步。

排序在商業(yè)數(shù)據(jù)處理和現(xiàn)代科學(xué)計(jì)算中有著重要的地位，它能夠應(yīng)用于事物處理、組合優(yōu)化、天體物理學(xué)、分子動(dòng)力學(xué)、語(yǔ)言學(xué)、基因組學(xué)、天氣預(yù)報(bào)和很多其他領(lǐng)域。其中一種排序算法（快速排序）甚至被譽(yù)為20 世紀(jì)科學(xué)和工程領(lǐng)域的十大算法之一。

數(shù)據(jù)結(jié)構(gòu)和算法中，關(guān)于排序有十大算法，包括冒泡排序，簡(jiǎn)單選擇排序，簡(jiǎn)單插入排序，歸并排序，堆排序，快速排序、希爾排序、計(jì)數(shù)排序，基數(shù)排序，桶排序。

一般在面試中最?？嫉氖?快速排序和歸并排序?，并且經(jīng)常有面試官要求現(xiàn)場(chǎng)寫(xiě)出這兩種排序的代碼。對(duì)這兩種排序的代碼一定要信手拈來(lái)才行。對(duì)于其他排序可能會(huì)要求比較各自的優(yōu)劣、各種算法的思想及其使用場(chǎng)景，還有要知道算法的時(shí)間和空間復(fù)雜度。

接下來(lái)將由易到難學(xué)習(xí)這十種算法：

1.冒泡排序

冒泡排序是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪(fǎng)過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過(guò)來(lái)。走訪(fǎng)數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)橄嚓P(guān)的元素會(huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

基本思路：

1、比較相鄰的元素。如果第一個(gè)比第二個(gè)大(小)，就交換它們兩個(gè)；

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

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

重復(fù)步驟1~2，直到排序完成。

*冒泡降序示例：*

原始數(shù)組

2.簡(jiǎn)單選擇排序

選擇排序的思想其實(shí)和冒泡排序有點(diǎn)類(lèi)似，都是在一次排序后把最小的元素放到最前面。但是過(guò)程不同，冒泡排序是通過(guò)相鄰的比較和交換。而選擇排序是通過(guò)對(duì)整體的選擇。

舉個(gè)例子，對(duì)5,3,8,6,4這個(gè)無(wú)序序列進(jìn)行簡(jiǎn)單選擇排序，首先要選擇5以外的最小數(shù)來(lái)和5交換，也就是選擇3和5交換，一次排序后就變成了3,5,8,6,4.對(duì)剩下的序列繼續(xù)進(jìn)行選擇和交換，最終就會(huì)得到一個(gè)有序序列。其實(shí)選擇排序可以看成冒泡排序的優(yōu)化，因?yàn)槠淠康南嗤?，只是選擇排序只有在確定了最小數(shù)的前提下才進(jìn)行交換，大大減少了交換的次數(shù)。

具體步驟

首先，找到數(shù)組中最大（?。┑哪莻€(gè)元素；

其次，將它和數(shù)組的第一個(gè)元素交換位置（如果第一個(gè)元素就是最大（小）元素那么它就和自己交換）；

再次，在剩下的元素中找到最大（?。┑脑?，將它與數(shù)組的第二個(gè)元素交換位置。如此往復(fù)，直到將整個(gè)數(shù)組排序。

簡(jiǎn)單選擇排序（降序）示例

原始數(shù)組：

3.簡(jiǎn)單插入排序

插入排序不是通過(guò)交換位置而是通過(guò)比較找到合適的位置插入元素來(lái)達(dá)到排序的目的的。相信大家都有過(guò)打撲克牌的經(jīng)歷，特別是牌數(shù)較大的。在分牌時(shí)可能要整理自己的牌，牌多的時(shí)候怎么整理呢？就是拿到一張牌，找到一個(gè)合適的位置插入。這個(gè)原理其實(shí)和插入排序是一樣的。

舉個(gè)例子，我們將要收到5,3,4,,8,6這幾張牌，我們先收到5這張牌，毫無(wú)疑問(wèn)，這張牌的位置是正確的，沒(méi)必要整理。接著收到了牌3，然后3要插到5前面，把5后移一位，變成3,5。接著又收到了牌4，現(xiàn)在我們會(huì)怎么做？把4插入到5前面，把5后移一位。

*具體步驟：*

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

為了給要插入的元素騰出空間，我們需要將插入位置之后的已排序元素在都向右移動(dòng)一位。

插入排序所需的時(shí)間取決于輸入中元素的初始順序。例如，對(duì)一個(gè)很大且其中的元素已經(jīng)有序（或接近有序）的數(shù)組進(jìn)行排序?qū)?huì)比對(duì)隨機(jī)順序的數(shù)組或是逆序數(shù)組進(jìn)行排序要快得多。

總的來(lái)說(shuō)，插入排序?qū)τ诓糠钟行虻臄?shù)組十分高效，也很適合小規(guī)模數(shù)組。

簡(jiǎn)單插入排序（降序）示例

原始數(shù)組：

4.希爾排序

一種基于插入排序的快速的排序算法(請(qǐng)大家先學(xué)習(xí)插入排序，了解基本的插入排序的思想。對(duì)于大規(guī)模亂序數(shù)組插入排序很慢，因?yàn)樵刂荒芤稽c(diǎn)一點(diǎn)地從數(shù)組的一端移動(dòng)到另一端。例如，如果主鍵最小的元素正好在數(shù)組的盡頭，要將它挪到正確的位置就需要N-1 次移動(dòng)。

希爾排序?yàn)榱思涌焖俣群?jiǎn)單地改進(jìn)了插入排序，也稱(chēng)為縮小增量排序，同時(shí)該算法是沖破O(n^2）的第一批算法之一。

希爾排序是把待排序數(shù)組按一定增量的分組，對(duì)每組使用直接插入排序算法排序；然后縮小增量繼續(xù)分組排序，隨著增量逐漸減少，每組包含的元素越來(lái)越多，當(dāng)增量減至 1 時(shí)，整個(gè)數(shù)組恰被分成一組，排序便完成了。這個(gè)不斷縮小的增量，就構(gòu)成了一個(gè)增量序列。

希爾排序（降序）示例

我們選擇增量的計(jì)算方式為：gap=數(shù)組的長(zhǎng)度/2，縮小增量繼續(xù)以gap = gap/2的方式，于是形成的增量序列為{7,3,1}。

3、

第三個(gè)增量為1，則第二次排序后數(shù)組被分為1組，進(jìn)行插入排序，形成最后的排序數(shù)組

希爾排序中的增量排序

在先前較大的增量下每個(gè)子序列的規(guī)模都不大,用直接插入排序效率都較高，盡管在隨后的增量遞減分組中子序列越來(lái)越大,由于整個(gè)序列的有序性也越來(lái)越明顯,則排序效率依然較高。

從理論上說(shuō)，只要一個(gè)數(shù)組是遞減的，并且最后一個(gè)值是1，都可以作為增量序列使用。有沒(méi)有一個(gè)步長(zhǎng)序列,使得排序過(guò)程中所需的比較和移動(dòng)次數(shù)相對(duì)較少,并且無(wú)論待排序列記錄數(shù)有多少,算法的時(shí)間復(fù)雜度都能漸近最佳呢？但是目前從數(shù)學(xué)上來(lái)說(shuō)，無(wú)法證明某個(gè)序列是“最好的”。

*常用的增量序列有：*

希爾增量序列 ：{N/2, (N / 2)/2, ..., 1}，其中N為原始數(shù)組的長(zhǎng)度，這是最常用的序列，但卻不是最好的

Hibbard序列：{2^k-1, ..., 3,1}

Sedgewick序列：{... , 109 , 41 , 19 , 5，1} 表達(dá)式為

5.歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。

若將兩個(gè)有序表合并成一個(gè)有序表，稱(chēng)為2-路歸并，與之對(duì)應(yīng)的還有多路歸并。

對(duì)于給定的一組數(shù)據(jù)，利用遞歸與分治技術(shù)將數(shù)據(jù)序列劃分成為越來(lái)越小的半子表，在對(duì)半子表排序后，再用遞歸方法將排好序的半子表合并成為越來(lái)越大的有序序列。

為了提升性能，有時(shí)我們?cè)诎胱颖淼膫€(gè)數(shù)小于某個(gè)數(shù)（比如15）的情況下，對(duì)半子表的排序采用其他排序算法，比如插入排序。

歸并排序（降序）示例

6.快速排序

快速排序被譽(yù)為20 世紀(jì)科學(xué)和工程領(lǐng)域的十大算法之一?？焖倥判颍≦uicksort）是對(duì)冒泡排序的一種改進(jìn)，也是采用分治法的一個(gè)典型的應(yīng)用。

首先任意選取一個(gè)數(shù)據(jù)（比如數(shù)組的第一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)，我們稱(chēng)為基準(zhǔn)數(shù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱(chēng)為一趟快速排序，也稱(chēng)為分區(qū)（partition）操作。在實(shí)際實(shí)現(xiàn)時(shí)，一般會(huì)在原數(shù)組上直接操作。

通過(guò)一趟快速排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

為了提升性能，有時(shí)我們?cè)诜指詈螵?dú)立的兩部分的個(gè)數(shù)小于某個(gè)數(shù)（比如15）的情況下，會(huì)采用其他排序算法，比如插入排序。

快速排序原理

11、所有比基準(zhǔn)數(shù)48小的數(shù)都已到它左邊，所有比基準(zhǔn)數(shù)48大的數(shù)都已到它右邊。將左邊和右邊再按快速排序繼續(xù)排序下去，就可完成最終的排序。

快速排序中的基準(zhǔn)數(shù)

基準(zhǔn)的選?。鹤顑?yōu)的情況是基準(zhǔn)值剛好取在無(wú)序區(qū)的中間，這樣能夠最大效率地讓兩邊排序，同時(shí)最大地減少遞歸劃分的次數(shù)，但是一般很難做到最優(yōu)?；鶞?zhǔn)的選取一般有三種方式，選取數(shù)組的第一個(gè)元素，選取數(shù)組的最后一個(gè)元素，以及選取第一個(gè)、最后一個(gè)以及中間的元素的中位數(shù)（如4 5 6 7, 第一個(gè)4, 最后一個(gè)7, 中間的為5, 這三個(gè)數(shù)的中位數(shù)為５, 所以選擇5作為基準(zhǔn)）。

Dual-Pivot快排：兩個(gè)基準(zhǔn)數(shù)的快速排序算法，其實(shí)就是用兩個(gè)基準(zhǔn)數(shù), 把整個(gè)數(shù)組分成三份來(lái)進(jìn)行快速排序，在這種新的算法下面，比經(jīng)典快排從實(shí)驗(yàn)來(lái)看節(jié)省了10%的時(shí)間。