5.【排序】快速排序递归与非递归

描述：
题目链接：https://leetcode-cn.com/problems/sort-an-array/
给定一个整数数组 nums，将该数组升序排列。

示例 1：
输入：[5,2,3,1]
输出：[1,2,3,5]

示例 2：
输入：[5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

1 <= A.length <= 10000
-50000 <= A[i] <= 50000

• 递归：

class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if nums == None or len(nums) == 0:
            return None
        left = 0
        right = len(nums) - 1
        self.quicksort(left, right, nums)
        return nums
    def quicksort(self, left, right, nums):
        if left >= right:
            return 
        low = left
        high = right
        key = nums[left]
        while left < right:
            while left < right and nums[right] >= key:
                right -= 1
            nums[left] = nums[right]
            while left < right and nums[left] <= key:
                left += 1
            nums[right] = nums[left]
        nums[left] = key
        self.quicksort(low, left - 1, nums)
        self.quicksort(right + 1, high, nums)

• 非递归：

class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # 辅助函数
        def pritation(left, right, nums):
            if left >= right:
                return -1
            key = nums[left]
            while left < right:
                while left < right and nums[right] >= key:
                    right -= 1
                nums[left] = nums[right]
                while left < right and nums[left] <= key:
                    left += 1
                nums[right] = nums[left]
            nums[left] = key
            return left
        
        if nums == None or len(nums) == 0:
            return None
        stack = []
        left = 0
        right = len(nums) - 1
        stack.append(right)
        stack.append(left)
        while len(stack) > 0:
            left = stack.pop()
            right = stack.pop()
            if left < right:
                k = pritation(left, right, nums)
                if k > left and k != -1:
                    stack.append(k - 1)
                    stack.append(left)
                if k < right and k != -1:
                    stack.append(right)
                    stack.append(k + 1)
        return nums