顧名思義，所謂排序算法（Sorting Algorithm）就是将一組資料按某種特定的順序重新排列組織。顯然，這一需要是我們在日常處理工作當中總是要用到的。這也是排序算法是計算機世界中最為重要的算法的原因。最為常見的順序是 數值順序 和 字元順序。對于一些其它算法的優化，一個高效的排序算法是起決定性作用的，比如查找、合并等。
排序算法的分類與評價
- 計算複雜度（Computational Complexity），包括最壞、平均、最佳情況，通常由資料元素的數量（n）來計算，而用大O符号來表達。理想的計算複雜度是 O(n)，但一般而言，好的性能是 O(n log n)，平均性能是 O(log^2 n)。
- 空間使用（Memory Usage），指除了待排序的源資料外，算法所需的額外的臨時存儲空間。通常将不使用或使用有限個（常數）元素O(1)額外空間的排序算法，稱為原地排序算法（In Place Sorting），比如冒泡排序。
- 穩定性（Stability），如果一個排序算法對于源資料中兩個排序關鍵值相同的元素，在排序後不改變其原有順序的，則稱這個排序算法是穩定的。比如以下對(2, 9) (1, 3) (2, 7) (3, 4)四個數字對按第一個數字排序時，穩定的算法則會得到 (1, 3) (2, 9) (2, 7) (3, 4)，而不穩定的算法則會得到 (1, 3) (2, 7) (2, 9) (3, 4)。
- 是否使用遞歸，通常程式語言都會對遞歸寄存器有所限制，一些早期的語言甚至不支援遞歸。
- 是否對比，多數的排序算法都會進行元素間的對比，但也有些算法是不用對比的，如計數排序。
- 排序方式，包括 插入、交換、選擇、合并 等等。
- 冒泡排序
運作方式：
1、比較相鄰的兩個元素，按所需順序決定是否交換。
2、對每一對相鄰元素進行同樣的工作，從第一對至最後一對。結束後，最後一個元素應該是所需順序的最值（如所需順序為由小至大，則為最大值）。
3、對所有元素重複上述步驟，除了最後一個。
4、重複前述步驟，稱前部分需要對比的為無序區，後部分不需要對比的為有序區，直到無序區僅剩一個元素。
[code=vb]Sub BubbleSort(ByRef arr)
Dim i&, j&, vSwap
For i = UBound(arr) To 2 Step -1
For j = 1 To i - 1
If arr(j) > arr(j + 1) Then
vSwap = arr(j): arr(j) = arr(j +1): arr(j + 1) = vSwap
End If
Next
Next
End Sub[/code]
注：有很多人的習慣的由小至大的雙循環（如下），真正的冒泡總是在一次循環後将最值元素冒泡式的置于有序區。
[code=vb]For i = 1 To UBound(arr) - 1
For j = i + 1 To UBound(arr)
If arr(i) > arr(j) Then vSwap = arr(i): arr(i) = arr(j): arr(j) = vSwap
Next
Next[/code] - 選擇排序
運作方式：
1、對（無序區）全部元素由前至後掃描，找出最值。
2、将最值元素與（無序區）第一個元素交換，此時前端為有序區，後端為無序區。
3、重複上述步驟，直到無序區僅剩一個元素。
[code=vb]Sub SelectionSort(ByRef arr)
Dim i&, j&, vSwap, min&
For i = 1 To UBound(arr) - 1
min = i
For j = i + 1 To UBound(arr)
If arr(min) > arr(j) Then min = j
Next
If min <> i Then
vSwap = arr(min): arr(min) = arr(i): arr(i) = vSwap
End If
Next
End Sub[/code] - 插入排序
運作方式：
1、全部元素同樣的分為有序區在前和無序區在後，開始時有序區僅有第一個元素。
2、取無序區的第一個元素，與有序區中元素由後至前掃描對比。
3、将該元素插入至正确位置，該位置（含）之後的有序區元素向後移位，将該位置指派為該元素。
4、重複上述步驟，直至無序區僅剩一個元素。
[code=vb]Sub InsertionSort(ByRef arr)
Dim i&, j&, vTemp
For i = 2 To UBound(arr)
vTemp = arr(i)
For j = i To 2 Step -1
If arr(j - 1) < vTemp Then Exit For
arr(j) = arr(j-1)
Next
arr(j) = vTemp
Next
End Sub[/code] - 快速排序
運作方式：
快速排序與二叉查找樹基于一樣的思路，采用了分治（Divide & Conquer）的政策。
1、選擇一個元素作為比較的基準（Pivot）。
2、将所有元素與基準逐個對比，按所需順序置于基準的兩側，如升序排列時大的放在基準右側、小的放在左側，将整個資料劃分為左右兩個分區。
3、視左右兩個分區為兩個單獨的待排序資料，遞歸的重複上述操作，直至分區中元素隻有一個。
取分區第一個元素作為基準的VBA實作，調用時 nLeft=LBound(arr): nRight=UBound(arr)：
[code=vb]Sub QuickSort(ByRef arr, ByRef nLeft&, ByRef nRight&)
Dim i&, j&, vKey, vSwap
If nLeft >= nRight Then Exit Sub
vKey = arr(nLeft)
i = nLeft + 1: j = nRight
Do
Do While i <= nRight
If arr(i) > vKey Then Exit Do
i = i + 1
Loop
Do While j > nLeft
If arr(j) < vKey Then Exit Do
j = j - 1
Loop
If i >= j Then Exit Do
vSwap = arr(i): arr(i) = arr(j): arr(j) = vSwap
Loop
If nLeft <> j Then
vSwap = arr(nLeft): arr(nLeft) = arr(j): arr(j) = vSwap
End If
If nLeft < j Then Call QuickSort(arr, nLeft, j)
If j + 1 < nRight Then Call QuickSort(arr, j + 1, nRight)
End Sub[/code] - 希爾排序
希爾排序是插入排序的一個優化。在插入排序中，每次對比是由後前逐個對比，或言對比的步長為1。有個叫Donald Shell的家夥提出，對比的步長可由大至小，直至步長為1變為插入排序。這樣一來在最初的幾個對比步長中，較小的元素（假設按升序排序）就會向目标位置前進一大步。
運作方式：
1、設定步長序列，由大至小。
2、由步長序列中，逐個擷取步長。
3、由源資料中第步長+1個元素向後掃描，作為基準值。
4、由步驟3中的基準值元素向前掃描與基準值對比，并進行必要的位移，同時每次遞減為步長而不是1。
5、将基準值插入到正确的位置。
6、重複2、3、4、5，直至步長為1。
以上就是排序的常用小技巧，或許你可以試一下
長按二維碼，識别關注