前言
之前對(duì)排序算法理解不是很深刻，也容易把幾個(gè)算法混在一起，所以整理了幾個(gè)常用的排序算法，并嘗試在自己的理解上給幾個(gè)算法優(yōu)化了下。
冒泡排序
冒泡應(yīng)該是最好理解的排序算法，所以把它放在第一個(gè)講。冒泡的思想是：兩兩比較相鄰記錄，步驟為:
1、從第一個(gè)元素開始往后遍歷數(shù)組，并與每個(gè)元素對(duì)比，如果比其他元素小則交換元素
2、從第二個(gè)元素開始往后遍歷數(shù)組，并與每個(gè)元素對(duì)比，如果比其他元素小則交換元素
3、......
用代碼實(shí)現(xiàn)為：
func bubbleSort(var arr:[Int]) -> [Int]{
for i in 0..<arr.count {
for var j = i+1; j < arr.count; j++ {
if arr[i] > arr[j] {
let guide = arr[j]
arr[j] = arr[i]
arr[i] = guide
}
}
}
return arr
}
這是最傳統(tǒng)的冒泡排序，需要執(zhí)行的步驟為 n + (n-1) + (n-2) + (n-3) + ......+ 1= (n+1)*n/2,所以時(shí)間復(fù)雜度為O(n^2)。
傳統(tǒng)的冒泡排序只是暴力遍歷數(shù)組，逐個(gè)比較大小，只要比當(dāng)前值小的就會(huì)交換，將當(dāng)前位置排好的過程中，對(duì)于接下來的排序沒有任何的幫助，所以需要做一些改善。
如果在遍歷的時(shí)候從后往前遍歷，然后將較小的數(shù)往前面排，這樣的話在接下來的排列過程中，就會(huì)更有優(yōu)勢，因?yàn)槟阍诎旬?dāng)前位置排列好的同時(shí)將某些相對(duì)小的元素也排到了前面，在數(shù)據(jù)較多的時(shí)候能大大減少數(shù)據(jù)兩兩交換的次數(shù)。
口頭描述比較抽象，還是看代碼吧
func betterBulleSort(var arr:[Int]) -> [Int]{
for i in 0..<arr.count {
//從后往前遍歷，這里是與傳遞冒泡不一樣的地方
for var j = arr.count - 1; j>0 && j>=i; j-- {
//如果前面的元素比當(dāng)前的大，就把當(dāng)前元素往前移
if arr[j-1] > arr[j] {
let guide = arr[j-1]
arr[j-1] = arr[j]
arr[j] = guide
}
}
}
return arr
}
除此之外，如果待排序的數(shù)組為
2,1,3,4,5,6,7,8
在第一次1和2交換位置之后整個(gè)數(shù)組就是有序的了，接下來的所有比較都是浪費(fèi)的。這種情況下可以設(shè)置一個(gè)flag，增加一個(gè)flag為真才繼續(xù)遍歷的控制，代碼實(shí)現(xiàn)為：
func bestBubbleSort(var arr:[Int]) -> [Int]{
var flag = true
for i in 0..<arr.count {
//如果flag為假則說明接下來的每個(gè)數(shù)都是有序的
if !flag { break }
for var j = arr.count - 1; j>0 && j>=i; j-- {
//每次遍歷都默認(rèn)flag為false
flag = false
if arr[j-1] > arr[j] {
let guide = arr[j-1]
arr[j-1] = arr[j]
arr[j] = guide
//當(dāng)有發(fā)生位置交換，設(shè)置flag為真，表明接下來的數(shù)可能是無序
flag = true
}
}
}
return arr
}
簡單排序
簡單排序的核心思想：找準(zhǔn)時(shí)機(jī)、再做替換
和冒泡相比，冒泡每次都做替換，簡單排序是遍歷數(shù)組后找到最小元素的下標(biāo)后再做替換。
func simpleSort(var arr:[Int]) -> [Int] {
var minIndex = 0
for i in 0..<arr.count {
minIndex = i
//遍歷找到最小元素所在的下標(biāo)
for var j = i+1; j<arr.count; j++ {
if arr[j]<arr[minIndex] { minIndex = j }
}
//如果最小元素下標(biāo)不是當(dāng)前下標(biāo)就交換
if minIndex != i {
let guide = arr[i]
arr[i] = arr[minIndex]
arr[minIndex] = guide
}
}
return arr
}
簡單排序的時(shí)間復(fù)雜度也是O(N^2)
雖然簡單排序和冒泡排序的時(shí)間復(fù)雜度一樣，但是簡單排序在性能方面還是好很多的，交換次數(shù)沒像冒泡那么頻繁。
直接插入排序
直接插入排序的基本操作是將一個(gè)無序的數(shù)插入到有序的表中，從而得到一個(gè)有序的表。
步驟：
1、將需要插入的數(shù)取出賦值給哨兵。
2、向前遍歷表，每個(gè)元素都與哨兵比較大小，如果比哨兵大，則將這個(gè)元素向后移動(dòng)一個(gè)位置，知道找到比哨兵小的元素，將哨兵放入該位置。
看看代碼實(shí)現(xiàn)：
func directInsertSort(var arr:[Int]) -> [Int] {
var guide = 0
for i in 1..<arr.count {
//如果當(dāng)前元素比前面元素大說明現(xiàn)在為有序狀態(tài)
if arr[i-1] < arr[i] { continue }
//取出需要排序的元素
guide = arr[i]
//向前遍歷表，每個(gè)元素與哨兵比較大小
for var j=i-1; j>=0 && arr[j]>guide; j-- {
//比哨兵大的元素向后移動(dòng)
arr[j+1] = arr[j]
}
//將哨兵插入合適位置
arr[j+1] = guide
}
return arr
}
直接插入排序的時(shí)間復(fù)雜度為O(n^2)
希爾排序
希爾排序（Shell Sort）可以看成是對(duì)直接插入排序的優(yōu)化，相對(duì)于直插法，它比較的步長變長了，基本思路為，將一個(gè)以一定的步長分割為多個(gè)組，每個(gè)組分別使用直插法進(jìn)行排序，之后縮短步長，繼續(xù)這個(gè)操作，直到步長為1為止。希爾排序使得排序算法的時(shí)間復(fù)雜度突破了O(n^2)的限制。
假設(shè)有這樣一組數(shù)
[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]
共16個(gè)元素如果我們以步長為5開始進(jìn)行排序
先將這組數(shù)一五為步長，分為幾組，第一組為[a0,a5,a10,a15]，第二組為[a2,a6,a11],第三組為......，分完組應(yīng)該是這樣的：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后用直插法對(duì)每列進(jìn)行排序，得到：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
經(jīng)過第一次排序得到的數(shù)組為：
[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]
可以看出第一個(gè)元素10已經(jīng)在正確的位置上了，接下來已3為步長再次對(duì)數(shù)組進(jìn)行分組：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序：
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后再以步長為1進(jìn)行排序，這里就是直接插入排序了
代碼實(shí)現(xiàn)為：
func shell(var arr:[Int]) -> [Int] {
//指定步長
var gap = arr.count
var temp = 0
var j = 0
do{
gap /= 2
for i in gap..<arr.count
{
if arr[i] > arr[i-gap] { continue }
temp = arr[i]
for j = i-gap; j>0 && arr[j]>temp;j-=gap {
arr[j+gap] = arr[j]
}
arr[j+gap] = temp
}
}while(gap>1)
return arr
}
希爾算法的步長是決定時(shí)間復(fù)雜度的關(guān)鍵，但是究竟應(yīng)該選擇什么樣的步長才是最好的，目前還是一個(gè)數(shù)學(xué)難題。不過大量的研究數(shù)據(jù)表明，步長與時(shí)間復(fù)雜度存在以下關(guān)系：
快速排序
快速排序應(yīng)該是排序算法中最經(jīng)典的了，最早是由圖靈獎(jiǎng)的獲得者Tony Hoare設(shè)計(jì)出來的。它與冒泡排序比較相似，也是通過不斷比較得出有序的表，但是相對(duì)于冒泡，快排中增大了記錄的比較和移動(dòng)距離，將關(guān)鍵字較大的記錄直接移動(dòng)到后面，關(guān)鍵字較小的記錄從后面移動(dòng)到前面，從而大大減少了總的比較次數(shù)和移動(dòng)交換次數(shù)。
快排的基本思想是：通過一趟排序?qū)⒋判虻谋矸譃閮刹糠?，即比關(guān)鍵字小的部分和比關(guān)鍵字大的部分，然后再對(duì)這兩個(gè)部分重復(fù)操作，直到整個(gè)序列有序
文字描述難免有些抽象，來看看代碼怎么實(shí)現(xiàn)吧，在看代碼過程中請(qǐng)記住快排序的基本思想，會(huì)有助于理解
func quickSort(var arr:[Int], var low:Int, var high:Int) -> [Int]{
//遞歸退出條件
if low < high {
/*!
*1、獲取flag值的下標(biāo)和已經(jīng)初略排序好的數(shù)組：
*flag前（后）面的元素比flag值?。ù螅?，
*/
let pivot = partition(arr, low: low, high: high).0
arr = partition(arr, low: low, high: high).1
/*!
*2、遞歸，flag前后兩部分繼續(xù)此操作，直到有序?yàn)橹? */
arr = quickSort(arr, low: low, high: pivot-1)
arr = quickSort(arr, low: pivot+1, high: high)
}
return arr
}
func partition(var arr:[Int], var low:Int, var high:Int) -> (Int,[Int]) {
var flag = arr[low]
var guide:Int?
/*!
*兩頭開工，遍歷數(shù)組，
*將比key大的移動(dòng)到后面，
*比key小的移動(dòng)到前面
*/
while (low < high){
//往前遍歷
while low<high && arr[high]>flag { high-- }
arr = swapeObject(arr, low: low, high: high)
//往后遍歷
while low<high && arr[low]<flag{ low++ }
arr = swapeObject(arr, low: low, high: high)
}
return ((arr as NSArray).indexOfObject(flag),arr)
}
//MARK: 交互元素
func swapeObject(var arr:[Int], low:Int, high:Int) -> [Int]{
let guide = arr[high]
arr[high] = arr[low]
arr[low] = guide
return arr
}
