快速排序-递归/分治法(C/Java/Python)(2021/3/21更新)

算法目录

2021/3/21更新：代码打错了...还缺了等号...补上了...等后面我多做一点排序题，再来更新点有用的。

算法介绍

快速排序是一种排序算法，时间复杂度为O(N*logN)。

算法思想

1. 选择参考点。
2. 比参考点大的数放参考点右边，小的则放左边。
3. 以参考点为边界，再对两边进行快速排序

步骤过程

本文章介绍的是使用递归的，参考点取左边界的快速排序。
后续我会写个用栈实现的非递归，一定会写，一定。一定。
然后会把分类和标签再加上数据结构。

一次排序的搜索过程，是左右边界的两个指针，向中间移动，
一旦两个指针指向同一个地方，那么本次排序就结束了，参考点的位置就标定了，
可以看下面的示例，第一次排序结束后，参考值3就找到所在位置。

在排序的过程中，
先将参考点与右指针比较，如果是正序的，就将右指针左移，
如果出现逆序，即参考值>右指针，那么将此时的左指针的值设置为右指针的值，
然后对比左指针，正序跳过，直到逆序，
将右指针的值设置成做指针的值，
之后比较右指针、左指针、右指针...

这里不是很好理解，为什么比对参考点与右指针比较，却修改了左指针的值，
拿张草稿纸出来动手试一下，会更容易记一点，
或者看下面的示例。

排序示例

arr表示array[]数组，为待分配数组，
r表示compareRight，为比较用的右指针，
l表示compareLeft，为比较用的左指针，
sta表示standard，为参考点的值。

待排序数组

第一次排序
（左侧数组为右侧代码执行后结果）

第二次排序
对第一次排序结果的左边排序

第三次排序
对第一次排序结果的右边排序

排序后数组

C版本代码

void quickSoft(int *array, int left, int right){
    if (left>right) return;       
    int compareLeft = left;
    int compareRight = right;
    int standard = array[compareLeft];
    while(compareLeft<compareRight){
        while(compareLeft<compareRight && standard<=array[compareRight]) 
            compareRight -= 1;
        if(compareLeft<compareRight)
            array[compareLeft] = array[compareRight];
        while(compareLeft<compareRight && standard>=array[compareLeft])
            compareLeft += 1;
        if(compareLeft<compareRight)
            array[compareRight] = array[compareLeft];
    }
    array[compareLeft] = standard;
    quickSoft(array, left, compareLeft-1);
    quickSoft(array, compareLeft+1, right);
}

Java版本代码

static int getStandard(int []array, int leftPos, int rightPos){
        int standard = array[leftPos];
        while(leftPos<rightPos){
            while(leftPos<rightPos && standard<=array[rightPos])
                rightPos -= 1;
            if(leftPos<rightPos)
                array[leftPos] = array[rightPos];
            while(leftPos<rightPos && standard>=array[leftPos])
                leftPos += 1;
            if(leftPos<rightPos)
                array[rightPos] = array[leftPos];
        }
        array[leftPos] = standard;
        return leftPos;
    }

    static void quickSoft(int []array, int leftPos, int rightPos){
        if(leftPos<rightPos){
            int standardPos = getStandard(array, leftPos, rightPos);
            quickSoft(array, leftPos, standardPos-1);
            quickSoft(array, standardPos+1, rightPos);
        }
    }

Python版本代码

def quickSoft(array, left, right):
    if left>right:
        return
    compareLeft = left
    compareRight = right
    standard = array[compareLeft]
    while compareLeft<compareRight:
        while compareLeft<compareRight and standard<=array[compareRight]:
            compareRight -= 1
        if compareLeft<compareRight:
            array[compareLeft] = array[compareRight]
        while compareLeft<compareRight and standard>=array[compareLeft]:
            compareLeft += 1
        if compareLeft<compareRight:
            array[compareRight] = array[compareLeft]
    array[compareLeft] = standard
    quickSoft(array, left, compareLeft-1)
    quickSoft(array, compareLeft+1, right)