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

参考:
http://www.cnblogs.com/jingmoxukong/p/4303826.html

上一篇下一篇

猜你喜欢

热点阅读