快速排序（java 图示+代码）

nliu / 2023-07-25 / 原文

对无序数据进行排序

时间复杂度 n*logn

100 50 200 30 10 40 43 300 150 130 110 220 56 32 11 111

以100做基准，比100小的放左边，比100大的放右边

第一轮：50，30，10，40，43，56，32，11，#100#，200，300，150，130，110，220，111

第二轮：30，10，40，43，32，11，#50#，56，| #100# |，150，130，110，111，#200#，300，220

第三轮：10，11，#30#，40，43，32，| #50# |，56，| #100# |，130，110，111，#150#，| #200# |，220，#300#

第一轮

按照这样的规则一次排序，直到两个基准重合，第一轮操作会将100排好位置

第二轮

第二轮结束，50、110的位置已经找到

重复上述步骤，最终得到有序结果。

代码示例

public static void main(String[] args) {
    int[] arr={100,50,200,30,10,40,43,300,150,130,110,220,56,32,11,111};
    sort(arr,0,arr.length-1);
    System.out.println(Arrays.toString(arr));
}

 public static void sort(int[] arr,int flag1,int flag2){
    int left=flag1;
    int right=flag2;
     while(flag1!=flag2){
         if(arr[flag1]>arr[flag1+1]){
             int temp=arr[flag1];
             arr[flag1]=arr[flag1+1];
             arr[flag1+1]=temp;
             flag1++;
         }else{
             int temp=arr[flag1+1];
             arr[flag1+1]=arr[flag2];
             arr[flag2]=temp;
             flag2--;
         }
     }
     //当左侧数据超过两个，再次排序
     if(flag1-1-left>0){
         sort(arr,left,flag1-1);
     }
     //当右侧数据超过两个，再次排序
     if(right-(flag1+1)>0){
         sort(arr,flag1+1,right);
     }
 }

小插曲

public class Node {
    public int value;
}

public static void main(String[] args) {
    int a=10;
    Node b=new Node();
    b.value=20;
    Node c=new Node();
    c.value=30;
    change(a,b,c);
    
    /**输出什么？？？**/
    System.out.println(a);  //10
    System.out.println(b.value); //20
    System.out.println(c.value); //55
}

public static void change(int p1,Node p2,Node p3){
    p1=33;
    p2=new Node();
    p2.value=44;
    p3.value=55;
}