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

算法目录

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

算法介绍

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

算法思想

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

步骤过程

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

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

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

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

排序示例

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

待排序数组

34152

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

34152开始排序
24152arr[r]
24152arr[l]
24154arr[l]>sta, arr[r]=arr[l]
24154arr[r]>sta, r--
24154arr[r]>sta, r--
21154arr[r[
21154arr[l]
21354l == r, arr[l]=sta

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

21开始排序
11arr[r]
11arr[l]
12l == r, arr[l]=sta

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

54开始排序
44arr[r]
44arr[l]
45l == r, arr[l]=sta

排序后数组

12345

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)

版权声明:
作者:MWHLS
链接:https://mwhls.top/910.html
来源:无镣之涯
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
打赏
< <上一篇
下一篇>>