LeetCode0912.排序数组 Go语言AC笔记

时间复杂度：O(nlog n)

解题思路

快速排序

        随机从left~right索引范围内找一个基准数，将该基准数与下标left的元素交换。接下来从下标right开始，只要right下标的元素值大于基准数，right就左移直至不满足条件，此时将该元素值交换到下标left的位置；然后left向右移动，直至找到一个不小于基准数的元素，然后将该元素值交换到right下标的位置。重复以上过程，直至left与right相遇，此时的下标位置就是数组排序后基准数的位置，返回该下标。

        整体的快速排序函数，还需要先判断left是否小于right，然后根据上述过程找到一个下标，用递归的方法对[left,下标-1]和[下标+1,right]的区间再次进行上述操作，最后的数组就是排序后的数组。

堆排序

        首先建立大根堆，这样堆顶就是待排序部分的最大值，将堆顶元素与待排序部分的最后一个元素交换位置，便完成了一次排序操作。由于交换后不满足大根堆的定义，所以需要重新建堆，直到待排序部分只有一个元素，此时返回排序结果。

        由于是在数组中建堆，按照完全二叉树的性质，根节点的两个孩子在数组中的下标分别是i*2+1和i*2+2（注意数组下标是从0开始），所以可以根据下标快速访问孩子找到根节点与两个孩子三者中的最大值。

AC代码

1 快速排序

1.1 优化版

针对面试手撕

 
func sortArray(nums []int) []int {
    quickSort(nums,0,len(nums)-1)
    return nums
}
 
func quickSort(nums []int,left,right int){
    //一定要判断left和right的大小关系
    if left>=right{
        return
    }
    idx:=partition(nums,left,right)
    quickSort(nums,left,idx-1)
    quickSort(nums,idx+1,right)
}
func partition(nums []int,left,right int)int{
    idx:=left+rand.Intn(right-left)
    nums[left],nums[idx]=nums[idx],nums[left]
    base:=nums[left]
    for left
        for left=base{
            right--
        }
        nums[left]=nums[right]
        for left
            left++
        }
        nums[right]=nums[left]
    }
    nums[left]=base
    return left
}

1.2 针对特殊情况的超级优化版

为了针对力扣五万个2的特殊数据，采用三路快排的思想AC

func sortArray(nums []int) []int {
    quickSort(nums,0,len(nums)-1)
    return nums
}
 
func quickSort(nums []int,left,right int){
    if left>=right{
        return
    }
    index:=partition(nums,left,right)
    less,more:=index,index //less和more是与base相同大小的元素上下限
    for i:=left;i
        if nums[i]==nums[index]{
            less--
            nums[i],nums[less]=nums[less],nums[i]
        }
    }
    for i:=right;i>more;i--{
        if nums[i]==nums[index]{
            more++
            nums[more],nums[i]=nums[i],nums[more]
        }
    }
    quickSort(nums,left,less-1)
    quickSort(nums,more+1,right)
}
 
func partition(nums []int,left,right int)int{
    idx:=left+rand.Intn(right-left)
    nums[left],nums[idx]=nums[idx],nums[left]
    base:=nums[left]
    for left
        for left=base{
            right--
        }
        nums[left]=nums[right]
        for left
            left++
        }
        nums[right]=nums[left]
    }
    nums[left]=base
    return left
}

2 堆排序

func sortArray(nums []int) []int {
    heapSort(nums)
    return nums
}
 
func heapSort(nums []int){
    n:=len(nums)
    //建立大根堆
    for i:=n>>1;i>=0;i--{
        maxHeapify(nums,i)
    }
    //从数组的最后一个元素开始堆排序
    for i:=n-1;i>0;i--{
        nums[0],nums[i]=nums[i],nums[0]  //堆顶是最大值，与待排序部分的最后一个元素交换位置
        maxHeapify(nums[:i],0)  //不满足大根堆要求，重新建堆
    }
}
 
func maxHeapify(nums []int,i int){
    n:=len(nums)
    for (i<<1)+1
        lc,rc:=(i<<1)+1,(i<<1)+2  //左孩子和右孩子在数组中的下标
        large:=i  //根节点和两个孩子三者最大值的下标
        if lcnums[large]{
            large=lc
        }
        if rcnums[large]{
            large=rc
        }
        //如果不是根节点最大，需要交换位置
        if large!=i{
            nums[i],nums[large]=nums[large],nums[i]
            i=large
        }else{
            break
        }
    }
}

感悟

快速排序的思想一直记着，但是每次写起来都是磕磕绊绊，还是不够熟练！

堆排序的建堆操作是从根节点到孩子结点，但是当建立大根堆以及堆排序时是从后向前遍历元素，并且建立大根堆是从数组中间开始向前遍历。