排序算法-快排

快排是一个较为常见的排序算法

快排的思路

有一个乱序的数组

[2 , 3 , 1 , 6 , 4 , 7 , 8 , 9 , 5]

首先以这个数组的最后一个数5进行分开,将这个数组进行成一个分块处理,第一部分是小于5,中间是等于5,后面是大于5。在三个区间内数字可以是无序的。

我们先不关心如何实现这个操作,假设这个操作可以实现。将这个操作作为一个基本操作

那么现在数组将会变为

[2 , 3 , 1 , 4 , 5 , 8 , 9 , 6 , 7]

再将5之前的4位数再进行一次基础操作,5之后也进行一次基础操作

[2 , 3 , 1 , 4 , 5 , 6 , 7 , 8 , 9]

如此递归进行下去,如果数组只有3位,那么它进行一次基础操作之后,它必将有序

那么重点就是这个基础操作如何实现

基础操作的实现

我们现在的目标是将按数组最后一个数将一个数组分为三个区域。

我们设定四个规则

当前数小于P,当前数与小于区下一个数交换,小于区右扩,当前数调下一个
当前数大于P,当前数与大于区前一个数交换,大于区左扩,当前数不动
当前数等于P,不动,当前数调下一个
大于区与小于区相遇时,最后一个数与大于区第一个数交换

还是这个数组[2 , 3 , 1 , 6 , 4 , 7 , 8 , 9 , 5],小于区用红色标记,大于区用绿色标记

当前数从下标0开始,2<5,小于区的下一个就是下标0,无需交换,下标调下一个

[2 , 3 , 1 , 6 , 4 , 7 , 8 , 9 , 5]

下标1,3<5,与小于区下一个交换,跳下一个

[2 , 3 , 1 , 6 , 4 , 7 , 8 , 9 , 5]

下标2,1<5,与小于区下一个交换,跳下一个

[2 , 3 , 1 , 6 , 4 , 7 , 8 , 9 , 5]

下标3,6>5,与大于区上一个交换,下标不动

[2 , 3 , 1 , 9 , 4 , 7 , 8 , 6 , 5]

下标3,9>5,与大于区上一个交换,下标不动

[2 , 3 , 1 , 8 , 4 , 7 , 9 , 6 , 5]

下标3,8>5,与大于区上一个交换,下标不动

[2 , 3 , 1 , 7 , 4 , 8 , 9 , 6 , 5]

下标3,7>5,与大于区上一个交换,下标不动

[2 , 3 , 1 , 4 , 7 , 8 , 9 , 6 , 5]

下标3,4<5,与小于区下一个交换,跳下一个

[2 , 3 , 1 , 4 , 7 , 8 , 9 , 6 , 5]

大于区与小于区相遇时,最后一个数与大于区第一个数交换

[2 , 3 , 1 , 4 , 5 , 8 , 9 , 6 , 7]

可能会觉得这个与小于区下一个进行交换是多余的,但事实是并不多余,假如有多个相同的数字触发等于的操作,就会出错

比如

[2 , 3 , 1 , 2]

下标为0,进行不交换的操作,下标往后调

[2 , 3 , 1 , 2]

下标为1,3>2,与大于区上一个交换,下标不动

[2 , 1 , 3 , 2]

下标为1,1<2,不交换的话,跳下一个,小于区右扩,那么小于与大于就相碰了

进行完结束操作,交换2与3,那么操作就结束了

如果交换,小于区的下一个为2,当前为1,交换一下就可以将1调回小于区

代码实现

这个基础操作传入三个参数,一个数组,一个需要进行操作的左端点,进行操作的右端点

public static int[] partition(int[] arr, int L, int R)

我们还需要三个变量

一个作为行走的下标index

一个作为小于区的最右端lessR

一个作为大于区的最左端moreL

public static int[] partition(int[] arr, int L, int R) 

按照上述的操作前三个规则走完的终结是index碰到了moreL。、

然后就是三个规则的实现swap是单独写的交换函数。

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

很好理解的一段简单代码

        while (index < moreL) {
            if (arr[index] < arr[R]) {
                swap(arr, index, lessR + 1);
                lessR++;
                index++;
            } else if (arr[index] == arr[R]) {
                index++;
            } else {
                swap(arr, index, moreL - 1);
                moreL--;
            }
        }

这时需要去返回一个数组,去返回等于区域的范围

return new int[]{lessR + 1, moreL};

用基础操作去递归实现快排

递归依然使用peocess方法。

因为返回了相同数字的范围。递归就是弄两边

    public static void process(int[] arr, int L, int R) {
        if (L > R) {
            return;
        }
        int[] equalE = partition(arr, L, R);
        //equalE[0]  等于区域的第一个数
        //equalE[1]  等于区域的最后一个数
        process(arr, L, equalE[0] - 1);
        process(arr, equalE[1] + 1, R);
    }

接着去真正的QuickSort去调用这个方法,并判断边界条件

    public static void QuickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

时间复杂度分析

快速排序的时间复杂度取决于划分子数组的方式。

最优划分(平均情况)的时间复杂度为O(nlogn),

最差情况(当数组已经排序时)的时间复杂度为O(n^2)。

版权声明:除特殊说明,博客文章均为栋dong原创,依据CC BY-SA 4.0许可证进行授权,转载请附上出处链接及本声明。
如有需要,请在留言板留言,或者添加我的QQ或者微信
我只是一个学生,如有错误或者侵权,请联系我,谢!
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
春节
快乐