排序策略演算法

① 面試必會八大排序演算法（Python）

一、插入排序

介紹

插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據。

演算法適用於少量數據的排序，時間復雜度為O(n^2)。

插入排演算法是穩定的排序方法。

步驟

①從第一個元素開始，該元素可以認為已經被排序

②取出下一個元素，在已經排序的元素序列中從後向前掃描

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

④重復步驟3，直到找到已排序的元素小於或者等於新元素的位置

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

⑥重復步驟2

排序演示

演算法實現

二、冒泡排序

介紹

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

它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。

這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。

原理

循環遍歷列表，每次循環找出循環最大的元素排在後面；

需要使用嵌套循環實現：外層循環控制總循環次數，內層循環負責每輪的循環比較。

步驟

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

②對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。

③針對所有的元素重復以上的步驟，除了最後一個。

④持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

演算法實現：

三、快速排序

介紹

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

基本思想

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

首先選出一個軸值(pivot，也有叫基準的)，通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

實現步驟

①從數列中挑出一個元素，稱為 「基準」（pivot）；

②重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）；

③對所有兩個小數列重復第二步，直至各區間只有一個數。

排序演示

演算法實現

四、希爾排序

介紹

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

希爾排序是基於插入排序的以下兩點性質而提出改進方法的：

·插入排序在對幾乎已經排好序的數據操作時， 效率高， 即可以達到線性排序的效率；

·但插入排序一般來說是低效的， 因為插入排序每次只能將數據移動一位。

基本思想

①希爾排序是把記錄按下標的一定量分組，對每組使用直接插入演算法排序；

②隨著增量逐漸減少，每組包1含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法被終止。

排序演示

演算法實現

五、選擇排序

介紹

選擇排序(Selection sort)是一種簡單直觀的排序演算法，時間復雜度為Ο(n2)。

基本思想

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

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

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

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

排序演示

選擇排序的示例動畫。紅色表示當前最小值，黃色表示已排序序列，藍色表示當前位置。

演算法實現

六、堆排序

介紹

堆排序（Heapsort）是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法，它是選擇排序的一種。

利用數組的特點快速指定索引的元素。

基本思想

堆分為大根堆和小根堆，是完全二叉樹。

大根堆的要求是每個節點的值不大於其父節點的值，即A[PARENT[i]] >=A[i]。

在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。

排序演示

演算法實現

七、歸並排序

介紹

歸並排序（Merge sort）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

基本思想

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

演算法思想

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

① 將序列每相鄰兩個數字進行歸並操作，形成 floor(n/2)個序列，排序後每個序列包含兩個元素；

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

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

自下而上迭代法

① 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列；

② 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；

③ 比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置；

④ 重復步驟③直到某一指針達到序列尾；

⑤ 將另一序列剩下的所有元素直接復制到合並序列尾。

排序演示

演算法實現

八、基數排序

介紹

基數排序（Radix Sort）屬於「分配式排序」，又稱為「桶子法」。

基數排序法是屬於穩定性的排序，其時間復雜度為O (nlog(r)m) ，其中 r 為採取的基數，而m為堆數。

在某些時候，基數排序法的效率高於其他的穩定性排序法。

基本思想

將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後，數列就變成一個有序序列。

基數排序按照優先從高位或低位來排序有兩種實現方案：

MSD（Most significant digital） 從最左側高位開始進行排序。先按k1排序分組, 同一組中記錄, 關鍵碼k1相等,再對各組按k2排序分成子組, 之後, 對後面的關鍵碼繼續這樣的排序分組, 直到按最次位關鍵碼kd對各子組排序後. 再將各組連接起來,便得到一個有序序列。MSD方式適用於位數多的序列。

LSD （Least significant digital）從最右側低位開始進行排序。先從kd開始排序，再對kd-1進行排序，依次重復，直到對k1排序後便得到一個有序序列。LSD方式適用於位數少的序列。

排序效果

演算法實現

九、總結

各種排序的穩定性、時間復雜度、空間復雜度的總結：

平方階O(n²)排序：各類簡單排序：直接插入、直接選擇和冒泡排序；

從時間復雜度來說：

線性對數階O(nlog₂n)排序：快速排序、堆排序和歸並排序；

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

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

② 常見的幾種排序演算法總結

對於非科班生的我來說，演算法似乎對我來說是個難點，查閱了一些資料，趁此來了解一下幾種排序演算法。
首先了解一下，什麼是程序

關於排序演算法通常我們所說的往往指的是內部排序演算法，即數據記錄在內存中進行排序。
排序演算法大體可分為兩種：
一種是比較排序，時間復雜度O(nlogn) ~ O(n^2)，主要有：冒泡排序，選擇排序，插入排序，歸並排序，堆排序，快速排序等。
另一種是非比較排序，時間復雜度可以達到O(n)，主要有：計數排序，基數排序，桶排序等

冒泡排序它重復地走訪過要排序的元素，一次比較相鄰兩個元素，如果他們的順序錯誤就把他們調換過來，直到沒有元素再需要交換，排序完成。這個演算法的名字由來是因為越小(或越大)的元素會經由交換慢慢「浮」到數列的頂端。

選擇排序類似於冒泡排序，只不過選擇排序是首先在未排序的序列中找到最小值（最大值），放到序列的起始位置，然後再從剩餘未排序元素中繼續尋找最小（大）元素，放到已排序序列的末尾，以此類推，直到所有元素均排序完畢。

插入排序比冒泡排序和選擇排序更有效率，插入排序類似於生活中抓撲克牌來。
插入排序具體演算法描述，以數組[3, 2, 4, 5, 1]為例。

前面三種排序演算法只有教學價值，因為效率低，很少實際使用。歸並排序（Merge sort）則是一種被廣泛使用的排序方法。
它的基本思想是，將兩個已經排序的數組合並，要比從頭開始排序所有元素來得快。因此，可以將數組拆開，分成n個只有一個元素的數組，然後不斷地兩兩合並，直到全部排序完成。
以對數組[3, 2, 4, 5, 1] 進行從小到大排序為例，步驟如下：

有了merge函數，就可以對任意數組排序了。基本方法是將數組不斷地拆成兩半，直到每一半隻包含零個元素或一個元素為止，然後就用merge函數，將拆成兩半的數組不斷合並，直到合並成一整個排序完成的數組。

快速排序（quick sort）是公認最快的排序演算法之一，有著廣泛的應用。
快速排序演算法步驟

參考：
常用排序演算法總結(一)
阮一峰-演算法總結

③ 常用的排序演算法都有哪些

排序演算法 所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
分類
在計算機科學所使用的排序演算法通常被分類為：
計算的復雜度（最差、平均、和最好表現），依據串列（list）的大小（n）。一般而言，好的表現是O。(n log n)，且壞的行為是Ω(n2)。對於一個排序理想的表現是O(n)。僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要Ω(n log n)。
記憶體使用量（以及其他電腦資源的使用）
穩定度：穩定排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。也就是一個排序演算法是穩定的，就是當有兩個有相等關鍵的紀錄R和S，且在原本的串列中R出現在S之前，在排序過的串列中R也將會是在S之前。
一般的方法：插入、交換、選擇、合並等等。交換排序包含冒泡排序（bubble sort）和快速排序（quicksort）。選擇排序包含shaker排序和堆排序（heapsort）。
當相等的元素是無法分辨的，比如像是整數，穩定度並不是一個問題。然而，假設以下的數對將要以他們的第一個數字來排序。
(4, 1) (3, 1) (3, 7) (5, 6)
在這個狀況下，有可能產生兩種不同的結果，一個是依照相等的鍵值維持相對的次序，而另外一個則沒有：
(3, 1) (3, 7) (4, 1) (5, 6) (維持次序)
(3, 7) (3, 1) (4, 1) (5, 6) (次序被改變)
不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地時作為穩定。作這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個物件間之比較，就會被決定使用在原先資料次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。
排列演算法列表
在這個表格中，n是要被排序的紀錄數量以及k是不同鍵值的數量。
穩定的
冒泡排序（bubble sort） — O(n2)
雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 額外 記憶體
計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外 記憶體
歸並排序 （merge sort）— O(n log n); 需要 O(n) 額外記憶體
原地歸並排序 — O(n2)
二叉樹排序 （Binary tree sort） — O(n log n); 需要 O(n) 額外記憶體
鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外記憶體
基數排序 （radix sort）— O(n·k); 需要 O(n) 額外記憶體
Gnome sort — O(n2)
Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外記憶體
不穩定
選擇排序 （selection sort）— O(n2)
希爾排序 （shell sort）— O(n log n) 如果使用最佳的現在版本
Comb sort — O(n log n)
堆排序 （heapsort）— O(n log n)
Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n) 期望時間, O(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情況時間, 需要 額外的 O(n + k) 空間, 也需要找到最長的遞增子序列（longest increasing subsequence）
不實用的排序演算法
Bogo排序 — O(n × n!) 期望時間, 無窮的最壞情況。
Stupid sort — O(n3); 遞回版本需要 O(n2) 額外記憶體
Bead sort — O(n) or O(√n), 但需要特別的硬體
Pancake sorting — O(n), 但需要特別的硬體
排序的演算法
排序的演算法有很多，對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序演算法。這裡面插入排序和冒泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對於簡單排序對空間的要求稍高一點，但時間效率卻能穩定在很高的水平。基數排序是針對關鍵字在一個較小范圍內的排序演算法。
插入排序
冒泡排序
選擇排序
快速排序
堆排序
歸並排序
基數排序
希爾排序
插入排序
插入排序是這樣實現的：
首先新建一個空列表，用於保存已排序的有序數列（我們稱之為"有序列表"）。
從原數列中取出一個數，將其插入"有序列表"中，使其仍舊保持有序狀態。
重復2號步驟，直至原數列為空。
插入排序的平均時間復雜度為平方級的，效率不高，但是容易實現。它藉助了"逐步擴大成果"的思想，使有序列表的長度逐漸增加，直至其長度等於原列表的長度。
冒泡排序
冒泡排序是這樣實現的：
首先將所有待排序的數字放入工作列表中。
從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。
重復2號步驟，直至再也不能交換。
冒泡排序的平均時間復雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序
選擇排序是這樣實現的：
設數組內存放了n個待排數字，數組下標從1開始，到n結束。
i=1
從數組的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。
如果i=n－1演算法結束，否則回到第3步
選擇排序的平均時間復雜度也是O(n²)的。
快速排序
現在開始，我們要接觸高效排序演算法了。實踐證明，快速排序是所有排序演算法中最高效的一種。它採用了分治的思想：先保證列表的前半部分都小於後半部分，然後分別對前半部分和後半部分排序，這樣整個列表就有序了。這是一種先進的思想，也是它高效的原因。因為在排序演算法中，演算法的高效與否與列表中數字間的比較次數有直接的關系，而"保證列表的前半部分都小於後半部分"就使得前半部分的任何一個數從此以後都不再跟後半部分的數進行比較了，大大減少了數字間不必要的比較。但查找數據得另當別論了。
堆排序
堆排序與前面的演算法都不同，它是這樣的：
首先新建一個空列表，作用與插入排序中的"有序列表"相同。
找到數列中最大的數字，將其加在"有序列表"的末尾，並將其從原數列中刪除。
重復2號步驟，直至原數列為空。
堆排序的平均時間復雜度為nlogn,效率高（因為有堆這種數據結構以及它奇妙的特徵，使得"找到數列中最大的數字"這樣的操作只需要O(1)的時間復雜度，維護需要logn的時間復雜度），但是實現相對復雜（可以說是這里7種演算法中比較難實現的）。
看起來似乎堆排序與插入排序有些相像，但他們其實是本質不同的演算法。至少，他們的時間復雜度差了一個數量級，一個是平方級的，一個是對數級的。
平均時間復雜度
插入排序 O(n2)
冒泡排序 O(n2)
選擇排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
歸並排序 O(n log n)
基數排序 O(n)
希爾排序 O(n1.25)
冒泡排序
654
比如說這個，我想讓它從小到大排序，怎麼做呢？
第一步：6跟5比，發現比它大，則交換。564
第二步：5跟4比，發現比它大，則交換。465
第三步：6跟5比，發現比它大，則交換。456

④ 排序演算法有多少種

排序(Sorting) 是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列。
排序就是把集合中的元素按照一定的次序排序在一起。一般來說有升序排列和降序排列2種排序，在演算法中有8中基本排序：
(1)冒泡排序；
(2)選擇排序；
(3)插入排序；
(4)希爾排序；
(5)歸並排序；
(6)快速排序；
(7)基數排序；
(8)堆排序；
(9)計數排序；
(10)桶排序。
插入排序
插入排序演算法是基於某序列已經有序排列的情況下，通過一次插入一個元素的方式按照原有排序方式增加元素。這種比較是從該有序序列的最末端開始執行，即要插入序列中的元素最先和有序序列中最大的元素比較，若其大於該最大元素，則可直接插入最大元素的後面即可，否則再向前一位比較查找直至找到應該插入的位置為止。插入排序的基本思想是，每次將1個待排序的記錄按其關鍵字大小插入到前面已經排好序的子序列中，尋找最適當的位置，直至全部記錄插入完畢。執行過程中，若遇到和插入元素相等的位置，則將要插人的元素放在該相等元素的後面，因此插入該元素後並未改變原序列的前後順序。我們認為插入排序也是一種穩定的排序方法。插入排序分直接插入排序、折半插入排序和希爾排序3類。
冒泡排序
冒泡排序演算法是把較小的元素往前調或者把較大的元素往後調。這種方法主要是通過對相鄰兩個元素進行大小的比較，根據比較結果和演算法規則對該二元素的位置進行交換，這樣逐個依次進行比較和交換，就能達到排序目的。冒泡排序的基本思想是，首先將第1個和第2個記錄的關鍵字比較大小，如果是逆序的，就將這兩個記錄進行交換，再對第2個和第3個記錄的關鍵字進行比較，依次類推，重復進行上述計算，直至完成第(n一1)個和第n個記錄的關鍵字之間的比較，此後，再按照上述過程進行第2次、第3次排序，直至整個序列有序為止。排序過程中要特別注意的是，當相鄰兩個元素大小一致時，這一步操作就不需要交換位置，因此也說明冒泡排序是一種嚴格的穩定排序演算法，它不改變序列中相同元素之間的相對位置關系。
選擇排序
選擇排序演算法的基本思路是為每一個位置選擇當前最小的元素。選擇排序的基本思想是，基於直接選擇排序和堆排序這兩種基本的簡單排序方法。首先從第1個位置開始對全部元素進行選擇，選出全部元素中最小的給該位置，再對第2個位置進行選擇，在剩餘元素中選擇最小的給該位置即可；以此類推，重復進行「最小元素」的選擇，直至完成第(n-1)個位置的元素選擇，則第n個位置就只剩唯一的最大元素，此時不需再進行選擇。使用這種排序時，要注意其中一個不同於冒泡法的細節。舉例說明：序列58539．我們知道第一遍選擇第1個元素「5」會和元素「3」交換，那麼原序列中的兩個相同元素「5」之間的前後相對順序就發生了改變。因此，我們說選擇排序不是穩定的排序演算法，它在計算過程中會破壞穩定性。
快速排序
快速排序的基本思想是:通過一趟排序演算法把所需要排序的序列的元素分割成兩大塊，其中，一部分的元素都要小於或等於另外一部分的序列元素，然後仍根據該種方法對劃分後的這兩塊序列的元素分別再次實行快速排序演算法，排序實現的整個過程可以是遞歸的來進行調用，最終能夠實現將所需排序的無序序列元素變為一個有序的序列。
歸並排序
歸並排序演算法就是把序列遞歸劃分成為一個個短序列，以其中只有1個元素的直接序列或者只有2個元素的序列作為短序列的遞歸出口，再將全部有序的短序列按照一定的規則進行排序為長序列。歸並排序融合了分治策略，即將含有n個記錄的初始序列中的每個記錄均視為長度為1的子序列，再將這n個子序列兩兩合並得到n/2個長度為2(當凡為奇數時會出現長度為l的情況)的有序子序列；將上述步驟重復操作，直至得到1個長度為n的有序長序列。需要注意的是，在進行元素比較和交換時，若兩個元素大小相等則不必刻意交換位置，因此該演算法不會破壞序列的穩定性，即歸並排序也是穩定的排序演算法。

⑤ 8種排序演算法速記

排序演算法的穩定性是指兩個相等的元素在排序前後其相對位置是不變的。而與時間復雜度沒有直接關系，所以要注意區分相關的概念。
穩定:冒(冒泡排序)直(直接插入排序)歸(歸並排序)基(基數排序，不常用)
不穩定:選(選擇排序)希(希爾排序)快(快速排序)堆(堆排序)

冒n2直n2
歸nlog2n
選n2快nlog2n
堆nlog2n

歸並，選擇排序，堆排序，由於平均最差相同，所以初始順序不影響其排序復雜度選擇

直接插入，歸並，快排，堆有關
冒泡，選擇無關

冒泡n最好 直接插入n最好
快排n2最差

只有快排的空間復雜度，和堆排序的空間復雜度比較多堆排序需要額外的輔助空間n
快排的空間復雜度，如果就地快排1
使用遞歸平均是logn，最差情況，退化成冒泡是n

上圖有錯:快排的空間復雜度，如果就地快排1
使用遞歸平均是logn，最差情況，退化成冒泡是n

⑥ 排序演算法有哪些

1.插入排序—直接插入排序(Straight Insertion Sort)
2. 插入排序—希爾排序（Shell`s Sort）
3. 選擇排序—簡單選擇排序（Simple Selection Sort）
4. 選擇排序—堆排序（Heap Sort）
5. 交換排序—冒泡排序（Bubble Sort）
6. 交換排序—快速排序（Quick Sort）
7. 歸並排序（Merge Sort）
8. 桶排序/基數排序(Radix Sort)

⑦ 常見排序演算法介紹

原理：比較相鄰兩個數，如果前面的數大於（小於）後面的數，則二者交換位置，直到盡頭，重復（N-1）次，得到一個有序數列
演算法復雜度：O(n^2)
排序過程：

原理：將一個數插入到一個有序數列，得到一個新的有序數列
演算法復雜度：O(n^2)
排序過程：

原理：從無序數組中選出一個最大值（最小值），放進有序數組
演算法復雜度：O(n^2)
排序過程：

原理：找關鍵值，然後將數列分成兩個數列，一個大於等於關鍵值的，一個小於等於關鍵值的，然後再對這兩個數列進行遞歸
演算法復雜度：O(nlogn)
演算法步驟：

排序過程：

原理：採用的是分治策略，將大問題分解成小問題，遞歸求解
演算法復雜度：O(nlogn)
演算法步驟：

排序過程：

將排序過程簡化：

原理：和選擇排序類似，只是將選擇大小這一步用堆來實現
堆的性質

原理：是插入排序的一種優化，先將整個序列分割成若乾子序列分別進行直接插入排序，待整個序列中數基本有序後，再進行一次插入排序

希爾排序的復雜度很大程度上由選擇的增量序列決定，現今沒有最優的增量序列

原理：不是通過數據比較來進行排序，經過統計數據出現次數，然後根據統計個數排出序列
演算法復雜度：O(n+k)
演算法步驟：

空間優化：選出最大值和最小值，將統計數組大小開為 max-min+1（這種優化和數據關系很大）

如何保證相同數據按照本來數據排列

計數排序主要被數據最大值和最小值的差值給限制住了，當差值較大時，就意味著申請更多的空間，造成大量的浪費，
但在統計數值在一個固定范圍的數據，比如身高，分數，體重之類的，效率還是比較高的。

原理：從低位到高位過比較每個數據數位的值進行的排序，利用了計數排序
演算法復雜度：O(n*m)

⑧ 基本排序演算法原理

演算法原理：每次對相鄰的兩個元素進行比較，若前者大於後者則進行交換，如此一趟下來最後一趟的就是最大元素，重復以上的步驟，除了已經確定的元素 。

演算法原理：每次對相鄰的兩個元素進行比較，若前者大於後者則進行交換，如此一趟下來最後一趟的就是最大元素，重復以上的步驟，除了已經確定的元素

演算法步驟

1)  設置兩個變數i、j，排序開始的時候：i=0，j=n-1；

2）第一個數組值作為比較值，首先保存到temp中，即temp=A[0]；

3）然後j-- ,向前搜索,找到小於temp後,因為s[i]的值保存在temp中,所以直接賦值,s[i]=s[j]

4）然後i++,向後搜索,找到大於temp後,因為s[j]的值保存在第2步的s[i]中,所以直接賦值,s[j]=s[i],然後j--,避免死循環

5）重復第3、4步，直到i=j,最後將temp值返回s[i]中

6)  然後採用「二分」的思想,以i為分界線,拆分成兩個數組 s[0,i-1]、s[i+1,n-1]又開始排序

排序圖解

演算法原理：從第一個元素開始，左邊視為已排序數組，右邊視為待排序數組，從左往右依次取元素，插入左側已排序數組，對插入新元素的左側數組重新生成有序數組 。需要注意的是，在往有序數組插入一個新元素的過程中，我們可以採用按 順序循環 比較，也可以通過 折半查找法 來找到新元素的位置，兩種方式的效率 取決於數組的數據量

演算法原理：希爾排序也是利用插入排序的思想來排序。希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然後演算法再取越來越小的步長進行排序，演算法的最後一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了，插入效率比較高。

排序圖解

選擇排序(Selection sort)是一種簡單直觀的排序演算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。選擇排序的主要優點與數據移動有關。如果某個元素位於正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬於非常好的一種。

歸並排序，顧名思義就是一種 「遞歸合並」 的排序方法（這個理解很重要）。對於一個數列，我們把它進行二分處理，依次遞歸下去，然後將小范圍的數進行排序，最後將其合並在一起。就實現了歸並排序。

這實際上是運用了 分治思想 ，顯然，想要把一個數列排好序，最終達到的目的就是它的任何一部分都是有序的。這樣的話，我們可以考慮分別把數列分成N多個部分，讓每個部分分別有序，然後再將其統一，變成所有的東西都有序。這樣就實現了排序。這個想法就叫分治思想。

排序圖解

排序圖解

⑨ 幾種常見的排序演算法分析學習

排序演算法一般分為以下幾種： （1）非線性時間比較類排序：交換類排序（快速排序和冒泡排序）、插入類排序（簡單插入排序和希爾排序）、選擇類排序（簡單選擇排序和堆排序）、歸並排序（二路歸並排序和多路歸並排序）；（2）線性時間非比較類排序：計數排序、基數排序和桶排序。