【寒假实习备战day8】快速排序算法的学习（二）

简单的自我介绍

我是一名双非大二学生，目前学习方向为Java后端，快速学习并学到了springboot，并和实验室的朋友做了一个简单的微信小程序，想在寒假找份有关互联网的实习，打算海投，城市和公司暂时没有特别强烈的意向，我会再次牢固的复习一遍Java整套学习知识，并且开始补充算法知识刷算法题，来备战这次寒假实习，并且想报名参加蓝桥杯Java B组的比赛，希望我的一些学习笔记能为你带来一些帮助，这次给大家带来的是快速排序的算法学习。

今天开始去Boos直聘上看一些最新的在郑州的一些Java实习招聘信息，就中意了五六个，果然郑州互联网环境是真不行啊，还是找远一点的地方实习看看机会吧。在宿舍效率...还是有点难受，周围宿友都在玩游戏，看视频，但我也不是懒人，没有被封宿舍也是下课就跑实验室，晚上十点半实验室那栋楼要关门我才走的（宿舍们和实验室那栋楼都是十一点关门），到了宿舍就是洗漱一下，看看手机休息娱乐一下，十二点前就睡觉了，我在宿舍就是要不睡觉，要不在睡觉的路上。害。可能我还是比较适合什么环境干什么事情吧，但这严峻的情况下，时间紧，任务重，我又不是超人，一时半会这状态就难以改变，说焦虑吧...其实也没有，更多的是一种麻木吧，因为我去年就非常焦虑了，现在已经免疫了哈哈哈哈哈哈，不知道是好事还是坏事。不能消极！继续努力，继续加油，呜呜呜呜😭😭😭

双边循环法需要注意的几个问题

1.基准点在左边且先j-- 再i++

2.while(i<j)一定要加否则排序好的值会再次被打乱

3.while(i<j&&a[i]<=x) = 一定要加为了防止基准点被移动

代码示例

public static void sort1(int[] a,int l,int r){
    if (l>=r)
        return;
    int i=l;
    int x = a[r];
    for (int j=l;j<r;j++){
        if (a[j]<x){
            int t=a[j];
            a[j]=a[i];
            a[i]=t;
            i++;
        }
    }
    int t=a[r];
    a[r]=a[i];
    a[i]=t;
    for (int k=0;k<a.length;k++)
        System.out.printf("%d ",a[k]);
    System.out.println();
    sort2(a,l,i-1);
    sort2(a,i+1,r);
}
public static void main(String[] args) {
    int[] a = {5,3,7,2,9,8,1,4};
    sort1(a,0,a.length-1);
}

结果：
3 2 1 4 9 8 7 5
1 2 3 4 9 8 7 5
1 2 3 4 9 8 7 5
1 2 3 4 5 8 7 9
1 2 3 4 5 8 7 9
1 2 3 4 5 7 8 9

双边循环法

public static void sort2(int[] a,int l,int r){
    if (l>=r)
        return;
    int x = a[l];
    int i = l;
    int j = r;
    while (i<j){
        while (i<j&&a[j]>x)
            j--;
        while (i<j&&a[i]<=x)
            i++;
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    int t=a[l];
    a[l]=a[j];
    a[j]=t;
    for (int k=0;k<a.length;k++)
        System.out.printf("%d ",a[k]);
    System.out.println();
    sort1(a,l,j-1);
    sort1(a,j+1,r);
}
public static void main(String[] args) {
    int[] a = {5,3,7,2,9,8,1,4};
    sort2(a,0,a.length-1);
}

PS：顺序要固定,如果不固定会导致 i找到最后大于基准点的值停止 j会因为想要找到小的然后最终与i重合退出循环但是现在j还没有找到小于基准点的值所以最后会因为最后和基准点进行交换导致错误为了防止基准点被移动，i<j是为了防止排序好的值再次被打乱

结果：

1 3 4 2 5 8 9 7
1 3 4 2 5 8 9 7
1 2 3 4 5 8 9 7
1 2 3 4 5 7 8 9