實現排序的各種基本演算法

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

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

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

排序演算法 所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
分類
在計算機科學所使用的排序演算法通常被分類為：
計算的復雜度（最差、平均、和最好表現），依據串列（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

C. 八大經典排序演算法原理及實現

該系列文章主要是記錄下自己暑假這段時間的學習筆記，暑期也在實習，抽空學了很多，每個方面的知識我都會另起一篇博客去記錄，每篇頭部主要是另起博客的鏈接。

冒泡排序演算法應該是大家第一個接觸的演算法，其原理都應該懂，但我還是想以自己的語言來敘述下其步奏：

按照計算時間復雜度的規則，去掉常數、去掉最高項系數，其復雜度為O(N^2)
冒泡排序及其復雜度分析

空間復雜度就是在交換元素時那個臨時變數所佔的內存

給定一個整數序列{6,1,2,3,4},每完成一次外層循環的結果為：

我們發現第一次外層循環之後就排序成功了，但是還是會繼續循環下去，造成了不必要的時間復雜度，怎麼優化？

冒泡排序都是相鄰元素的比較，當相鄰元素相等時並不會交換，因此冒泡排序演算法是穩定性演算法

插入排序是對冒泡排序的一種改進

插入排序的思想是數組是部分有序的，再將無序的部分插入有序的部分中去,如圖：
（圖片來自 這里 ）

空間復雜度就是在交換元素時那個臨時變數所佔的內存

插入排序的優化，有兩種方案：

文章後面會給出這兩種排序演算法

由於插入排序也是相鄰元素的比較，遇到相等的相鄰元素時不會發生交換，也不會造成相等元素之間的相對位置發生變化

其原理是從未排序的元素中選出最小值(最大值)放在已排序元素的後面

空間復雜度就是在交換元素時那個臨時變數所佔的內存

選擇排序是不穩定的，比如 3 6 3 2 4，第一次外層循環中就會交換第一個元素3和第四個元素2，那麼就會導致原序列的兩個3的相對位置發生變化

希爾排序算是改良版的插入排序演算法，所以也稱為希爾插入排序演算法

其原理是將序列分割成若乾子序列（由相隔某個 增量 的元素組成的），分別進行直接插入排序；接著依次縮小增量繼續進行排序，待整個序列基本有序時，再對全體元素進行插入排序，我們知道當序列基本有序時使用直接插入排序的效率很高。
上述描述只是其原理，真正的實現可以按下述步奏來：

希爾排序的效率取決於 增量值gap 的選取，這涉及到數學上尚未解決的難題，但是某些序列中復雜度可以為O(N 1.3)，當然最好肯定是O(N)，最壞是O(N 2)

空間復雜度就是在交換元素時那個臨時變數所佔的內存

希爾排序並不只是相鄰元素的比較，有許多跳躍式的比較，難免會出現相同元素之間的相對位置發生變化，所以希爾排序是不穩定的

理解堆排序，就必須得先知道什麼是堆？

二叉樹的特點：

當父節點的值總是大於子結點時為 最大堆 ；反之為 最小堆 ，下圖就為一個二叉堆

一般用數組來表示堆，下標為 i 的結點的父結點下標為(i-1)/2；其左右子結點分別為 (2 i + 1)、(2 i + 2)

怎麼將給定的數組序列按照堆的性質，調整為堆？

這里以建立最小堆為示例，

很明顯對於其葉子結點來說，已經是一個合法的子堆，所以做堆調整時，子節點沒有必要進行，這里只需從結點為A[4] = 50的結點開始做堆調整，即從（n/2 - 1）位置處向上開始做堆調整：

由於每次重新恢復堆的時間復雜度為O(logN)，共N - 1次重新恢復堆操作，再加上前面建立堆時N / 2次向下調整，每次調整時間復雜度也為O(logN)，二次操作時間相加還是O(N logN)。故堆排序的時間復雜度為O(N * logN)。

空間復雜度就是在交換元素時那個臨時變數所佔的內存

由於堆排序也是跨越式的交換數據，會導致相同元素之間的相對位置發生變化，則演算法不穩定。比如 5 5 5 ,堆化數組後將堆頂元素5與堆尾元素5交換，使得第一個5和第三個5的相對位置發生變化

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

快速排序在應該是大家經常看到、聽到的演算法，但是真正默寫出來是有難度的。希望大家看了下面 挖坑填數 方法後，能快速寫出、快速排序。

其原理就這么幾句話，但是現實起來並不是這么簡單，我們採取流行的一種方式 挖坑填數分治法

對於序列： 72 6 57 88 60 42 83 73 48 85

數組變為： 48 6 57 88 60 42 83 73 88 85
再重復上面的步驟，先從後向前找，再從前向後找：

數組變為： 48 6 57 42 60 72 83 73 88 85
可以看出a[5]前面的數字都小於它，a[5]後面的數字都大於它。因此再對a[0…4]和a[6…9]這二個子區間重復上述步驟就可以了

空間復雜度，主要是遞歸造成的棧空間的使用:

快速排序的優化主要在於基準數的選取

快速排序也是跨越式比較及交換數據，易導致相同元素之間的相對位置發生變化，所以快速排序不穩定

前面也說了二分查找排序是改進的插入排序，不同之處在於，在有序區間查找新元素插入位置時，為了減少比較次數提高效率，採用二分查找演算法進行插入位置的確定
具體步驟，設數組為a[0…n]：

二分查找插入位置，因為不是查找相等值，而是基於比較查插入合適的位置，所以必須查到最後一個元素才知道插入位置。
二分查找最壞時間復雜度：當2^X>=n時，查詢結束，所以查詢的次數就為x，而x等於log2n（以2為底，n的對數）。即O(log2n)
所以，二分查找排序比較次數為：x=log2n
二分查找插入排序耗時的操作有：比較 + 後移賦值。時間復雜度如下：

二分查找排序在交換數據時時進行移動，當遇到有相等值插入時也只會插入其後面，不會影響其相等元素之間的相對位置，所以是穩定的

白話經典演算法排序
冒泡排序選擇排序
快速排序復雜度分析
優化的插入排序

D. java實現幾種常見排序演算法

下面給你介紹四種常用排序演算法：

1、冒泡排序

特點：效率低，實現簡單

思想（從小到大排）：每一趟將待排序序列中最大元素移到最後，剩下的為新的待排序序列，重復上述步驟直到排完所有元素。這只是冒泡排序的一種，當然也可以從後往前排。

E. 排序演算法有多少種

排序(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的有序長序列。需要注意的是，在進行元素比較和交換時，若兩個元素大小相等則不必刻意交換位置，因此該演算法不會破壞序列的穩定性，即歸並排序也是穩定的排序演算法。

F. 10種排序演算法

排序演算法是《數據結構與演算法》中最基本的演算法之一。

排序演算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序演算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸並排序、快速排序、堆排序、基數排序等。用一張圖概括：

點擊以下圖片查看大圖：

關於時間復雜度

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

線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸並排序；

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

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

關於穩定性

穩定的排序演算法：冒泡排序、插入排序、歸並排序和基數排序。

不是穩定的排序演算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n：數據規模 k："桶"的個數 In-place：佔用常數內存，不佔用額外內存 Out-place：佔用額外內存 穩定性：排序後 2 個相等鍵值的順序和排序之前它們的順序相同

包含以下內容：

1、冒泡排序 2、選擇排序 3、插入排序數搭 4、希爾排序 5、歸並排序 6、快速排序 7、堆排序 8、計數排序 9、桶排序 10、基數排序

排序演算法包含的相關內容具體如下：

冒泡排序演算法

冒泡排序（Bubble Sort）也是一種簡單直觀的排序演算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該薯畝拿數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢"浮"到數列的頂端。

選擇排序演算法

選擇排序是一種簡單直觀的排序演算法，耐差無論什麼數據進去都是 O(n?) 的時間復雜度。所以用到它的時候，數據規模越小越好。唯一的好處可能就是不佔用額外的內存空間。

插入排序演算法

插入排序的代碼實現雖然沒有冒泡排序和選擇排序那麼簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直觀的排序演算法，它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。

希爾排序演算法

希爾排序，也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序演算法。

歸並排序演算法

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

快速排序演算法

快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 演算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。

堆排序演算法

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。

計數排序演算法

計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

桶排序演算法

桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在於這個映射函數的確定。

基數排序演算法

基數排序是一種非比較型整數排序演算法，其原理是將整數按位數切割成不同的數字，然後按每個位數分別比較。由於整數也可以表達字元串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用於整數。

G. 列舉常見的排序演算法

一、冒泡排序
二、選擇排序
三、插入排序
四、快速排序
五、堆排序
六、歸並排序
七、基數排序
八、希爾排序
九、桶排序
十、二叉排序樹排序

H. 基本排序演算法原理

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

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

演算法步驟

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多個部分，讓每個部分分別有序，然後再將其統一，變成所有的東西都有序。這樣就實現了排序。這個想法就叫分治思想。

排序圖解

排序圖解

I. 常見排序演算法介紹

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

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

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

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

排序過程：

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

排序過程：

將排序過程簡化：

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

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

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

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

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

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

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

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

J. 常見排序演算法歸納

排序演算法一般分類：

比較兩個相鄰的元素，將值大的元素交換至右端。

依次比較兩個相鄰的數，將小數放到前面，大數放到後面

即在第一趟：首先比較第1個數和第2個數，將小數放前，大數放後。然後比較第2個數和第3個數，將小數放前，大數放後，如此一直繼續下去，直到比較最後兩個數，將小數放前，大數放後。然後重復第一趟步驟，直到所有排序完成。

第一趟比較完成後，最後一個數一定是數組中最大的一個數，所以第二趟比較的時候最後一個數不參與比較。

第二趟完成後，倒數第二個數也一定是數組中第二大的數，所以第三趟比較的時候最後兩個數不參與比較。

依次類推......

輸出結果：

冒泡排序的優點： 每進行一趟排序，就會少比較一次，因為每進行一趟排序都會找出一個較大值。如上例：第一趟比較之後，排在最後的一個數一定是最大的一個數，第二趟排序的時候，只需要比較除了最後一個數以外的其他的數，同樣也能找出一個最大的數排在參與第二趟比較的數後面，第三趟比較的時候，只需要比較除了最後兩個數以外的其他的數，以此類推……也就是說，沒進行一趟比較，每一趟少比較一次，一定程度上減少了演算法的量。

用時間復雜度來說：

從一個數組中隨機選出一個數N，通過一趟排序將數組分割成三個部分，1、小於N的區域 2、等於N的區域 3、大於N的區域，然後再按照此方法對小於區的和大於區分別遞歸進行，從而達到整個數據變成有序數組。

如下圖：

假設最開始的基準數據為數組的第一個元素23，則首先用一個臨時變數去存儲基準數據，即 tmp=23 ，然後分別從數組的兩端掃描數組，設兩個指示標志： low 指向起始位置， high 指向末尾。

首先從後半部分開始，如果 掃描到的值大於基準數據 就讓 high-1 ，如果發現有元素比該基準數據的值小，比如上面的 18 <= tmp ，就讓 high位置的值賦值給low位置 ，結果如下：

然後開始從前往後掃描，如果掃描到的值小於基準數據就讓 low+1 ，如果發現有元素大於基準數據的值，比如上圖 46 >= tmp ，就再將 low 位置的值賦值給 high 位置的值，指針移動並且數據交換後的結果如下：

然後再開始從前往後遍歷，直到 low=high 結束循環，此時low或者high的下標就是 基準數據23在該數組中的正確索引位置 ，如下圖所示：

這樣一遍遍的走下來，可以很清楚的知道，快排的本質就是把比基準數據小的都放到基準數的左邊，比基準數大的數都放到基準數的右邊，這樣就找到了該數據在數組中的正確位置。

然後採用遞歸的方式分別對前半部分和後半部分排序，最終結果就是自然有序的了。

輸出結果：

最好情況下快排每次能恰好均分序列，那麼時間復雜度就是O(nlogn)，最壞情況下，快排每次劃分都只能將序列分為一個元素和其它元素兩部分，這時候的快排退化成冒泡排序，時間復雜度為O(n^2)。

插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。

將一個數據插入到 已經排好序的有序數據 中

第一趟排序：

用數組的第二個數與第一個數( 看成是已有序的數據 )比較

第二趟排序：

用數組的第三個數與已是有序的數據 {2,3} (剛才在第一趟排的)比較

在第二步中：

...

後面依此類推

輸出結果：

選擇排序是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法。

舉例：數組 int[] arr={5,2,8,4,9,1}

第一趟排序 ： 原始數據： 5 2 8 4 9 1

最小數據1，把1放在首位，也就是1和5互換位置，

排序結果： 1 2 8 4 9 5

第二趟排序 ：

第1以外的數據 {2 8 4 9 5} 進行比較，2最小，

排序結果： 1 2 8 4 9 5

第三趟排序 ：

除 1、2 以外的數據 {8 4 9 5} 進行比較，4最小，8和4交換

排序結果： 1 2 4 8 9 5

第四趟排序 :

除第 1、2、4 以外的其他數據 {8 9 5} 進行比較，5最小，8和5交換

排序結果： 1 2 4 5 9 8

第五趟排序：

除第 1、2、4、5 以外的其他數據 {9 8} 進行比較，8最小，8和9交換

排序結果： 1 2 4 5 8 9

輸出結果：

歸並排序（merge sort）是利用歸並的思想實現的排序方法，該演算法採用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然後遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。

比如我們對 [8,4,5,7,1,3,6,2] 這個數組進行歸並排序，我們首先利用分治思想的「分」將數組拆分。

輸出結果：