快速排序（含图片演示+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

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