首页 > 代码库 > 堆排序(Swift版本)

堆排序(Swift版本)

一:什么是堆?

堆可视为  “以数组方式存储的一棵完全二叉树”

堆又分为最大堆和最小堆, 最大堆就是对于整个二叉树中的每一个节点都满足:节点的键值比其左右子节点的键值都要大,对应的最小堆则是:节点的键值比其左右子节点的键值都要小

二:堆排序的思路

    对于一个存储最大堆的数组arr(长度为size), 根节点arr[0]是所有节点中键值最大,将arr[0]和arr[size-1]的值交换,然后将除去arr[size-1]后的size-1个节点作为一个独立的二叉树,但是此时的这课新的树由于前面交换arr[0]和arr[size-1]的原因需要重新调整为堆。

    堆排序就是不断交换和调整的过程。所以我们先要解决两个问题

1.如何调整为最大堆(或者最小堆)

2.如何由一个无序的输入数组生成一个堆

具体代码如下:

调整:输入的参数为一个数组、堆大小和调整的位置(节点对应的数组下标,并假设该节点的左右子树已符合堆性质)

func maxHeapify<Elem: Comparable>(_ arr : inout [Elem], _ size: Int, _ pos: Int) {
    func swap(_ a: inout Elem, _ b: inout Elem) {
        let tmp = a
        a = b
        b = tmp
    }
   
    let l = 2*pos + 1
   
    let r = 2*pos + 2
   
    var index = pos
   
    if l < size && arr[l] > arr[index] {
        index = l
    }
   
    if r < size && arr[r] > arr[index] {
        index = r
    }
   
    if index != pos {
        swap(&arr[pos], &arr[index])
        maxHeapify(&arr, size, index)
    }
}

 

如何建立堆:输入的参数是一个无序的数组(一个从底向上的调整过程)

func buildMaxHeap<Elem: Comparable>(_ arr: inout [Elem]) {
    let bounce = arr.count/2 - 1
   
    for i in (0...bounce).reversed() {
        maxHeapify(&arr, arr.count, i)
    }
}

 

堆排序:

func heapSort<Elem: Comparable>(_ arr: inout [Elem]) {
    func swap(_ a: inout Elem, _ b: inout Elem) {
        let tmp = a
        a = b
        b = tmp
    }
       
    buildMaxHeap(&arr)   
   
    var size = arr.count
       
    while size > 1 {
        swap(&arr[0], &arr[size - 1])
        size = size - 1
        maxHeapify(&arr, size, 0)
    }
}

 

测试:

var intArray = [3, 8, 46, 38, 29, 15, 8]

print("before")

for elem in intArray {
    print("elem = \(elem)")
}

heapSort(&intArray)

print("after")

for elem in intArray {
    print("elem = \(elem)")
}

 

结果:

技术分享

 

测试的环境:https://swiftlang.ng.bluemix.net/#/repl

堆排序(Swift版本)