排序学习 - 为了面对算法面试(4)

排序学习 - 为了面对算法面试(3) -快速排序

• 6.堆排序: 堆排序是利用堆的性质进行的一种选择排序

  方法原理:

  • 1.建最大堆
  • 2.取出堆顶值,将堆底放到堆顶(这时的堆已不符合最大堆的性质)
  • 3.维护剩余元素,使其成为最大堆
  • 4.重复过程 2 3
  • 5.排序完成

func heapSort(arr: inout [Int]){
    var heapSize = arr.count
    //构建最大堆
    buildMaxHeap(arr: &arr, heapSize: heapSize)
    while heapSize > 1 {
        //交换堆顶和堆底的值
        arr.swapAt(0, heapSize-1)
        heapSize -= 1
        //维护剩余元素的最大堆性质
        heapify(arr: &arr, i: 1, heapSize: heapSize)
    }
    
}

//创建最大堆
func buildMaxHeap(arr: inout [Int],heapSize: Int){
    var i = arr.count/2
    while i>0 {
        heapify(arr: &arr, i: i,heapSize: heapSize)
        i-=1
    }
}

func heapify(arr: inout [Int],i: Int,heapSize: Int){
//    for i in 1...arr.count{
        let l = 2*i
        let r = 2*i + 1
        var lagest: Int
        //比较父节点和左孩子
        if(l <= heapSize && arr[l-1] > arr[i-1]) {
            lagest = l
        }else{
            lagest = i
        }
        //比较最大值和右孩子
        if r <= heapSize && arr[r-1] > arr[lagest-1]{
            lagest = r
        }
        if i != lagest {
            //如果交换了值那么父节点就有可能不符合最大堆的性质,需要维护其最大堆的性质
          arr.swapAt(i-1, lagest-1)
          heapify(arr: &arr, i: lagest,heapSize: heapSize)
        }
}

至此排序算法的学习告一小段落,全部的代码放在了SORTLEARNING
文章并没有什么教学意义,因为都是引用,代码也没有什么参考价值,只是自己敲出来,能够加深理解和印象.