<filename>tencent/all_sort_algorithm/quick_sort.py
# -*- coding: utf-8 -*-
"""

   File Name：     quick_sort
   Author :       jing
   Date：          2020/3/31
"""


def quick_sort(nums):
    n = len(nums)

    def quick(left, right):
        if left >= right:
            return nums
        pivot = left
        i = left
        j = right
        while i < j:
            while i < j and nums[j] > nums[pivot]:
                j -= 1
            while i < j and nums[i] <= nums[pivot]:
                i += 1
            nums[i], nums[j] = nums[j], nums[i]
        nums[pivot], nums[j] = nums[j], nums[pivot]
        quick(left, j - 1)
        quick(j + 1, right)
        return nums

    return quick(0, n - 1)


print(quick_sort([3,2,3,1,2,4,5,5,6]))
