排序数组

🎯 问题描述（来源于LeetCode）

描述：
给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
说明：

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

示例：

示例 1：

1
2
3

输入：nums = [5,2,3,1]
输出：[1,2,3,5]
解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。

示例 2：

1
2
3

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
解释：请注意，nums 的值不一定唯一。

💻 解题思路

思路1：希尔排序

思路1：代码实现

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        size=len(nums)
        gap=size // 2
        while gap>0:
            for i in range(gap,size):
                temp=nums[i]
                j=i
                while j>=gap and nums[j-gap]>temp:
                    nums[j]=nums[j-gap]
                    j-=gap
                nums[j]=temp
            gap//=2
        return nums

思路1：📊 性能分析

提交结果

运行时间：635ms击败39.21%
内存消耗：23.51MB击败92.42%

复杂度验证

时间复杂度： $O(n^2)$
空间复杂度： $O(1)$

思路2：归并排序

思路2：代码实现

class Solution:
    def merge(self,left_nums:[int],right_nums:[int]):
        nums=[]
        left_i=right_i=0
        while left_i<len(left_nums)and right_i<len(right_nums):
            if left_nums[left_i]<right_nums[right_i]:
                nums.append(left_nums[left_i])
                left_i+=1
            else:
                nums.append(right_nums[right_i])
                right_i+=1
        while left_i<len(left_nums):
            nums.append(left_nums[left_i])
            left_i+=1
        while right_i<len(right_nums):
            nums.append(right_nums[right_i])
            right_i+=1
        return nums
    def mergesort(self,nums:[int])->[int]:
        if len(nums)<=1:
            return nums
        mid=len(nums)//2
        left_nums=self.mergesort(nums[0:mid])
        right_nums=self.mergesort(nums[mid:])
        return self.merge(left_nums,right_nums)
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.mergesort(nums)

        return nums

思路2：📊 性能分析

提交结果

运行时间：771ms击败19.44%
内存消耗：25.03MB击败43.20%

复杂度验证

时间复杂度： $O(Nlogn)$
空间复杂度： $O(N)$

思路3：快速排序

思路3：代码实现

import random
class Solution:
    def randomPartition(self,nums:[int],low:int,high:int)->int:
        i=random.randint(low,high)
        nums[low],nums[i]=nums[i],nums[low]
        return self.partition(nums,low,high)
    def partition(self,nums:[int],low:int,high:int)->int:
        pivot=nums[low]
        i,j=low,high
        while i<j:
            while i<j and nums[j]>=pivot:
                j-=1
            while i<j and nums[i]<=pivot:
                i+=1
            nums[i],nums[j]=nums[j],nums[i]
        nums[low],nums[j]=nums[j],nums[low]
        return i
    def quicksort(self,nums:[int],low:int,high:int)->[int]:
        if low <high:
            pivot_i=self.randomPartition(nums,low,high)
            self.quicksort(nums,low,pivot_i-1)
            self.quicksort(nums,pivot_i+1,high)
        return nums
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.quicksort(nums,0,len(nums)-1)