leetcode-912 排序数组

留言

912. 排序数组

难度: 中等



非常简单,排序,且没有要求时间复杂度,可以有10+种写法…

祭出快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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

func quicksort(nums []int, lo,hi int) {
    if lo >= hi {
        return
    }
    p := partition(nums,lo,hi)
    quicksort(nums,lo,p-1)
    quicksort(nums,p+1,hi)
}

func partition(nums []int,lo,hi int) int {
    pivot := nums[hi]
    i := lo-1
    for j:=lo;j<hi;j++ {

        //一进循环就是一个判断,不满足直接下一次循环
        if nums[j] < pivot  { //满足的条件是当前元素的值要小于枢轴值
            i++
            nums[i],nums[j] = nums[j],nums[i]
        }
    }
    //注意,这个swap是在循环之外!
    nums[i+1],nums[hi] = nums[hi],nums[i+1]
    return i+1
}

文章目录