隨著人口城鎮(zhèn)化的進(jìn)程，城市人口的慢慢增加符相，對(duì)于一些生活在一二線城市的同學(xué)來說拆融，排隊(duì)已然成為生活中的基操：上公交排隊(duì)、打車排隊(duì)啊终、坐地鐵排隊(duì)镜豹、點(diǎn)餐排隊(duì)、喝奶茶排隊(duì)蓝牲、辦證排隊(duì)趟脂、下課ATM取錢排隊(duì)……說到排隊(duì)，豬哥想起有次去銀行辦事的我……
排隊(duì)我們可以理解為是根據(jù)時(shí)間（先來后到的）做的一種排序例衍，使元素從無序到有序的方法昔期，我們稱為：排序算法。
程序世界往往和現(xiàn)實(shí)世界有很多相似之處佛玄，所以排序的問題在工作中也常常會(huì)遇到硼一，比如商品根據(jù)不同條件排序、搜索相關(guān)性排序梦抢、以及一些根據(jù)時(shí)間或以某種規(guī)則的排序等等般贼；而且在面試和算法比賽中排序也是必不可少的一個(gè)考點(diǎn)，比如手寫一個(gè)快排惑申、如何處理億級(jí)數(shù)據(jù)排序以及時(shí)間復(fù)雜和空間復(fù)雜度等問題具伍；
排序算法對(duì)程序員來說可以說是一項(xiàng)基本功，其重要性是不言而喻的圈驼。本期豬哥帶大家來了解下常見的十大排序算法，而本文會(huì)作為開胃菜為大家簡(jiǎn)單介紹一些排序算法的相關(guān)概念望几，下次會(huì)為大家詳細(xì)講解每種排序的代碼實(shí)現(xiàn)及圖解绩脆！
一、排序定義
既然排序如此重要那何為排序呢橄抹？看看百科對(duì)排序的定義：
排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作靴迫，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列÷ナ模——百度百科
豬哥的理解是：簡(jiǎn)單來說就是將一組無序的數(shù)據(jù)通過某種算法然后使它們按某種規(guī)則有序的排列玉锌，這就是排序的定義。
二疟羹、相關(guān)概念
排序(Sorting) 是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作主守，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列禀倔，重新排列成一個(gè)關(guān)鍵字有序的序列。
排序算法是一種算法参淫，而算法是與語言無關(guān)的救湖，你可以用Python實(shí)現(xiàn)，也可以用Java涎才、C鞋既、Js等任何語言實(shí)現(xiàn)。
1.比較排序和非比較排序
我們將排序的時(shí)候元素之間是否需要比較分為：比較排序和非比較排序耍铜，下面簡(jiǎn)單理解一下這兩個(gè)概念：
a）比較排序：
顧名思義就是需要通過元素之間比較之后再?zèng)Q定先后順序邑闺。如下冒泡排序的動(dòng)圖，每次都是選取兩個(gè)元素(綠色)進(jìn)行比較：
現(xiàn)實(shí)生活中這種比較排序的例子很多棕兼，比如中學(xué)按成績(jī)排名或高矮順序來安排座位检吆；
b）非比較排序：
非比較排序就是不需要通過元素之間的比較就可以確定每個(gè)元素的位置，如下是基數(shù)排序的動(dòng)圖程储，排序時(shí)每個(gè)元素并不需要比較蹭沛，而是有自己固定的位置：
現(xiàn)實(shí)生活中非比較排序的例子如大學(xué)坐位置；
[圖片上傳失敗...(image-79198c-1552874176257)]
[圖片上傳失敗...(image-128ae-1552874176257)]
2.穩(wěn)定和不穩(wěn)定
我們排隊(duì)的時(shí)候章鲤，當(dāng)出現(xiàn)兩個(gè)人同時(shí)搶占一個(gè)位置的情況摊灭，不免會(huì)發(fā)生一些口角；而在排序算法中也會(huì)遇到兩元素相同的情況败徊，這時(shí)候怎么辦呢帚呼？
假設(shè)我們有這樣一組數(shù)據(jù)[7，5皱蹦，2煤杀，5]，然后我們來看看穩(wěn)定排序算法和不穩(wěn)定排序算法得出的結(jié)果：
a）穩(wěn)定：
如果a原本在b前面沪哺，而a=b沈自，排序之后a仍然在b的前面。
b）不穩(wěn)定：
如果a原本在b的前面辜妓，而a=b枯途，排序之后 a 可能會(huì)出現(xiàn)在 b 的后面。
[圖片上傳失敗...(image-e0c649-1552874176257)]
3.算法復(fù)雜度
算法復(fù)雜度分為時(shí)間復(fù)雜度和空間復(fù)雜度籍滴。其作用： 時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量酪夷；而空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。（算法的復(fù)雜性體現(xiàn)在運(yùn)行該算法時(shí)的計(jì)算機(jī)所需資源的多少上孽惰，計(jì)算機(jī)資源最重要的是時(shí)間和空間（即寄存器）資源晚岭，因此復(fù)雜度分為時(shí)間和空間復(fù)雜度）。
a）時(shí)間復(fù)雜度：
時(shí)間復(fù)雜度(Time Complexity)是描述運(yùn)行算法所花費(fèi)的時(shí)間量的計(jì)算復(fù)雜度勋功，記做O(f(n))坦报。
n稱為問題的規(guī)模库说，當(dāng)n不斷變化時(shí),時(shí)間頻度T(n)也會(huì)不斷變化。但是它的變化是有規(guī)律的燎竖，所以引入時(shí)間復(fù)雜度這個(gè)概念璃弄。一般情況下，算法中的基本操作重復(fù)次數(shù)的是問題規(guī)模n的某個(gè)函數(shù)构回，用T(n)表示夏块，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時(shí)，T（n)/f(n)的極限值為不等于零的常數(shù)纤掸，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)脐供。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度借跪。
b）空間復(fù)雜度：
空間復(fù)雜度(Space Complexity)是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度政己，記做S(n)=O(f(n))。
[圖片上傳失敗...(image-a177b6-1552874176257)]
c）復(fù)雜度
上面給大家講了時(shí)間復(fù)雜度和空間復(fù)雜度掏愁，下面看看常見的幾種復(fù)雜度：
[圖片上傳失敗...(image-9004ad-1552874176257)][圖片上傳失敗...(image-78e446-1552874176257)]
三歇由、總結(jié)
本文為大家介紹了排序算法的三個(gè)相關(guān)知識(shí)點(diǎn)：
- 比較排序和非比較排序
- 穩(wěn)定和不穩(wěn)定
-
算法復(fù)雜度
比較與穩(wěn)定
排序算法一覽表.png
參考：
