Py008-01-06快速排序

快速排序

第一个实现方式

非原地排序，非常费空间

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
import math
# 非原地排序  每次都把列表分为左右两个区间
def quickSort(arr):
    if len(arr) <= 1: return arr

    # 取中间位
    pivotIndex = math.ceil(len(arr) / 2);
    pivot = arr[pivotIndex];
    del arr[pivotIndex];

    # 左右区间，用于存放排序后的数
    left = [];
    right = [];
    for i in range(len(arr)):
        print('分区操作的第 ' + str(i + 1) + ' 次循环：');
        # 小于基准，放于左区间，大于基准，放于右区间
        if arr[i] < pivot:
            left.append(arr[i]);
            print('左边：' + str(arr[i]))
        else:
            right.append(arr[i]);
            print('右边：' + str(arr[i]))
    print(left, right)
    return quickSort(left) + [pivot] + quickSort(right)


arr = [14, 3, 15, 7, 2, 76, 11];
print(quickSort(arr));

原地排序

  • 以第一个值为起点 li[0]
  • 从右开始找 li[len(li)-1] 比 li[0] 小则交换，索引往左移动一位。
  • 然后从左往右找 比li[0]大 则交换，索引往右移动一位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def partition(li,left,right):
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp: # 从右面找比tmp小的数
            right -= 1 # 往左走一步
            print(li,'right')
        li[left] = li[right] # 把右边的值填到左边的空位上

        while left < right and li[left] <= tmp: # 从左面找比tmp大的数
            left += 1 # 往右走一步
            print(li,'left')
        li[right] = li[left] # 把左边的值填到右边的空位上

    li[left] = tmp # 把tmp归位
    return left # 返回中间值

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

print(li)
partition(li,0,len(li)-1)
print(li)

第二步，递归的方式来排序左面的和右边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def partition(li,left,right):
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp: # 从右面找比tmp小的数
            right -= 1 # 往左走一步
        li[left] = li[right] # 把右边的值填到左边的空位上

        while left < right and li[left] <= tmp: # 从左面找比tmp大的数
            left += 1 # 往右走一步
        li[right] = li[left] # 把左边的值填到右边的空位上

    li[left] = tmp # 把tmp归位
    return left # 返回中间值

def quick_sort(li,left,right):
    if left<right :# 至少两个元素
        mid = partition(li,left,right)
        quick_sort(li,left,mid-1)
        quick_sort(li,mid+1,right)

li = [5,7,4,6,3,1,2,9,8]
quick_sort(li,0,len(li)-1)
print(li)

快速排序的效率

  • 时间复杂度 O(n*log n)

快排的问题

  • 递归 (python有个递归层数的问题默认1000)
  • 最坏情况

什么是最坏情况

  • 当列表是 倒序排列的时候 [9,8,7,6,5,4,3,2,1]
1
基本和冒泡一样了

解决方案就是随机一个数字,而不是固定取第一位

  • 随机快排