Swift - 快速排序
发布时间:2020-12-14 06:08:07 所属栏目:百科 来源:网络整理
导读:思想 基本思想 : 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再递归每一部分,得到最后结果 步骤 设置一个pivot,一般取第一个元素 从后向前找一个比pivot元素小的数,交换位置(将大元素与pivot
思想基本思想 : 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再递归每一部分,得到最后结果 步骤
代码import Foundation
//快速排序
var unsortedList : [Int] = []
//排序20个 0-99的随机整数
for i in 0..<20 {
unsortedList.append(Int(arc4random_uniform(UInt32(100))))
}
print("快排原始数组 : (unsortedList)nn")
//统计一下快排的次数
var sortCount : Int = 0
//时间复杂度为O(NlogN)
quickSort(&unsortedList,low: 0,high: unsortedList.count - 1)
//递归调用
private func quickSort(_ list : inout [Int],low : Int,high : Int){
if low < high {
let prePivot = quickSortNode(&list,low: low,high: high)
quickSort(&list,high: prePivot - 1)
quickSort(&list,low: prePivot + 1,high: high)
}
}
//单次快排
private func quickSortNode(_ list : inout [Int],high : Int) -> Int{
var low = low
var high = high
let pivot = list[low]
//上下未相遇
while low < high {
//从后面找一个比pivot小的数,填入pivot位置
while low < high && list[high]>=pivot {
high -= 1
}
list[low] = list[high]
//从前面找一个比pivot大的数,填入刚刚放入位置
while low < high && list[low]<=pivot {
low += 1
}
list[high] = list[low]
}
//pivot放入坑
list[low] = pivot
//统计快排次数的
sortCount += 1
print("第(sortCount)次快排后的结果 result:(list)n")
return low
}
结果特性(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |