01.快排

1.1 快排-递归实现

**注：**快排代码实现（类似于二叉树 递归调用）----右手左手一个慢动作，左手右手一个慢动作重播

  • 空间复杂度 O(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
#!/usr/bin/env python
# -*- coding:utf-8 -*-
import random
import sys
sys.setrecursionlimit(10000000)             #设置系统最大递归深度

def quick_sort(data, left, right):
    if left < right:
        mid = partition(data, left, right)    # mid返回的是上一个用来排序那个数的下标
        quick_sort(data, left, mid - 1)
        quick_sort(data, mid + 1,right)

# 每执行一次partition函数都可以实现将某个数左边都比这个数小右边都比这个数大
def partition(data, left, right):
    tmp = data[left]
    while left < right:
        while left < right and data[right] >= tmp:     # 从右向左找小于tmp的数放到左边空位置
            right -= 1
        data[left] = data[right]                       # 将右边小于tmp值得数放到左边空位置
        while left < right and data[left] <= tmp:      # 从左向右找到大于tmp的值放到右边空位置
            left += 1
        data[right] = data[left]                       # 将右边大于tmp值得数放到右边空位置
    data[left] = tmp
    return left

data = list(range(100))
random.shuffle(data)                                 #将有序列表打乱
quick_sort(data, 0, len(data) - 1)
print(data)

1.2 快排-简单实现

  • 空间复杂度高（O(N)）：需要开辟新的列表存储
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#! /usr/bin/env python
# -*- coding: utf-8 -*-
def quick(list):
    if len(list) < 2:
        return list

    tmp = list[0]  # 临时变量 可以取随机值
    left = [x for x in list[1:] if x <= tmp]  # 左列表
    right = [x for x in list[1:] if x > tmp]  # 右列表
    return quick(left) + [tmp] + quick(right)

li = [4,3,7,5,8,2]
print quick(li)  # [2, 3, 4, 5, 7, 8]

#### 对[4,3,7,5,8,2]排序
'''
[3, 2] + [4] + [7, 5, 8]                 # tmp = [4]
[2] + [3] + [4] + [7, 5, 8]              # tmp = [3] 此时对[3, 2]这个列表进行排序
[2] + [3] + [4] + [5] + [7] + [8]        # tmp = [7] 此时对[7, 5, 8]这个列表进行排序
'''

实现方式2

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

"""
   nums, 0, len(nums)-1

  要使nums在 0到 len(nums)-1有序，先找一个分界点p， 使得nums[0:p-1]都小于等于num[p]
                                               使得nums[p:len(num)-1]大于nums[p]
  这就是一个前序遍历
"""


def sort(sums: list, left, right):
    if left >= right:
        return
    p = partition(sums, left, right)
    sort(sums, left, p - 1)
    sort(sums, p + 1, right)


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


if __name__ == '__main__':
    nums = [10, 2, 1, 3, 4, 5, 6, 7]
    sort(nums, 0, len(nums) - 1)
    print(nums)

__END__