leetcode-912-Sort-an-Array

发表于   |  

TODO

描述

Given an array of integers nums, sort the array in ascending order.

Example 1:

1
2
Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:

1
2
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Constraints:

  • 1 <= nums.length <= 5 * 104
  • -5 * 104 <= nums[i] <= 5 * 104

分析

面试必考…可以总结一下各种排序方法。

解决方案1(Python)

快速排序

会超时

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) <= 1:
            return nums
        less, greater, base = [], [], nums.pop()
        for i in nums:
            if i < base:
                less.append(i)
            else:
                greater.append(i)
        return self.sortArray(less) + [base] + self.sortArray(greater)

冒泡排序

会超时。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        numsLen = len(nums)
        if numsLen < 2:
            return nums
        
        for i in range(numsLen):
            for j in range(numsLen-i-1):
                if nums[j] > nums[j+1]:
                    nums[j], nums[j+1] = nums[j+1], nums[j]
        return nums

选择排序

会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        numsLen = len(nums)
        
        if numsLen < 2:
            return nums
        
        for i in range(numsLen-1):
            smallest = nums[i]
            position = i
            for j in range(i, numsLen):
                if nums[j] < smallest:
                    smallest = nums[j]
                    position = j
            if i != position:
                nums[i], nums[position] = nums[position], nums[i]
        
        return nums

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        numsLen = len(nums)
        
        if numsLen < 2:
            return nums
        
        for i in range(1, numsLen):
            key = nums[i]
            j = i - 1
            while j >= 0 and nums[j] > key:
                nums[j+1] = nums[j]
                j -= 1
            nums[j+1] = key
        
        return nums

解决方案2(Golang)

快速排序

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
func quickSort(arr []int, left, right int) []int {
    if len(arr) <= 1 {
        return arr
    }
    
    partition := func(arr []int, left, right int) int {
        pivot := arr[left]
        slow := left
        for quick := left+1; quick <= right; quick++ {
            if arr[quick] < pivot {
                slow++
                arr[quick], arr[slow] = arr[slow], arr[quick]
            }
        }
        arr[slow], arr[left] = arr[left], arr[slow]
        return slow
    }
    
    if left < right {
        pivot := partition(arr, left, right)
        quickSort(arr, left, pivot-1)
        quickSort(arr, pivot+1, right)
    }
    return arr
}

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

题目来源