前言
排序算法可謂數(shù)據(jù)結(jié)構(gòu)中的基礎(chǔ)知識(shí)。在實(shí)際編碼工作中，直接手寫排序算法的情況越來越少，更多的是應(yīng)用其思想來指引我們更好的寫出高效率的代碼。溫故而知新，寫這篇文章目的就是筆者記錄復(fù)習(xí)的一個(gè)過程。
常見幾種排序
| 名稱 | 時(shí)間復(fù)雜度 | 空間復(fù)雜度 | 是否穩(wěn)定 |
|---|---|---|---|
| 冒泡排序 | O(n^2) | O(1) | 是 |
| 插入排序 | O(n^2) | O(1) | 是 |
| 選擇排序 | O(n^2) | O(1) | 否 |
| 堆排序 | O(nlogn) | O(1) | 否 |
| 歸并排序 | O(nlogn) | O(1) | 是 |
| 快速排序 | O(nlogn) | O(1) | 否 |
| 桶排序 | O(n) | O(k) | 是 |
冒泡排序
它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。
算法思路：
1 ，比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
2 ，對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
3， 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
4，持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。實(shí)現(xiàn)
func bubleSort<T:Comparable>(_ array:[T] , _ compare:(T,T) -> Bool) -> [T] {
var tempArray = array
for i in 1..<tempArray.count {
for j in 0..<tempArray.count - I {
if compare(tempArray[j],tempArray[j + 1]) {
tempArray.swapAt(j, j+1)
}
}
}
return tempArray
}
插入排序
插入排序是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
算法思路
1，從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序
2，取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
3，如果該元素（已排序）大于新元素，將該元素移到下一位置
4，重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
5，將新元素插入到該位置后
6，重復(fù)步驟2~5實(shí)現(xiàn)
func insertSort<T : Comparable> (_ array : [T], _ compare:(T,T) -> Bool ) -> [T]{
var tempArray = array
for var i in 1..<tempArray.count {
while i > 0 && compare(tempArray[i], tempArray[i - 1]) {
tempArray.swapAt(i, i - 1)
i -= 1
}
}
return tempArray
}
選擇排序
首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)。如果某個(gè)元素位于正確的最終位置上，則它不會(huì)被移動(dòng)。選擇排序每次交換一對(duì)元素，它們當(dāng)中至少有一個(gè)將被移到其最終位置上，因此對(duì)N個(gè)元素的表進(jìn)行排序總共進(jìn)行至多N-1次交換。在所有的完全依靠交換去移動(dòng)元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N。
- 思路
1，循環(huán)比較當(dāng)次數(shù)組中最大或最小的數(shù)值，并標(biāo)記。
2，如果發(fā)現(xiàn)最大或最小數(shù)值，進(jìn)行交換位置。 - 實(shí)現(xiàn)
func selectionSort<T : Comparable> (_ array:[T] , _ compare:(T,T) -> Bool) -> [T]{
var tempArray = array
for i in 0..<tempArray.count-1 {
var selectedItemIndex = I
for j in i+1..<tempArray.count {
if compare(tempArray[selectedItemIndex],tempArray[j]) {
selectedItemIndex = j
}
}
if selectedItemIndex != I {
tempArray.swapAt(miniItemIndex, i)
}
}
return tempArray
}
堆排序
是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。
思路
1，最大堆調(diào)整（Max_Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)。
2，創(chuàng)建最大堆（Build_Max_Heap）：將堆所有數(shù)據(jù)重新排序。
3，堆排序（HeapSort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算。實(shí)現(xiàn)
/**
* 最大堆調(diào)整
*/
func heapify(_ array:inout [Int], _ i:Int,_ size:Int) {
let left = 2 * I
let right = left + 1
var largest = I
if left < size && array[left] > array[i] {
largest = left
}
if right < size && array[right] > array[largest] {
largest = right
}
if largest != I {
array.swapAt(i, largest)
heapify(&array,largest,size)
}
}
/**
* 構(gòu)建最大堆
*/
func buildHeap(_ array:inout [Int]) {
var i = array.count
while i > 0 {
heapify(&array, i - 1, array.count)
I-=1
}
print("build heap:\(array)")
}
/**
*堆排序
*/
func heapSort(_ array: inout [Int]) {
buildHeap(&array)
var size = array.count
for i in stride(from: array.count-1, through: 1, by: -1){
array.swapAt(i, 0)
size-=1
heapify(&array, 0, size)
}
print("sorted heap:\(array)")
}
歸并排序
歸并排序是創(chuàng)建在歸并操作上的一種有效的排序算法，1945年由約翰·馮·諾伊曼首次提出。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用，且各層分治遞歸可以同時(shí)進(jìn)行。
- 思路
- 將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作
ceil(n/2)個(gè)序列，排序后每個(gè)序列包含兩/一個(gè)元素 - 若此時(shí)序列數(shù)不是1個(gè)則將上述序列再次歸并，形成
ceil()個(gè)序列，每個(gè)序列包含四/三個(gè)元素 - 重復(fù)步驟2，直到所有元素排序完畢，即序列數(shù)為1
- 實(shí)現(xiàn)
func mergeSort(array: [Int]) -> [Int] {
var helper = Array(count: array.count, repeatedValue: 0)
var array = array
mergeSort(&array, &helper, 0, array.count - 1)
return array
}
func mergeSort(inout array: [Int], inout _ helper: [Int], _ low: Int, _ high: Int) {
guard low < high else {
return
}
let middle = (high - low) / 2 + low
mergeSort(&array, &helper, low, middle)
mergeSort(&array, &helper, middle + 1, high)
merge(&array, &helper, low, middle, high)
}
func merge(inout array: [Int], inout _ helper: [Int], _ low: Int, _ middle: Int, _ high: Int) {
// copy both halves into a helper array
for i in low ... high {
helper[i] = array[i]
}
var helperLeft = low
var helperRight = middle + 1
var current = low
// iterate through helper array and copy the right one to original array
while helperLeft <= middle && helperRight <= high {
if helper[helperLeft] <= helper[helperRight] {
array[current] = helper[helperLeft]
helperLeft += 1
} else {
array[current] = helper[helperRight]
helperRight += 1
}
current += 1
}
// handle the rest
guard middle - helperLeft >= 0 else {
return
}
for i in 0 ... middle - helperLeft {
array[current + i] = helper[helperLeft + I]
}
}
快速排序
快速排序，又稱劃分交換排序，一種排序算法,最早由東尼·霍爾提出。
- 思路
- 從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot），
- 重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。
- 遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
遞歸到最底部時(shí)，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個(gè)算法一定會(huì)結(jié)束，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。
- 實(shí)現(xiàn)
func breakCollection (array : inout Array<Int> , left : Int ,right : Int) -> Int{
var left = left
var right = right
let temp = array[left]
while left < right {
while left < right && array[right] >= temp {
right -= 1
}
array[left] = array[right]
while left < right && array[left] <= temp {
left += 1
}
array[right] = array[left]
}
array[left] = temp
print(array)
return left
}
func quickSort(array : inout Array<Int> , start:Int ,end:Int) ->Array<Int>{
if start < end {
let mid = breakCollection(array: &array, left: start, right:end)
quickSort(array: &array, start: 0, end: mid - 1)
quickSort(array: &array, start: mid + 1, end: end)
}
return array
}
結(jié)語
算法排序的精妙之處在于前人總結(jié)的數(shù)據(jù)處理理論，合理的利用好各個(gè)算法能夠提高我們?nèi)粘＞幋a的效率。理解學(xué)會(huì)算法，避免死記硬背，學(xué)會(huì)運(yùn)用，而不是照搬代碼。共勉！
Refrence
https://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F
https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F
https://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F
https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
http://www.itdecent.cn/p/70e08f1a95c6
