---

title: 排序数组(快速排序)
date: 2020-03-31 10:15:12
tags: [排序]

categories: LeetCode

题目描述

给你一个整数数组 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]

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

快速排序，将第一个数作为基准，左边设一个指针，右边一个指针。
右边指针与基准相比，如果大，则指针向前移动。也就是保证，大于基准的数都在基准右侧。
如果小，则将值赋值给当前左指针（第一次是基准）的位置。右指针停止，左指针与基准比较，小于或等于，向后移动，大于的话，将左指针的值给到上一次停止的右指针的位置。
最后当左指针与右指针相等时，一次遍历完成。并且该位置就是基准的位置。
以基准位置为界，分成两部分重新进行排序

代码

Code

class Solution:
    冒泡排序
    def sortArray(self, nums: List[int]) -> List[int]:
        if not nums:
            return nums
        tmp = 0
        for i in range(len(nums)):
            change = False
            for j in range(len(nums)-i-1):
                if nums[j] > nums[j+1]:
                    nums[j], nums[j+1] = nums[j+1], nums[j]
                    change = True
            if not change:
                break
        return nums
    快速排序
    def sortArray(self, nums: List[int]) -> List[int]:
        
        def Quick(nums, left, right):
            lo = left
            hi = right
            if lo >= hi:
                return nums
            tmp = nums[lo]
            while lo < hi:
                while lo < hi and tmp <= nums[hi]:
                    hi -= 1
                nums[lo] = nums[hi]
                while lo < hi and tmp >= nums[lo]:
                    lo +=1
                nums[hi] = nums[lo]
            
            nums[lo] = tmp
            Quick(nums, left, hi-1)
            Quick(nums, hi+1, right)
            return nums
        

        return Quick(nums,0,len(nums)-1)