快速排序

快速排序是一个非常高效的排序算法，目前的应用非常广泛， 同时也是面试的常客。学好快速排序，能够对找到工作有很大的帮助。同时，也有很多面试题也会用到这种思想。

快速排序也是一种分治的思想，但是它于归并算法更加好是因为归并算法会用到辅助数组，其空间复杂度是O(n). 而快速排序不需要用到新的数组空间，它的空间复杂度是O(1).

快速排序的核心是：选定一个值作为轴心值，然后将数组分成两个部分，一部分是大于这个轴心值，另一部分是小于这个轴心值的。然后将这个轴心值前的部分继续使用快速排序，将这个轴心值的后半部分继续使用快速排序。直到指剩下了一个元素的时候是不需要交换的。快速排序非常适用于大数据量的排序，因为它既不占用多余的空间，又能达到时间复杂度是O(nlogn).

下面，快速排序的步骤：

image

第一步：选择最大的index作为轴心

第二步：选择两个指分别指向最左边左边和除了轴心的最右边。

第三步：两个指针分别是left和right。左边的只想低索引。右边的指向高索引。

第四步：当左边的索引的值小于轴心，那就向右移动索引。

第五步：当右边的索引的值大于轴心，那就向左移动索引。

第六步：当第四步和第五步都不符合时，交换彼此。

第七步：如果 left >= right, 那么left就是新的轴心的位置，将轴心与之交换。

代码示例

def QuickSort(array, left=0, right=None):
    arrayLen = len(array)
    if arrayLen <= 1:
        return array
    if right == None:
        right = arrayLen - 1
    if left < right:
        pivot = partition(array, left, right)
        QuickSort(array, left, pivot - 1)
        QuickSort(array, pivot + 1, right)

def partition(array, left, right):
    pivotValue = array[right]
    i = left
    j = right - 1
    while i < j:
        while j > left and array[j] > pivotValue:
            j -= 1
        while i < right and array[i] <= pivotValue:
            i += 1
        if i < j:
            array[i], array[j] = array[j], array[i]
            i += 1
            j -= 1
    if array[i] > array[right]:
        array[i], array[right] = array[right], array[i]
    return i

if __name__ == '__main__':
    testList = [2, 7, 6, 1, 5, 4, 9, 3]
    QuickSort(testList)
    print(testList)

另一种实现方式理解会有偏差，所以给出大家下面参考，如果能理解下面的代码，请使用下面的方式编写快速排序：

image.png

1.选取一个数字作为基准，可选取末位数字

2.将数列第一位开始，依次与此数字比较，如果小于此数，将小数交换到左边，最后达到小于基准数的在左边，大于基准数的在右边，分为两个数组

3.分别对两个数组重复上述步骤

代码示例

def QuickSort(array, left=0, right=None):
    arrayLen = len(array)
    if arrayLen <= 1:
        return array
    if right == None:
        right = arrayLen - 1
    if left < right:
        pivot = partition(array, left, right)
        QuickSort(array, left, pivot - 1)
        QuickSort(array, pivot + 1, right)

def partition(array,left,right):
    i = left-1
    for j in range(left,right):
        if array[j] <= array[right]:
            i += 1
            array[j],array[i] = array[i],array[j]
    array[i+1],array[right] = array[right],array[i+1]
    return i+1

if __name__ == '__main__':
    testList = [2, 7, 6, 1, 5, 4, 9, 3]
    QuickSort(testList)
    print(testList)