歸并排序.jpg
最近在學(xué)習(xí)算法，歸并排序和快速排序都用到分治思想跛锌，編程實(shí)現(xiàn)方式是通過遞歸添吗。本文旨在給Swift語言開發(fā)者提供編程思路，具體什么是歸并和快排就不做詳細(xì)介紹了瞬哼，畢竟各種書籍和文章很容易搜索婚肆。。
歸并排序坐慰，本文包含三個函數(shù)较性，進(jìn)行排序的函數(shù)是func merge()，merge（）注意細(xì)節(jié)是參數(shù)是有序數(shù)組结胀。
由于之前一直是OC開發(fā)赞咙，對Swift不熟，所數(shù)組的操作浪費(fèi)了自己很多時間糟港，還好實(shí)現(xiàn)出來了攀操，代碼如下，提供給大家參考秸抚，也歡迎指正...
class Sort {
// 合并有序數(shù)組
private func merge(_ array1:[Int], _ array2:[Int])->[Int]{
var a = [Int]()
let m = array1.count
let n = array2.count
var i:Int = 0
var j:Int = 0
while i<m && j<n {
if array1[i] <= array2[j] {
a.append(array1[i])
i += 1
}else{
a.append(array2[j])
j += 1
}
}
if i == m {
a += array2[j..<n]
}else{
a += array1[i..<m]
}
return a
}
// 遞歸分解
private func mergeSortC(_ array:[Int]) -> [Int]{
if array.count <= 1 {
print("count = 1,array:\(array)")
return array
}
print(array)
let tmpArray = array
let n = array.count
let q = (0+n-1)/2
let leftArray = mergeSortC(Array(tmpArray[0...q]))
let rightArray = mergeSortC(Array(tmpArray[q+1...n-1]))
return merge(leftArray,rightArray)
}
// 排序?qū)ν夂瘮?shù)
public func mergeSort(array:[Int]) -> [Int] {
let b:[Int] = mergeSortC(array)
return b
}
}
函數(shù)調(diào)用：
var sort = Sort()
let array = sort.mergeSort(array: [11,8,3,9,7,1,2,5])
print(array)
控制臺輸出:
[1, 2, 3, 5, 7, 8, 9, 11]
