1.歸并排序
- 歸并排序概念
歸并排序核心思想是分治媳叨，即將完整數(shù)組拆分成更小的數(shù)組万牺，最小單位位1，每個小的數(shù)組排好序彩匕， 然后依次合并數(shù)組腔剂，遞歸變小然后再遞歸變大的過程。
過程如圖
image.png
- 代碼如下swift版本
let orList:[Int] = [1,2,6,8,4,5,7]
print(orList)
let list = [Int]()
func mergeSort(_ array:[Int])->[Int]{
var helper = Array(repeating: 0, count: array.count)
var array = array
mergeSort(&array, &helper, 0, array.count-1)
return array;
}
//拆分驼仪，將數(shù)組拆分成小單位的數(shù)組 單位為1
func mergeSort(_ array:inout [Int], _ helper:inout [Int], _ low: Int, _ height:Int){
guard low < height else {
return
}
let middel = (height - low)/2 + low
//拆分左邊
mergeSort(&array, &helper, low, middel)
print("1 \(low),\(height),\(middel),\(array)")
//拆分右邊
mergeSort(&array, &helper, middel+1, height)
print("2 \(low),\(height),\(middel),\(array)")
//對當(dāng)前數(shù)組排序
merge(&array, &helper, low, height, middel)
print("3 \(low),\(height),\(middel),\(array)")
}
func merge(_ array:inout [Int], _ helper:inout [Int], _ low: Int, _ height:Int, _ middel:Int){
//將目標(biāo)數(shù)組賦值給輔助數(shù)組
for i in low ... height {
helper[i] = array[i]
}
//初始化游標(biāo)
var helperLeft = low, helperRight = middel+1
var current = low
//因為middle左右的數(shù)組都是排好序的，只需要依次將游標(biāo)處的比較小的放入array數(shù)組袜漩，
//這里有兩種情況绪爸，一種是左游標(biāo)沒走完 后邊需要在進(jìn)行往后賦值，一種是右游標(biāo)沒走完宙攻，因為右邊已經(jīng)在后邊不需要再重復(fù)處理
while helperLeft <= middel && helperRight <= height {
if helper[helperLeft] <= helper[helperRight] {
array[current] = helper[helperLeft]
helperLeft += 1
}else{
array[current] = helper[helperRight]
helperRight += 1
}
current += 1
}
guard middel - helperLeft >= 0 else {
return
}
//將左數(shù)組沒有處理完的數(shù)據(jù)拼接到數(shù)組后邊
for i in 0 ... middel - helperLeft {
array[current+i] = helper[helperLeft+i]
}
}
let array = mergeSort(orList)
print(array)
時間復(fù)雜度最好最壞O(nlog2n) 空間復(fù)雜度O(n) 穩(wěn)定排序
2.快速排序
快排是選取數(shù)組中某一個元素key奠货，將比key小的放在左邊，比key大的放在右邊座掘，然后對key左邊的數(shù)組和key右邊的數(shù)組分別進(jìn)行相同的操作递惋。
swift代碼如下：
var orList:[Int] = [10,2,6,8,1,4,5,7,89]
print(orList)
func speedSort(_ array:inout [Int]){
guard array.count > 0 else {
return
}
speedSort(&array, left: 0, right: array.count-1)
}
func speedSort(_ array:inout [Int], left: Int, right: Int){
guard left < right else {
return
}
let temp = array[left]
var pre = left
var post = right
while pre < post {
while pre < post && array[post] >= temp {
post -= 1
}
array[pre] = array[post]
while pre < post && array[pre] <= temp {
pre += 1
}
array[post] = array[pre]
}
array[pre] = temp
speedSort(&array, left: left, right: pre-1)
speedSort(&array, left: pre+1, right: right)
}
speedSort(&orList)
print(orList)
時間復(fù)雜度O(nlog2n) 最壞O(n^2) 空間復(fù)雜度O(log2n) 不穩(wěn)定排序
