排序算法一之快排、归并、堆排(swift 实现)

1.快排

思想
快排选取一个作为基准，把小的数放到基准数的左边，把大的数放到基准数的右边。再以基准数左边、右边分别进行快排。
快排更像树的前序遍历
源码

func quick(arr: inout [Int]) {
    quickSortArray(array: &arr, left: 0, right: arr.count-1)
}

func quickSortArray(array:inout [Int],left:Int,right:Int) {
        if left >= right {
            return
        }
        
        var l = left,r = right
        let key = array[left]
        while l < r {
            while l < r && key<=array[r] {
                r -= 1
            }
            if l < r {
                array[l] = array[r]
            }
            
            while l<r && key>=array[l] {
                l += 1
            }
            if l < r {
                array[r] = array[l]
            }
        }
        array[l] = key
        
        quickSortArray(array: &array, left: left, right: l-1)
        quickSortArray(array: &array, left: l+1, right: right)
    }

时间复杂度
快排在最糟糕得情况下时间复杂度是O(n²),平均的复杂度是O(nlogn)
空间复杂度为o(1)
示例
72,6,57,88,60,42,83,73,48,85
第一趟:选取72为基数
从右查找比72小的数，是48,下标是8。结果:48,6,57,88,60,42,83,73,48,85
从左查找比72大的数，是88,下标是3。结果:48,6,57,88,60,42,83,73,88,85
从7开始查找比72小的数,是42,下标是5。结果:48,6,57,42,60,42,83,73,88,85
从3开始查找比72大的数,没有了。用72填充到下标是5的数:48,6,57,42,60,72,83,73,88,85

2.归并

思想
归并是先把数拆成单个再进行合并，有点像树的后序遍历。
源码

func merge(arr: inout [Int]) {
        var temp = Array.init(repeating: 0, count: arr.count)
        mergeSort(arr: &arr, left: 0, right: arr.count-1,temp:&temp)
        print("排序结果:\(arr)")
    }
    
    func mergeSort(arr:inout [Int],left:Int,right:Int,temp:inout [Int]) {
        if left>=right{
            return
        }
        let middle = (right+left)/2
        mergeSort(arr: &arr, left: left, right: middle,temp: &temp)
        mergeSort(arr: &arr, left: middle+1, right: right,temp: &temp)
        mergeTwoArr(arr: &arr, left: left, middle: middle, right: right,temp: &temp)
    }

func mergeTwoArr(arr:inout [Int],left:Int,middle:Int,right:Int,temp:inout [Int]) {
        var i = left
        var j = middle+1
        var t = 0
        while i<=middle && j<=right {
            if arr[i]<=arr[j] {
                temp[t] = arr[i]
                i+=1
            }else{
                temp[t] = arr[j]
                j+=1
            }
            t+=1
        }
        while i<=middle {
            temp[t] = arr[i]
            t+=1;i+=1
        }
        while j<=right {
            temp[t] = arr[j]
            t+=1;j+=1
        }
        
        t = 0
        for j in left...right {
            arr[j] = temp[t]
            t+=1
        }
        
    }

时间复杂度
在最坏、最佳、平均情况下归并排序时间复杂度均为o(nlogn)
归并的空间复杂度为o(n)，需要借助额外的空间

3.堆排

思想:二叉树的应用
关键在于堆的调整，升序需要大顶堆，把小的数往下沉。
先构建大顶堆，再倒叙遍历数组，交换第0个与第i个位置,不断调整大顶堆
源码

func heap(arr: inout [Int]) {
        if arr.count == 0 {
            return
        }
        //构建大顶堆
        for i in (0...arr.count/2).reversed() {
            heapAdjust(array: &arr, parent: i, length: arr.count)
        }
        print("构建堆:\(arr)")

        for j in (1..<arr.count).reversed() {
            ArrayUtil.swap(arr: &arr, i: 0, j: j)
            heapAdjust(array: &arr, parent: 0, length: j)
        }
        print("\(arr)")
    }
    
func heapAdjust(array:inout [Int], parent:Int,length:Int) {
        var parentIndex = parent
        let temp = array[parentIndex]
        var child = 2*parentIndex+1//2n+1:左孩子,2n+2:右孩子
        //把最小的数据放在大于孩子节点的位置
        while child<length {
            //取左右孩子节点的最大节点
            if child+1<length && array[child]<array[child+1]{
                child += 1
            }
            if temp>array[child]{//父节点大于左右孩子节点
                break
            }
            array[parentIndex] = array[child]
            parentIndex = child
            
            child = 2*child+1
        }
        array[parentIndex] = temp
    }

时间复杂度
时间复杂度是O(nlogn)

总结:

排序是基础中的基础，而快排、归并、堆排的思想很重要，要像1+1=2一样熟记于心。
能手搓排序算法，再应用。下章节将举例应用以上排序算法，加深理解

最后编辑于：2020.09.03 09:18:04