swift 3.1 堆排序
2017-04-25 本文已影响10人
ping_oO
//
func heapsAdjust(array:Array<Int>, parent:Int, length:Int) -> Array<Int> {
var array = array
var parent = parent
let parentPoint = array[parent] //父节点
var child = parent*2+1 //左节点
while child+1<=length {
if child+1<length && array[child]<array[child+1] {
child = child + 1
}
if parentPoint < array[child] {
array[parent] = array[child]
parent = child
child = child*2+1
}else {
break;
}
}
array[parent] = parentPoint
return array
}
//排序
func heapSort(array:Array<Int>) -> Array<Any>? {
var array = array
// 循环建立初始堆
for i in (0...array.count/2).reversed() {
autoreleasepool {
array = heapsAdjust(array: array, parent: i, length: array.count)
}
}
for i in (0...array.count-1).reversed() {
autoreleasepool {
// 最后一个元素和第一元素进行交换
let temp = array[i];
array[i] = array[0];
array[0] = temp;
array = heapsAdjust(array: array, parent: 0, length: i)
print("\(array.count-i)---\(array)")
}
}
return array
}
调用:
heapSort(array: [1, 3, 4, 5, 2, 6, 9, 7, 8, 0])
reason.png