快速排序原理及实现

快速排序的步骤：

1. 从数组中选择一个基准数（选择哪一个没有关系，为了方便一般选第一个或者最后一个，也可以随机选择）。
2. 把小于基准数的数移动到基准数左边，大于基准数的数移动到基准数右边，和基准值相同的数可以放到任意一边。此时，基准数左边的所有值都小于右边的任意值。
3. 对于左右两边的子数组，重复以上操作，直到数组有序。

如果可以开辟新数组保存结果，用python可以很快地写出代码。但如果要求不使用额外数组空间、在原地完成排序，应该怎么办呢？（面试、考试一般都要求这样）对于第二步，历史上曾提出过许多种方法，在现在刷题时不同的人也会使用不同的方法。

下面介绍一个比较常见的交换法，仅仅看很难理解其中的原理，自己画图走一遍将会恍然大悟！

1. 选择数组的第一个元素a[0]作为pivot，设置两个指针，i指向最左边的元素a[0]，j指向最右边的元素a[n-1]。
2. 比较a[j]和pivot，当a[j] >= pivot时j指针向左移动一位，直到a[j] < pivot。
3. 将a[j]填到a[i]中
4. 比较a[i]和pivot，当a[i] <= pivot时left指针向右移动一位，直到a[i] > pivot。
5. 将a[i]填到a[j]中
6. 不断重复2、3、4、5步骤
7. 当i指针和j指针重合时，令a[i] = pivot,此时pivot的左边所有元素都小于等于pivot，右边所有元素都大于等于pivot。
8. 对于pivot左边和右边的元素组成的数组，如果长度大于二，则递归进行1到5步。

代码：

def quickSort(nums: list) -> list:
    def sortArray(nums: list, left: int, right: int) -> list:
        i, j = left, right
        if i < j:
            piviot = nums[i]
            while i != j:
                while nums[j] >= piviot and j > i:
                    j -= 1
                nums[i] = nums[j]
                while nums[i] <= piviot and i < j:
                    i += 1
                nums[j] = nums[i]
            nums[i] = piviot
            sortArray(nums, left, i - 1)
            sortArray(nums, i + 1, right)

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