[interview: Basics 05: quick sort]

【 interview ： The basic chapter 05： Quick sort 】

00. Preface

Please point out any questions , thank .

01. brief introduction

Quick sort is an advanced sort algorithm , The average time complexity can reach O(n$lo{g}_{2}n$), Its main idea is to find a datum point larger than the datum point and put it at one end of the datum point Those smaller than the reference point shall be placed at one end of the reference point Repeat the process at each end Implement with recursion .

General idea ： The reference point of each trip remains unchanged Finally, exchange benchmarks

There are two mainstream methods to realize quick sorting ：

1. Unilateral circulation method ： Select the rightmost end as the benchmark , There are two variables i j,i Used to maintain the boundary of elements smaller than the datum point , That is, the target index of each exchange , j Responsible for finding elements smaller than the benchmark , Once found with i swapping , Last i Exchange with the reference point Complete a sequence .

2. Bilateral circular law ： Select the leftmost end as the benchmark , There are two variables i j,i Responsible for finding elements larger than the benchmark from left to right , j Responsible for finding elements smaller than the benchmark , Once found j And i swapping , Finally, the benchmark is connected with i j Switching of coincidence points A sort is done .

02. Algorithm steps

Pair sequence {5,3,7,2,9,8,1,4} Perform ascending quick sort .

Unilateral circulation method ( The rightmost end is the reference point ):

i=0 And j=1 swapping i=1 And j=3 swapping i=2 And j=6 swapping i=3 And r=7 swapping
3 2 1 4 9 8 7 5
i=0 And r=2 swapping
1 2 3 4 9 8 7 5
i=1 And j=1 swapping i=2 And r=2 swapping
1 2 3 4 9 8 7 5
i=4 And r=7 swapping
1 2 3 4 5 8 7 9
i=5 And j=5 swapping i=6 And j=6 swapping i=7 And r=7 swapping
1 2 3 4 5 8 7 9
i=5 And r=6 swapping
1 2 3 4 5 7 8 9

Bilateral circular law ( The leftmost end is the reference point ):

Datum subscript 0 Reference point value 5
i=2 And j=7 swapping i=4 And j=6 swapping i=4 And j=4 swapping l=0 And j=4 swapping
1 3 4 2 5 8 9 7
Datum subscript 0 Reference point value 1
i=0 And j=0 swapping l=0 And j=0 swapping
1 3 4 2 5 8 9 7
Datum subscript 1 Reference point value 3
i=2 And j=3 swapping i=2 And j=2 swapping l=1 And j=2 swapping
1 2 3 4 5 8 9 7
Datum subscript 5 Reference point value 8
i=6 And j=7 swapping i=6 And j=6 swapping l=5 And j=6 swapping
1 2 3 4 5 7 8 9

Several problems that should be paid attention to in the bilateral circulation method

1. The reference point is on the left And first j-- Again i++

2.while(i<j) Be sure to add. Otherwise, the sorted values will be scrambled again

3.while(i<j&&a[i]<=x) = Be sure to add. To prevent the datum point from being moved

Code implementation

Unilateral circulation method :

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);
}

result

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

Bilateral circular law

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)//  The order should be fixed , If not fixed, it will lead to  i Find the last value greater than the reference point and stop  j because 
            //  Want to find small   Then finally with i coincidence   Exit loop   But now j No value smaller than the reference point has been found   So finally 
            //  Errors will be caused by the final exchange with the benchmark 
            j--;
        while (i<j&&a[i]<=x)// = In order to prevent   The reference point is moved ,i<j To prevent the sorted values from being disturbed again 
            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);
}

result

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