排序重要性

在計算機編程的過程中柏锄，需要學習很多的算法酿箭，了解算法的設計與原理可以幫助我們提高自身的編程素養(yǎng)。學習算法最基本最常見的就是排序算法了趾娃。排序也為算法的學習與入門提供了一個很好的例子缭嫡。
排序的目的就是為了方便查找，但是為了提高計算機的運行時間和內(nèi)存占用抬闷，前人們提出并不斷改進各種各樣的排序算法妇蛀，這些算法也從不同角度展示了算法設計的重要原則和技巧。

排序算法根據(jù)不同的劃分依據(jù)有不同的劃分標準：

根據(jù)算法穩(wěn)定性可以分為穩(wěn)定（冒泡排序笤成、插入排序评架、歸并排序、基數(shù)排序）和不穩(wěn)定（選擇排序炕泳、快速排序纵诞、希爾排序、堆排序）培遵。
排序算法的穩(wěn)定性通俗地講就是能保證排序前2個相等的數(shù)其在序列的前后位置順序和排序后它們兩個的前后位置順序相同浙芙。在簡單形式化一下，如果Ai = Aj, Ai原來在位置前籽腕，排序后Ai還是要在Aj位置前嗡呼。

也可以劃分內(nèi)部排序和外部排序兩類，如下圖所示：

排序算法分類

廢話不多說皇耗，接下來依次講一下八大排序算法：

選擇排序--簡單（直接）選擇排序

時間復雜度：O(n^2)
空間復雜度：O(1)
穩(wěn)定度：非穩(wěn)定
1.從第一個位置8依次往后比較大小南窗，第一次遍歷的過程中找到最小元素0，然后將0與8交換位置；
2.從第二個位置5依次往后比較大小矾瘾，第二次遍歷的過程中找到最小元素1女轿，然后將1與5交換位置；
3.....
重復直到最后一次遍歷完成壕翩，排序過程也就完成了蛉迹。

簡單選擇排序動畫展示

選擇排序--堆排序

時間復雜度：O(nlogn)
空間復雜度：O(1)
穩(wěn)定度：非穩(wěn)定
堆排序是利用利用樹這種數(shù)據(jù)結(jié)構(gòu)所設計的一種排序算法。堆可分為兩種：大頂堆和小頂堆放妈。
大頂堆要求每個節(jié)點的值不大于其父節(jié)點（小頂堆要求每個節(jié)點的值不小于其父節(jié)點）北救。堆排序正是利用這個特性，不斷地將堆頂元素取出進行排序芜抒。這個用語言比較難講清楚珍策，大家還是看下邊的動畫理解吧：

堆排序

插入排序--直接插入排序

時間復雜度：O(n^2)
空間復雜度：O(1)
穩(wěn)定度：穩(wěn)定
1.從n個元素的首元素開始，先比較前兩個元素的大小宅倒，將較小值置于左端攘宙；
2.再將第三個元素在前兩個已經(jīng)排序好的元素之間找到其位置；
3.再將第四個元素在前三個已經(jīng)排序好的元素之間找到其位置拐迁；
4.再將第五個元素在前四個已經(jīng)排序好的元素之間找到其位置蹭劈；
....
直到最后一個元素在前n-1個已經(jīng)排序好的元素之間找到其位置，排序完成线召。
動畫如下圖所示：

直接插入排序

插入排序--希爾排序

時間復雜度：O(nlogn)
空間復雜度：O(1)
穩(wěn)定度：非穩(wěn)定
希爾排序首先將n個元素以n/2為步長劃分元素為一組铺韧，對每個小組內(nèi)的元素進行直接插入排序，然后每個小組均為有序數(shù)組缓淹，再將n個元素以n/4為步長劃分....依次循環(huán)哈打。具體步驟如下圖所示：
我們簡單處理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n為要排序數(shù)的個數(shù)

希爾排序

交換排序--冒泡排序

平均時間復雜度：O(n^2)
空間復雜度：O(1)
穩(wěn)定度：穩(wěn)定
冒泡排序可以這樣理解：將一個長度為2的滑動窗從元素的最左向右依次滑動，每次保證窗口內(nèi)部的元素最大值在窗口的右邊讯壶，如果最大值不在右邊的話料仗，則交換窗口內(nèi)部的兩個元素位置∨羲荩滑動窗口第一次滑動完成后罢维，將元素的最大值置于最右端。依次循環(huán)完成排序丙挽。

冒泡排序

交換排序--快速排序

平均時間復雜度：O(nlogn)
空間復雜度：O(logn)~O(n)
穩(wěn)定度：非穩(wěn)定
快速排序?qū)嵸|(zhì)是對冒泡排序的改進肺孵。快速排序的過程可以與雙指針結(jié)合理解：在所有的記錄中取某一個記錄的值為標準（通常取第一個記錄鍵值為基準）颜阐，通過一趟排序?qū)⑺械脑胤譃閮蓚€部分：標準元素的左邊均為小于或等于當前標準的元素平窘，標準元素的右邊均為大于當前標準的元素。如下圖所示為第一個標準元素6從開始到完成一次快速排序的過程（在首尾共建立兩個指針指向當前的元素凳怨，其中一個指針指向標準元素6的位置瑰艘，對于左指針來說是鬼，如果指針指向的元素大于標準值，則交換兩個元素的位置紫新，右指針相反）：

快速排序

歸并排序

平均時間復雜度：O(nlogn)
空間復雜度：O(n)
穩(wěn)定度：穩(wěn)定
歸并排序其實就是將n個元素先劃分為n個長度為1的組均蜜，然后進行兩兩歸并，第一次歸并結(jié)束的結(jié)果是有n/2個排序好的組芒率。再依次進行兩兩組的歸并囤耳，如此重復，直至最后形成包含n個記錄的有序文件位置偶芍。

歸并排序

基數(shù)排序

平均時間復雜度：O(d(r+n))
r代表關鍵字基數(shù)(一組數(shù)組中有幾個不同的數(shù)字)充择，d代表序列中最大值的位數(shù)，n代表序列的長度
空間復雜度：O(dr+n)
穩(wěn)定度：穩(wěn)定
基數(shù)排序是按照低位先排序匪蟀，然后收集匣屡；再按照高位排序波岛，然后再收集笋敞；依次類推觉痛，直到最高位。大家直接看圖理解：

基數(shù)排序

綜上言簡意賅的介紹了每種排序方法以及其排序的過程查刻。希望可以幫助各位看官加深理解與學習键兜。

注：本文的一些動圖來自于其他網(wǎng)站凤类，也誠摯的感謝他們穗泵。
https://blog.csdn.net/donglynn/article/details/49758003
https://www.cnblogs.com/zhi-ming/p/10453124.html