排序算法作為數(shù)據結構與算法的基礎知識逗宜，在實際開發(fā)中有許多的應用；當然還有更重要的一點鳄梅，排序算法幾乎屬于面試必問的知識。博主個人對排序算法做了一些概括未檩，如下文戴尸。
引言
排序總共分為五類：
- 插入排序：直接插入排序，希爾排序
- 選擇排序：直接選擇排序冤狡，堆排序
- 交換排序：冒泡排序孙蒙，快速排序
- 歸并排序
- 基數(shù)排序
下文將分別用一段話來概述其算法的實現(xiàn)项棠；
1. 插入排序
插入排序是通過構建有序序列的基礎上，對于未排序數(shù)據從后向前掃描挎峦，并找出相應位置插入的過程
1.1 直接插入排序
基本思想：順序地將待排序的數(shù)據元素按其關鍵字值的大小插入到已排序數(shù)據元素子集合的適當位置香追。子集合的數(shù)據元素個數(shù)從只有一個數(shù)據元素開始逐次增大，當子集合大小最終與集合大小相同時排序完畢坦胶。
通俗地來講透典，有一數(shù)組a，長度為n,初始第一個元素為集合R{a1}顿苇，依次為R{a1,a2}峭咒、R{a1,a2,a3}、.....岖圈、R{a1,a2,a3,....,an}排序;最終R{a1,a2,a3,....,an}排序的結果即排序完畢讹语；(Notes:集合順序不一定是R{a1,a2,a3})
Java代碼詳見：InsertionSort.java
時間復雜度：
1. 最佳：O(n)
2. 平均：O(n^2)
3. 最壞：O(n^2)
空間復雜度：O(1)
1.2 希爾插入排序
基本思想：把待排序的數(shù)據元素分成若干個小組，對同一小組內的數(shù)據元素用直接插入法排序蜂科；小組的個數(shù)逐次縮小顽决，當完成了所有數(shù)據元素都在一個組內的排序后排序過程結束。希爾排序又稱作為縮小增量排序导匣。
通俗地來講才菠，有一數(shù)組a，長度為n,并設定一組增量,并將數(shù)組a按增量進行分組贡定，例如有一增量為3硝岗，則分組為R{a1,a4,a7.....},R{a2,a5,a8...}等;再將分組好的數(shù)組進行插入排序罕容。
Java代碼詳見：ShellSort.java
時間復雜度：
1. 最佳：O(n)
2. 平均：O((nlog(n))^2)
3. 最壞：O((nlog(n))^2)
空間復雜度：O(1)
增量的選擇：
- 最后一個增量必須為1
- 應避免增量序列中的取值為倍數(shù)（尤其是相鄰的值）膀值，否則會發(fā)生重復比較
2. 選擇排序
選擇排序是每一次從待排序的數(shù)據元素中選出最凶逦帧（或最大）的一個元素，存放在序列的起始位置旋炒，直到全部待排序的數(shù)據元素排完
2.1 直接選擇排序
基本思想：有一數(shù)組R{a0,..,an-1}步悠，按順序從R{a0,..,an-1},R{a1,...,an-1},.......,R{an-2,an-1}中選取出最小值，該值與每次數(shù)組中的第一個元素進行交換,總共需要n-1次瘫镇，得到一個排好序的有序序列鼎兽。
Java代碼詳見：SelectSort.java
時間復雜度：
1. 最佳：O(n^2)
2. 平均：O(n^2)
3. 最壞：O(n^2)
空間復雜度：O(1)
2.2 堆排序
基本思想：即把最大堆堆頂?shù)淖畲髷?shù)取出，之后將剩余的堆重新調整為最大堆铣除，并再次將堆頂?shù)淖畲髷?shù)取出谚咬，直到堆中最后一個數(shù)被取出時結束。一般堆中有如下幾種操作：
- 最大堆調整（Max-Heapify）：將堆的末端子節(jié)點作調整使得子節(jié)點永遠小于父節(jié)點
- 創(chuàng)建最大堆（Build-Max-Heap）：將堆中所有數(shù)據重排序尚粘，使其成為最大堆
- 堆排序（Heap-Sort）：移除位在最大堆中的堆頂元素择卦，并遞歸調用最大堆調整運算
堆排序中幾個重要的節(jié)點計算公式：
- 父節(jié)點：(i-1)/2，i的父節(jié)點下標
- 子節(jié)點(左)：2i + 1，i的左子節(jié)點下標
- 子節(jié)點(右)：2(i+1)秉继，i的右子節(jié)點下標
最大堆與最小堆定義：
- 最大堆(大根堆)：堆頂元素(根節(jié)點)的值是堆中所有值中最大值
- 最小堆(小根堆)：堆頂元素(根節(jié)點)的值是堆中所有值中最小值
Java代碼詳見：HeapSort.java
時間復雜度：
1. 最佳：O(nlog(n))
2. 平均：O(nlog(n))
3. 最壞：O(nlog(n))
空間復雜度：O(1)
3. 交換排序
交換排序是將序列中的值進行比較并按大小進行交換位置潘明；特點為：將值大的數(shù)據向序列尾部一定，將值小的數(shù)據向序列頭部移動
3.1 冒泡排序
基本思想：對每一對相鄰元素作比較大小秕噪，并按照大小交換位置。
- 從a0-an數(shù)組中厚宰，進行相鄰元素比較腌巾，較大者則與較小者交換位置，這樣一次完整比較后則最后一個元素即為最大值
- 剩余a0-an-1為未排序的序列铲觉；重復1）步驟澈蝙，不過是從a0-an-1數(shù)組中進行元素比較
- 持續(xù)每次對越來越少的數(shù)組重復上述的步驟，直到沒有任何一對元素需要比較
Java代碼詳見：BubbleSort.java
時間復雜度：
1. 最佳：O(n)
2. 平均：O(n^2)
3. 最壞：O(n^2)
空間復雜度：O(1)
3.2 快速排序
基本思想：快速排序是基于分治法處理的撵幽，步驟如下：
- 分解：將數(shù)組a[p,r]劃分成兩個子數(shù)組a[p,q-1]和a[q+1,r],使得A[p,q-1] <= A[q] <= A[q+1,r]
- 解決：遞歸調用[分解]步驟灯荧，分別對兩個子數(shù)組進行分解
- 合并：將最終結果進行合并
簡單地說，就是將數(shù)組a[p,r]按數(shù)組中的某個值(基準)劃分盐杂，小于該值的歸為一個數(shù)組逗载，大于該值的歸為一個數(shù)組；之后重復對分解后的數(shù)組進行遞歸操作链烈。
Java代碼詳見：QuickSort.java
時間復雜度：
1. 最佳：O(nlog(n))
2. 平均：O(nlog(n))
3. 最壞：O(n^2)
空間復雜度：O(n log(n))
4. 歸并排序
基本思想：歸并排序也是基于分治法處理的厉斟；歸并排序分為多路歸并和兩路歸并，可用與外排序和內排序强衡；這里主要講下內排序的兩路歸并方式擦秽。
- 分解：將數(shù)組a[p,r]分為(r-p)/2個長度為2的數(shù)組，并使每個數(shù)組都有序
- 合并：將子數(shù)組兩兩合并漩勤，最終合成的數(shù)據則已經排好序
Java代碼詳見：MergeSort.java
時間復雜度：
1. 最佳：O(nlog(n))
2. 平均：O(nlog(n))
3. 最壞：O(n^2)
空間復雜度：O(n)
5. 基數(shù)排序
基本思想：將數(shù)組序列中的數(shù)(必須為正整數(shù))都統(tǒng)一成相同數(shù)位感挥，超出位數(shù)前面補零；然后從最低位開始越败，依次按個位触幼、十位、百位....(具體按數(shù)的位數(shù)決定)的方式進行多次排序眉尸，最終則為有序序列域蜗；
Java代碼詳見：RadixSort.java
時間復雜度：
1. 最佳：O(nk)
2. 平均：O(nk)
3. 最壞：O(nk)
空間復雜度：O(n+k)
k為無序序列中最大值的數(shù)位10^k，例如98->10^2;故k=2
總結
本文主要闡述了這些排序算法的基本思想和時間復雜度等情況噪猾，并附上了本人寫的代碼霉祸；寫此文的初衷亦是為了鞏固自己的排序算法基礎，如果表述不當?shù)牡胤秸堥喿x了本文的朋友多指教袱蜡。謝謝丝蹭！
附上一些排序算法的不錯的blog：
