快速排序算法

快速排序的算法的核心思想是选取一个中间值，将整个数组分为两个部分一个比这个一半比这个中间值大，一半比这中间值小。之后将数组从这个中间值中分成两部分，采用分治的方式将左边的一半排序，再将右边的一半排序。这里一个技巧性就是如何遍历数组，以及如何交换。

这里有个非常有技巧性的东西，就是将中间值取出来，并且用它空出来的空位来进行交换。

def quickSort2(nums, start, end):
    if (start >= end):
        return
    low, hight = start, end
    p = nums[start]
    while(start < end):
        while(start < end and p <= nums[end]):
            end -= 1
        nums[start] = nums[end]
        while(start < end and p >= nums[start]):
            start += 1
        nums[end] = nums[start]

    nums[start] = p
    quickSort2(nums, low, start-1)
    quickSort2(nums, start+1, hight)

但是快速排序的算法有一个问题就是算法的稳定性不好

最好情况下的算法复杂度是

最坏的情况下是