快速排序（含图片演示+python代码）

概述快速排序（含图片演示+python代码）由于最近在做快排相关的题，因此特地整理了一下，并且配了一些图片演示，一来是为了自己印象深刻，二来也方便大家理解。基本思想：1．先从数列中取出一个数作为基准数。2．分区过程，将比这个基准数大的数全放到它的右边，小于或等于它的数全放到它的左边。 快速排序（含图片演示+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 = 0r = len(arr) - 1quickSort(arr,l,r)arr

以上就是快排的全部内容了~~

总结

以上是内存溢出为你收集整理的快速排序（含图片演示+python代码）全部内容，希望文章能够帮你解决快速排序（含图片演示+python代码）所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。