Python 排序算法6：快速排序(2)

qiuyouzhi

Python 排序算法：快速排序(2)

实现快速排序
实现快排有两种方法：
1，双边循环法
2，单边循环法

双边循环法
假设这里有一个列表：

[4, 7, 6, 5, 3, 2, 8, 1]

它的排序结果：

1   left
[4, 7, 6, 5, 3, 2, 8, 1]
6   right
[4, 1, 6, 5, 3, 2, 8, 7]
5   right
[4, 1, 6, 5, 3, 2, 8, 7]
2   left
[4, 1, 6, 5, 3, 2, 8, 7]
4   right
[4, 1, 2, 5, 3, 6, 8, 7]
3   left
[4, 1, 2, 5, 3, 6, 8, 7]
3   right
[4, 1, 2, 3, 5, 6, 8, 7]
1   left
[3, 1, 2, 4, 5, 6, 8, 7]
2   left
[3, 1, 2, 4, 5, 6, 8, 7]
1   left
[2, 1, 3, 4, 5, 6, 8, 7]
6   right
[1, 2, 3, 4, 5, 6, 8, 7]
5   right
[1, 2, 3, 4, 5, 6, 8, 7]
4   right
[1, 2, 3, 4, 5, 6, 8, 7]
6   right
[1, 2, 3, 4, 5, 6, 8, 7]
5   right
[1, 2, 3, 4, 5, 6, 8, 7]
7   left
[1, 2, 3, 4, 5, 6, 8, 7]
[1, 2, 3, 4, 5, 6, 7, 8]

代码：

def quickSort(arr, begin, end):
    if begin > end:
        return None
    pivotIndex = partition(arr, begin, end)
    quickSort(arr, begin, pivotIndex - 1)
    quickSort(arr, pivotIndex + 1, end)

def partition(arr, begin, end):
    pivot = arr[begin]
    left = begin
    right = end

    while left != right:
        while left < right and arr[right] > pivot:
            right -= 1
            print(right, '  right')
            print(arr)
            
        while left < right and arr[left] <= pivot:
            left += 1
            print(left, '  left')
            print(arr)

        if left < right:
            arr[left], arr[right] = arr[right], arr[left]
            #print(arr)

    arr[begin] = arr[left]
    arr[left] = pivot

    return left

array = [4, 7, 6, 5, 3, 2, 8, 1]
quickSort(array, 0, len(array)-1)
print(array)

(这里把print也加了进去，就是为了方便理解)

在下一节，我们会编写出单边循环法的快排！