相关概念

    快速排序法 Quicksort 也是一个分治思想的算法.

    对一个子数组 A[p: r] 进行快速排序的三步分治过程:

        1, 分解.  将数组 A[p : r] 被划分为两个子数组(可能为空) A[p : q-1] 和 A[q+1 : r] , 使得 A[p : q-1] 中的每一个元素都小于等于 A[q], 并且 A[q] 小于 A[q+1 : r] 中的每一个元素.

        2, 解决. 通过递归调用快速排序, 对子数组 A[p : q-1] 和 A[q+1 : r] 进行排序.

        3, 合并. 快速排序算法是原址排序, 所以不需要合并操作.

Python programming

    1, 构建算法函数 quick_sort(A,p,r)

        def quick_sort(A, p, r):

            if p < r:

                q = partition(A, p, r)  # 假定分解函数已经实现, 后续给出代码.

                quick_sort(A, p, q-1)

                quick_sort(A, q+1, r)    

        2, 创建分解算法 partition(A,p,r)

        def partition(A, p, r):

            x = A[r]

            i = p - 1

            for j in range(p, r):

                print('Step', j+1)

                print(111, A)

                if A[j] <= x:

                    i += 1

                    print('Index', i,A[i],j,A[j])

                    A[i], A[j] = A[j], A[i]

                    print(222, A)

                print(333, i)

            print(444, A[i+1],A[r])

            A[i+1], A[r] = A[r], A[i+1]

            print(555, A,i+1)

            return i+1

        3, 程序运行

        if __name__ == '__main__':

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

            print('Before : ', A)

            quick_sort(A, 0, 7)

            print('After : ', A)  

结果打印:

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

Step 1

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

    Index 0 2 0 2                           # 将 A[0] 和 A[0] 交换

    222 [2, 8, 7, 1, 3, 5, 6, 4]         # 数组不变

    333 0

Step 2

    111 [2, 8, 7, 1, 3, 5, 6, 4]         # A[1] = 8 > x = 4, 不发生交换操作

    333 0

Step 3

    111 [2, 8, 7, 1, 3, 5, 6, 4]          # A[2] = 7 > x = 4, 不发生交换操作

    333 0

Step 4

    111 [2, 8, 7, 1, 3, 5, 6, 4]           # A[3] = 1 < x = 4, 发生交换操作

    Index 1 8 3 1                             # A[1]  和 A[3] 交换

    222 [2, 1, 7, 8, 3, 5, 6, 4]           # 数组中的 8 和 1 发生交换

    333 1

Step 5

    111 [2, 1, 7, 8, 3, 5, 6, 4]           # A[4] = 3 < x = 4, 发生交换操作

    Index 2 7 4 3                             # A[2]  和 A[4] 交换

    222 [2, 1, 3, 8, 7, 5, 6, 4]           # 数组中的 7 和 3 发生交换

    333 2

Step 6

    111 [2, 1, 3, 8, 7, 5, 6, 4]           # A[5] = 5 > x = 4, 不发生交换操作

    333 2

Step 7

    111 [2, 1, 3, 8, 7, 5, 6, 4]           # A[6] = 6 > x = 4, 不发生交换操作

    333 2                                        # 最后 i = 2, 即 q 的值. 由于python 数组是 0 base 的, 为了递归调用的对齐, 返回 q = 2+1 = 3 (注: 对齐方法保持统一就可以)

444 8 4

555 [2, 1, 3, 4, 7, 5, 6, 8] 3            # 将 A[3 = 2+1 ] 和 x = A[7] 交换

# 得出 q 值后, 后续通过递归调用处理子数组 A[0, q-1] 和 A[q+1, 7]

Step 1

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

Index 0 2 0 2

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

333 0

Step 2

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

Index 1 1 1 1

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

333 1

444 3 3

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

Step 1

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

333 -1

444 2 1

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

Step 5

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

Index 4 7 4 7

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

333 4

Step 6

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

Index 5 5 5 5

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

333 5

Step 7

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

Index 6 6 6 6

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

333 6

444 8 8

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

Step 5

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

333 3

Step 6

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

Index 4 7 5 5

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

333 4

444 7 6

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

After :  [1, 2, 3, 4, 5, 6, 7, 8]       # 完成快速排序. 快速排序算法是原址排序.