排序算法概述

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

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

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

類似的技術(shù)也能有效解決其他類型的問題十酣；

排序算法常常是我們解決其他問題的第一步。

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

數(shù)據(jù)結(jié)構(gòu)和算法中怔接，關(guān)于排序有十大算法搪泳，包括冒泡排序，簡單選擇排序扼脐，簡單插入排序岸军，歸并排序，堆排序，快速排序凛膏、希爾排序杨名、計數(shù)排序，基數(shù)排序猖毫，桶排序台谍。

一般在面試中最常考的是?快速排序和歸并排序?吁断，并且經(jīng)常有面試官要求現(xiàn)場寫出這兩種排序的代碼趁蕊。對這兩種排序的代碼一定要信手拈來才行。對于其他排序可能會要求比較各自的優(yōu)劣仔役、各種算法的思想及其使用場景掷伙，還有要知道算法的時間和空間復(fù)雜度。

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

1.冒泡排序

冒泡排序是一種簡單的排序算法又兵。它重復(fù)地走訪過要排序的數(shù)列任柜，一次比較兩個元素昧狮，如果它們的順序錯誤就把它們交換過來粥谬。走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成喧兄。這個算法的名字由來是因為相關(guān)的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端逆皮。

基本思路：

1宅粥、比較相鄰的元素。如果第一個比第二個大(小)电谣，就交換它們兩個秽梅；

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

3晒来、針對所有的元素重復(fù)以上的步驟竹观，除了最后一個；

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

*冒泡降序示例：*

原始數(shù)組

2.簡單選擇排序

選擇排序的思想其實和冒泡排序有點類似懂酱，都是在一次排序后把最小的元素放到最前面竹习。但是過程不同，冒泡排序是通過相鄰的比較和交換列牺。而選擇排序是通過對整體的選擇整陌。

舉個例子，對5,3,8,6,4這個無序序列進行簡單選擇排序，首先要選擇5以外的最小數(shù)來和5交換泌辫，也就是選擇3和5交換随夸，一次排序后就變成了3,5,8,6,4.對剩下的序列繼續(xù)進行選擇和交換，最終就會得到一個有序序列震放。其實選擇排序可以看成冒泡排序的優(yōu)化宾毒，因為其目的相同，只是選擇排序只有在確定了最小數(shù)的前提下才進行交換殿遂，大大減少了交換的次數(shù)诈铛。

具體步驟

首先，找到數(shù)組中最大（心浮）的那個元素幢竹；

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

再次，在剩下的元素中找到最大（惺磺）的元素邑飒，將它與數(shù)組的第二個元素交換位置。如此往復(fù)轻掩，直到將整個數(shù)組排序幸乒。

簡單選擇排序（降序）示例

原始數(shù)組：

3.簡單插入排序

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

舉個例子臀蛛，我們將要收到5,3,4,,8,6這幾張牌，我們先收到5這張牌崖蜜，毫無疑問浊仆，這張牌的位置是正確的，沒必要整理豫领。接著收到了牌3抡柿，然后3要插到5前面，把5后移一位等恐，變成3,5洲劣。接著又收到了牌4备蚓，現(xiàn)在我們會怎么做？把4插入到5前面囱稽，把5后移一位郊尝。

*具體步驟：*

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

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

插入排序所需的時間取決于輸入中元素的初始順序横缔。例如，對一個很大且其中的元素已經(jīng)有序（或接近有序）的數(shù)組進行排序?qū)葘﹄S機順序的數(shù)組或是逆序數(shù)組進行排序要快得多衫哥。

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

簡單插入排序（降序）示例

原始數(shù)組：

4.希爾排序

一種基于插入排序的快速的排序算法(請大家先學(xué)習(xí)插入排序膛锭，了解基本的插入排序的思想。對于大規(guī)模亂序數(shù)組插入排序很慢蚊荣，因為元素只能一點一點地從數(shù)組的一端移動到另一端初狰。例如，如果主鍵最小的元素正好在數(shù)組的盡頭互例，要將它挪到正確的位置就需要N-1 次移動奢入。

希爾排序為了加快速度簡單地改進了插入排序，也稱為縮小增量排序媳叨，同時該算法是沖破O(n^2）的第一批算法之一腥光。

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

希爾排序（降序）示例

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

3说铃、

第三個增量為1访惜，則第二次排序后數(shù)組被分為1組，進行插入排序腻扇，形成最后的排序數(shù)組

希爾排序中的增量排序

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

從理論上說幼苛，只要一個數(shù)組是遞減的窒篱，并且最后一個值是1，都可以作為增量序列使用舶沿。有沒有一個步長序列,使得排序過程中所需的比較和移動次數(shù)相對較少,并且無論待排序列記錄數(shù)有多少,算法的時間復(fù)雜度都能漸近最佳呢墙杯？但是目前從數(shù)學(xué)上來說，無法證明某個序列是“最好的”括荡。

*常用的增量序列有：*

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

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

Sedgewick序列：{... , 109 , 41 , 19 , 5嫉髓，1} 表達式為

5.歸并排序

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

若將兩個有序表合并成一個有序表，稱為2-路歸并褪子，與之對應(yīng)的還有多路歸并量淌。

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

為了提升性能渔扎，有時我們在半子表的個數(shù)小于某個數(shù)（比如15）的情況下硫狞，對半子表的排序采用其他排序算法，比如插入排序晃痴。

歸并排序（降序）示例

6.快速排序

快速排序被譽為20 世紀(jì)科學(xué)和工程領(lǐng)域的十大算法之一残吩。快速排序（Quicksort）是對冒泡排序的一種改進倘核，也是采用分治法的一個典型的應(yīng)用泣侮。

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

通過一趟快速排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分铜犬，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小舞终，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行癣猾，以此達到整個數(shù)據(jù)變成有序序列敛劝。

為了提升性能，有時我們在分割后獨立的兩部分的個數(shù)小于某個數(shù)（比如15）的情況下纷宇，會采用其他排序算法夸盟，比如插入排序。

快速排序原理

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

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

基準(zhǔn)的選取：最優(yōu)的情況是基準(zhǔn)值剛好取在無序區(qū)的中間痘儡，這樣能夠最大效率地讓兩邊排序辕万，同時最大地減少遞歸劃分的次數(shù)，但是一般很難做到最優(yōu)沉删〗ツ颍基準(zhǔn)的選取一般有三種方式，選取數(shù)組的第一個元素矾瑰，選取數(shù)組的最后一個元素砖茸，以及選取第一個、最后一個以及中間的元素的中位數(shù)（如4 5 6 7, 第一個4, 最后一個7, 中間的為5, 這三個數(shù)的中位數(shù)為５, 所以選擇5作為基準(zhǔn)）殴穴。

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