Python学习路线分享实现快速排序算法

　　好程序员Python学习路线分享实现快速排序算法快速排序算法是一种基于交换的高效的排序算法，由C.R.A.Hoare于1962年提出，是一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide and conquer algorithm)。

分治法的基本思想

将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

快速排序的基本思想

  • 先找到一个基准点（一般指数组的中部），然后数组被该基准点分为两部分，依次与该基准点数据比较，如果比它小，放左边；反之，放右边。
  • 左右分别用一个空数组去存储比较后的数据。
  • 最后递归执行上述操作，直到数组长度 <= 1;

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

def quick_sort(lists, left, right):

    '''快速排序'''

    # 跳出递归判断

    if left >= right:

        return lists

 

    # 选择参考点，该调整范围的第1个值

    key = lists[left]

    low = left  

    high = right

 

    # 循环判断直到遍历全部

    while left < right:

        # 从右边开始查找大于参考点的值

        while left < right and lists[right] >= key:

            right -= 1

        lists[left] = lists[right]  # 这个位置的值先挪到左边

 

        # 从左边开始查找小于参考点的值

        while left < right and lists[left] <= key:

            left += 1

        lists[right] = lists[left]  # 这个位置的值挪到右边

 

    # 写回改成的值

    lists[left] = key

 

    # 递归，并返回结果

    quick_sort(lists, low, left - 1)    # 递归左边部分

    quick_sort(lists, left + 1, high)   # 递归右边部分

    return lists

 

numbers = [4, 0, 7, 9, 2, 8, 1, 3, 6, 5]

quick_sort(numbers，0，len(numbers)-1)

assert numbers == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]