912. 排序数组

Link

力扣

Problem

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

• 1 <= nums.length <= 5 * 104

• -5 * 104 <= nums[i] <= 5 * 104

Solution

快速排序

Go

func sortArray(nums []int) []int {
    rand.Seed(time.Now().Unix())
    qsort(nums, 0, len(nums)-1)
    return nums
}

func qsort(nums []int, l, r int){
    if l >= r {
        return 
    }
    index := randomPartition(nums, l, r)
    qsort(nums, l, index-1)
    qsort(nums, index+1, r)
}

func randomPartition(nums []int, l, r int) int {
    i := rand.Intn(r-l+1)+l 
    nums[i], nums[r] = nums[r], nums[i]
    return partition(nums, l, r)
}

func partition(nums []int, l, r int) int {
    x := nums[r]
    index := l
    for i := l; i < r; i++ {
        if nums[i] < x {
            nums[index], nums[i] = nums[i], nums[index]
            index++
        }
    } 
    nums[index], nums[r] = nums[r], nums[index]
    return index
}

C++

归并排序

Go

func sortArray(nums []int) []int {
    mergeSort(nums, 0, len(nums)-1)
    return nums
}

func mergeSort(nums []int, l, r int) {
    if l>=r {
        return
    }
    mid := l + (r-l)>>1
    mergeSort(nums, l, mid)
    mergeSort(nums, mid+1, r)

    //剪枝
    if nums[mid+1] > nums[mid] {
        return
    }
    //归并
    i, j := l, mid+1
    tmp := make([]int, r-l+1)
    for pos := range tmp {
        if j>r || (i<=mid && nums[i] < nums[j]) {
            tmp[pos] = nums[i]
            i++
        }else{
            tmp[pos] = nums[j]
            j++
        }
    }
    copy(nums[l:r+1], tmp)
}

堆排序

Go

func sortArray(nums []int) []int {
    heapsort(nums)
    return nums
}

func heapsort(nums []int){
    end := len(nums) - 1
    for i:=end>>1; i>=0; i--{
        sink(nums, i, end)
    }
    for i:=end; i>=0; i--{
        nums[0], nums[i] = nums[i], nums[0]
        end--
        sink(nums, 0, end)
    }
}

func sink(heap []int, root, end int){
    for{
        child := root*2 + 1
        if child>end{
            return
        }
        if child<end && heap[child] <= heap[child+1]{
            child++
        }
        if heap[root] > heap[child]{
            return
        }
        heap[root], heap[child] = heap[child], heap[root]
        root = child
    }
}