面试必备排序算法 - 快速排序

本贴最后更新于 1068 天前,其中的信息可能已经渤澥桑田

简介

快速排序(Quicksort)是对冒泡排序的一种改进。

快速排序由C.A.R.Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,一次达到整个数据变成有序序列。

算法原理

设要排序的数组是A[0],A[1]......A[n-1],首先取任意一个数据(通常选用数组的第一个)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,整个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的算法是:

  1. 设置两个变量left, right用来表示数组元素索引,排序开始的时候:left=0, right=n-1
  2. 以第一元素作为关键数据,赋值给key,即key=A[0]
  3. right开始向前搜索,即由后开始向前搜索(right--),找到第一个小于key的值A[right],将A[right]A[left]互换
  4. left开始向后搜索,即由前开始向后搜索(left++), 找到第一个大于keyA[left], 将A[left]A[right]互换;
  5. 重复第3,4步,直到left=right,注意判断和搜索是同时进行的,也即是每次改变left, right都要进行判断

排序演示

快排图

假设用户输入了如下数组:

索引 0 1 2 3 4 5
数据 6 2 7 3 8 9

创建变量left=0(指向第一个数据),right=5(指向最后一个数据),k=6(赋值为第一个数据的值)。

要把所有比k小的数移到k的左面,开始寻找比6小的数,从right开始,从右往左找,不断递减变量right的值,找到第一个索引3的数据比6小,于是把数据3移到下标0的位置,把索引为0的数据6移到下标3的位置,完成第一次比较,结果如下:

索引 0 1 2 3 4 5
数据 3 2 7 6 8 9

此时,left=0, right=3 k=6

开始进行第二次比较,这次从左边开始找。递增变量left,发现索引2的数据是一个比k大的,于是用索引2的数据7和right指向的下标3的数据6做交换,结果如下:

索引 0 1 2 3 4 5
数据 3 2 6 7 8 9

此时,left=2, right=3, k=6

称上面两次比较为一个循环。

接着,再递减变量right, 不断重复进行上面的循环比较。

在本例中,进行一次循环,就发现leftright碰头了:他们都指向了下标2。于是第一遍比较结束。凡是k(=6)的左边的数都比它小,凡是右边的数都比它大。

如果leftright没有碰头的话,就递增left找大的,还没有,就再递增right找小的,如此反复,不断循环,注意判断和寻找是同时进行的。然后,对k两边数据,再分组分别进行上述过程,直到不能再分为止。

注意:第一遍快速排序不会直接得到最终结果,只会把比k大和比k小的数分到k的两边。

python代码实现

实现上面的过程

#!/usr/bin/python  
# -*- coding: utf-8 -*-  

l = [6, 2, 7, 3, 8, 9]
left = 0
right = 5
key = l[0]
#  从右边找起找到比key小的值,然后与l[key]互换
while left < right and l[right] >= key:
    right -= 1

l[right], l[left] = l[left], l[right]

print('第一次从右往左交换:')
print('left=%s' % left, 'right=%s' % right)
print(l)

#  从左边找到比key大的值,然后与l[right]互换
while left < right and l[left] < key:
    left += 1

l[left], l[right] = l[right], l[left]

print('第一次从左往右交换:')
print('left=%s' % left, 'right=%s' % right)
print(l)

运行结果:

第一次从右往左交换
('left=0', 'right=3')
[3, 2, 7, 6, 8, 9]
第一次从左往右交换
('left=2', 'right=3')
[3, 2, 6, 7, 8, 9]

因为我们已知了数列,我们需要对上述代码做个归纳来适应任何数列,归纳代码如下:

def f(l):
    left = 0
    right = len(l) - 1
    key = l[0]

    while left < right:
   
        while left < right and l[right] >= key:  # 从右向左比较
            right -= 1
        l[right], l[left] = l[left], l[right]


        while left < right and l[left] < key:  # 从左向右比较
            left += 1
  
        l[left], l[right] = l[right], l[left]


l = [6, 2, 7, 3, 8, 9]

f(l)
print(l)

执行结果:

[3, 2, 6, 7, 8, 9]

这样我们实现了传入一个任意数列进行一次快速排序的函数,我们继续归纳总结,如果我们只想对一个数列的一部分进行快速排序呢?

这样我们需要指定数列的区间,那么我们将上述函数修改如下:

def f(l, left=None, right=None):
    if left is None:
        left = 0
    if right is None:
        right = len(l) - 1
    key = l[left]
    while left < right:
        while left < right and l[right] >= key:  # 从右向左比较
       right -= 1
        l[right], l[left] = l[left], l[right]


        while left < right and l[left] < key:  # 从左向右比较
            left += 1
        l[left], l[right] = l[right], l[left]

l = [6, 2, 7, 3, 8, 9]
print(l)
f(l, 0, 4)
print(l)

执行结果:

[6, 2, 7, 3, 8, 9]
[3, 2, 6, 7, 8, 9]

我们实现了对任意数列的任意区间的快速排序,那么我们按照快速排序的思想,进行递归就可以解决问题,代码如下:

def f(l, left=None, right=None):
    if left is None:
        left = 0
    if right is None:
        right = len(l) - 1
    if right > left:  # 递归结束的条件
        index_l = left
        index_r = right
        key = l[left]
        while left < right:
            while left < right and l[right] >= key:  # 从右向左比较
                right -= 1
            l[right], l[left] = l[left], l[right]
     
            while left < right and l[left] < key:  # 从左向右比较
                left += 1
            l[left], l[right] = l[right], l[left]

        # 递归
        f(l, left=index_l, right=left-1)  # 左边的一半
        f(l, left=left+1, right=index_r)  # 右边的一半

l = [54, 50, 43, 68, 9, 74, 91, 69, 42, 49, 18, 50, 31, 99, 79, 92, 50, 43, 46, 10, 74, 75, 13, 32, 10, 54, 32, 12, 42, 6, 20, 75, 99, 26, 48, 82, 1, 68, 15, 97, 22, 35, 8, 90, 45, 100, 20, 18, 81, 81, 69, 37, 26, 85, 69, 78, 84, 95, 42, 0, 56, 53, 20, 29, 35, 82, 86, 81, 43, 33, 44, 28, 25, 69, 45, 8, 12, 85, 87, 84, 56, 75, 12, 59, 76, 31, 62, 54, 67, 31, 71, 40, 42, 88, 100, 44, 88, 9, 36, 22]

f(l)
print(l)

执行结果:

[0, 1, 6, 8, 8, 9, 9, 10, 10, 12, 12, 12, 13, 15, 18, 18, 20, 20, 20, 22, 22, 25, 26, 26, 28, 29, 31, 31, 31, 32, 32, 33, 35, 35, 36, 37, 40, 42, 42, 42, 42, 43, 43, 43, 44, 44, 45, 45, 46, 48, 49, 50, 50, 50, 53, 54, 54, 54, 56, 56, 59, 62, 67, 68, 68, 69, 69, 69, 69, 71, 74, 74, 75, 75, 75, 76, 78, 79, 81, 81, 81, 82, 82, 84, 84, 85, 85, 86, 87, 88, 88, 90, 91, 92, 95, 97, 99, 99, 100, 100]

不考虑空间复杂度可以简化代码如下:

def quick_sort(l):
    if len(l) >= 2:  # 递归结束条件
        k = l[0]  # 选取k值
        left, right = [], []  # 定义基准值左右两侧的列表
        l.remove(k)  # 移除基准元素
        for item in l:
            if item < k:
                left.append(item)
            else:
                right.append(item)
        return quick_sort(left) + [k] +quick_sort(right)
    else:
        return l

一行代码可以实现:

打赏 5 积分后可见
5 积分 • 7 打赏
1 操作
877649301 在 2021-04-25 14:59:30 更新了该帖
回帖
请输入回帖内容 ...