排序算法可以說是數(shù)據(jù)結(jié)構(gòu)與算法當(dāng)中最為基礎(chǔ)的部分陆爽，針對的是數(shù)組這一數(shù)據(jù)結(jié)構(gòu)缸托。將數(shù)組中的無序數(shù)據(jù)元素通過算法整理為有序的數(shù)據(jù)元素即為排序
算法一：插入排序
插入排序（Insertion Sort）是一種簡單直觀的排序算法姥闪。它的工作原理是通過構(gòu)建有序序列蛔溃，對于未排序數(shù)據(jù)匾竿，在已排序序列中從后向前掃描瓦宜，找到相應(yīng)位置并插入。
步驟如下：
1. 從第一個元素開始岭妖，該元素可以認(rèn)為已經(jīng)被排序
2. 取出下一個元素临庇，在已經(jīng)排序的元素序列中從后向前掃描
3. 如果該元素（已排序）大于新元素反璃，將該元素移到下一位置
4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到該位置中
6. 重復(fù)步驟2
//MARK:- 插入排序
func insertSort(inout arr: [Int]) -> [Int] {
for i in 1 ..< arr.count {
let key = arr[i]
var j = i - 1
while j >= 0 && arr[j] > key {
arr[j + 1] = arr[j]
j -= 1
}
arr[j + 1] = key
}
return arr
}
算法二：希爾排序
希爾排序(Shell Sort)是插入排序的一種假夺。也稱縮小增量排序淮蜈，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法侄泽。
步驟如下：
* 希爾排序是把記錄按下標(biāo)的一定增量分組礁芦，對每組使用直接插入排序算法排序；
* 隨著增量逐漸減少悼尾，每組包含的關(guān)鍵詞越來越多柿扣，當(dāng)增量減至1時，整個文件恰被分成一組闺魏，算法便終止未状。
//MARK:- 希爾排序
func shellSort(inout arr: [Int]) -> [Int] {
var j: Int
var gap = arr.count / 2
while gap > 0 {
for i in 0 ..< gap {
j = i + gap
while j < arr.count {
if arr[j] < arr[j - gap] {
let temp = arr[j]
var k = j - gap
while (k >= 0 && arr[k] > temp) {
arr[k + gap] = arr[k]
k -= gap
}
arr[k + gap] = temp
}
j += gap
}
}
gap /= 2
}
return arr
}
算法三：選擇排序
選擇排序(Selection sort)是一種簡單直觀的排序算法。它的工作原理如下析桥。首先在未排序序列中找到最小元素司草，存放到排序序列的起始位置，然后泡仗，再從剩余未排序元素中繼續(xù)尋找最小元素埋虹，然后放到排序序列末尾驹马。以此類推秩冈，直到所有元素均排序完畢。
步驟如下：
* 遍歷數(shù)組遂铡，找到最小的元素截亦，將其置于數(shù)組起始位置爬泥。
* 從上次最小元素存放的后一個元素開始遍歷至數(shù)組尾，將最小的元素置于開始處崩瓤。
* 重復(fù)上述過程袍啡，直到元素排序完畢。
//MARK:- 選擇排序
func selectionSort(inout arr: [Int]) -> [Int] {
for i in 0 ..< arr.count - 1 {
var min = i
for j in i+1 ..< arr.count {
if arr[min] > arr[j] {
min = j
}
}
let temp = arr[min]
arr[min] = arr[i]
arr[i] = temp
}
return arr
}
算法四：冒泡排序
冒泡排序（Bubble Sort）是一種簡單的排序算法却桶。它重復(fù)地走訪過要排序的數(shù)列境输，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來肾扰。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換畴嘶，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端集晚。
步驟如下：
* 比較相鄰的元素。如果第一個比第二個大区匣，就交換他們兩個偷拔，直到把最大的元素放到數(shù)組尾部蒋院。
* 遍歷長度減一，對剩下的元素從頭重復(fù)以上的步驟莲绰。
* 直到?jīng)]有任何一對數(shù)字需要比較時完成欺旧。
//MARK:- 冒泡排序
func bubbleSort(inout arr: [Int]) -> [Int] {
for i in 0 ..< arr.count {
for j in 0 ..< arr.count - 1 - i {
if arr[j] > arr[j + 1] {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}
算法五：歸并排序
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用蛤签。
步驟如下：
1. 申請空間辞友，創(chuàng)建兩個數(shù)組，長度分別為兩個有序數(shù)組的長度
2. 設(shè)定兩個指針震肮，最初位置分別為兩個已經(jīng)排序序列的起始位置
3. 比較兩個指針?biāo)赶虻脑爻屏x擇相對小的元素放入到合并空間，并移動指針到下一位置
4. 重復(fù)步驟3直到某一指針達(dá)到序列尾
5. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾
//MARK:- 歸并排序
func mergeSort(inout arr: [Int]) -> [Int] {
func merge (inout arr: [Int], low: Int, mid: Int, high: Int, inout temp: [Int]) {
var i = low
var j = mid + 1
let m = mid
let n = high
var k = 0
while (i <= m && j <= n) {
if (arr[i] <= arr[j])
{
temp[k] = arr[i]
k += 1
i += 1
}
else
{
temp[k] = arr[j]
k += 1
j += 1
}
}
while i <= m {
temp[k] = arr[i]
k += 1
i += 1
}
while j <= n {
temp[k] = arr[j]
k += 1
j += 1
}
for f in 0 ..< k {
arr[low + f] = temp[f]
}
}
func internalMergeSort(inout arr: [Int], low: Int, high: Int, inout temp: [Int]) {
if high <= low {
return
}
let mid = low + (high - low) / 2
// 左邊有序
internalMergeSort(&arr, low: low, high: mid, temp: &temp)
// 右邊有序
internalMergeSort(&arr, low: mid + 1, high: high, temp: &temp)
// 將兩邊合起來
merge(&arr, low: low, mid: mid, high: high, temp: &temp)
}
var temp: [Int] = arr// 輔助數(shù)組
internalMergeSort(&arr, low: 0, high: arr.count - 1, temp: &temp)
return arr
}
算法六：快速排序
快速排序（Quicksort）是對冒泡排序的一種改進(jìn)戳晌。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分鲫尊，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序沦偎，整個排序過程可以遞歸進(jìn)行疫向，以此達(dá)到整個數(shù)據(jù)變成有序序列。
步驟：
* 從數(shù)列中挑出一個元素豪嚎，稱為 “基準(zhǔn)”（pivot）搔驼，
* 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面侈询，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）舌涨。在這個分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置妄荔。這個稱為分區(qū)（partition）操作泼菌。
* 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
//MARK:- 快速排序
func quickSort(inout arr: [Int]) -> [Int] {
func partition(p: Int, _ r: Int) -> Int {
var i = p - 1
let key = arr[r]
for j in p ..< r {
if arr[j] < key {
i = i + 1
let temp = arr[j]
arr[j] = arr[i]
arr[i] = temp
}
}
arr[r] = arr[i + 1]
arr[i + 1] = key
return i + 1
}
func internalQuickSort(p: Int, _ r: Int) {
if p < r {
let q = partition(p, r)
internalQuickSort(p, q - 1)
internalQuickSort(q + 1, r)
}
}
internalQuickSort(0, arr.count - 1)
return arr
}
算法七：堆排序
堆排序（Heap Sort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法啦租。堆是一個近似完全二叉樹的結(jié)構(gòu)哗伯，并同時滿足堆性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。
步驟如下：
* 按堆的定義將數(shù)組R[0..n]調(diào)整為堆（這個過程稱為創(chuàng)建初始堆）篷角，交換R[0]和R[n]焊刹；
* 將R[0..n-1]調(diào)整為堆，交換R[0]和R[n-1]恳蹲；
* 重復(fù)上述過程虐块，直到交換了R[0]和R[1]為止。
//MARK:- 堆排序
func heapSort(inout arr: [Int]) -> [Int] {
func buildheap(inout arr: [Int]) {
let length = arr.count
let heapsize = length
var nonleaf = length / 2 - 1
while nonleaf >= 0 {
heapify(&arr, i: nonleaf, heapsize: heapsize)
nonleaf -= 1
}
}
func heapify(inout arr: [Int], i : Int, heapsize: Int){
var smallest = i
let left = 2*i+1
let right = 2*i+2
if(left < heapsize){
if(arr[i]>arr[left]){
smallest = left
}
else {
smallest = i
}
}
if(right < heapsize){
if(arr[smallest] > arr[right]){
smallest = right
}
}
if(smallest != i){
var temp: Int
temp = arr[i]
arr[i] = arr[smallest]
arr[smallest] = temp
heapify(&arr,i: smallest,heapsize: heapsize)
}
}
func internalHeapSort(inout arr: [Int]) {
var heapsize = arr.count
buildheap(&arr)
for _ in 0 ..< arr.count - 1 {
var temp: Int
temp = arr[0]
arr[0] = arr[heapsize - 1]
arr[heapsize - 1] = temp
heapsize = heapsize - 1
heapify(&arr, i: 0, heapsize: heapsize)
}
}
internalHeapSort(&arr)
return arr
}
參考
http://codecloud.net/sort-2208.html
http://wenzhiquan.github.io/2016/03/28/seven_sort/
