Python教程

快速排序(含图片演示+python代码)

本文主要是介绍快速排序(含图片演示+python代码),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

快速排序(含图片演示+python代码)

由于最近在做快排相关的题,因此特地整理了一下,并且配了一些图片演示,一来是为了自己印象深刻,二来也方便大家理解。

基本思想:

1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个基准数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对基准数的左右区间重复第二步,直到各区间只有一个数。

看文字会比较难理解,下面直接上图,大家可以看完图再回过头来理解文字。

第一步,选定基准数
在这里插入图片描述
如图所示,有这样一个无序数组arr,我们选定第一个数,即arr[0]为基准值,我们将arr[0]存入变量base中,我们可以想象在原来arr[0]的位置挖了一个坑:
在这里插入图片描述

第二步,比较过程
①令i=最左边元素索引,j=最右边元素索引。
②从右往左找小于base的元素:将j逐步向左移动,查找第一个小于base的元素。显然,arr[5]<base,因此将arr[5]的值插入原来的坑arr[0]中,这样就在arr[5]上形成了新的坑,由于arr[0]已经更新,因此i没有必要继续指着arr[0]了,所以i+1:
在这里插入图片描述
③从左往右找大于base的元素:将i逐步向右移动,查找第一个大于base的元素。
arr[1]<base,i++
arr[2]<base,i++
arr[3]>base,因此将arr[3]插入原来的坑arr[5]中,这样就在arr[3]上形成了新的坑,由于arr[3]已经更新,因此j没有必要继续指着arr[5]了,所以j-1:
在这里插入图片描述
由于i<j,因此我们继续重复②③,直到i>=j时停止。
重复②:从右往左找小于base的元素:将j逐步向左移动,查找第一个小于base的元素。显然,arr[4]<base,因此将arr[4]插入原来的坑arr[3]中,这样就在arr[4]上形成了新的坑,由于arr[3]已经更新,因此i没有必要继续指着arr[3]了,所以i+1:
在这里插入图片描述
④中止比较:由于此时i>=j,因此比较中止,将base插入到坑arr[4]中,此时可以发现,arr[4]左边都是小于base的元素,右边都是大于base的元素:
在这里插入图片描述
代码如下:

# 输入数组,最左元素索引,最右元素索引
def adjustArr(arr,l,r):
    i = l
    j = r
    # 以最左元素作为比较基准
    x = arr[i]
    while i < j :
        # 从右向左找比x小的数来填arr[i]
        while i < j and arr[j] >= x:
            j = j - 1
        if i < j :
            # 将arr[j]替换arr[i],arr[j]变成新的坑
            arr[i] = arr[j]
            i = i + 1
        # 从左向右找比x大的数来填arr[i]
        while i < j and arr[i] < x:
            i = i + 1
        if i < j :
            # 将arr[i]替换arr[j],arr[i]变成新的坑
            arr[j] = arr[i]
            j = j - 1
    # 退出时,i等于j。将x填到这个坑中。
    arr[i] = x
    
    return i
        

接下来,我们需要把基准值左右两边的数组单独拎出来,再次执行上述①-④的过程。例如,左边数组是[16,56,43,27],我们还是选定16为基准值来进行快排,而右边数组为[95],只有一个元素,不用再排了。这就是分治思想。
分治部分代码如下:

def quickSort(arr,l,r):
    if l < r :
        i = adjustArr(arr,l,r)
        quickSort(arr,l,i-1)
        quickSort(arr,i+1,r)

测试结果:

# 输入待排序数组
arr = [55,23,5,78,13,45,69,80,17]
l = 0
r = len(arr) - 1
quickSort(arr,l,r)
arr

在这里插入图片描述
以上就是快排的全部内容了~~

这篇关于快速排序(含图片演示+python代码)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!