Quick sorting (detailed illustration of single way, double way, three way)

One 、 Quick sort

         Select any data of the array to be sorted as the benchmark , Traversing elements in an array . Place elements smaller than the reference value to the left of the reference value , Those greater than the reference value are placed to the right of the reference value , Put the reference value in the middle , At this time, the reference value reaches the final position . Then, the subarray on the left and the subarray on the right of the benchmark are processed in the same way , Until the interval is reduced to 1, It means that the array is ordered .

Two 、 One way sorting

Example ： Given a length of 10 Array of {6,1,2,7,9,3,4,5,10,8}

The problem solving steps ;

（1） The idea of quick sorting is to put the first element of the array 6 Move to a position in the sequence M, Give Way M The elements on the left are <=6,M The right elements of are >=6; So we need to define two pointers i and j At the beginning and end of the sequence ;

（2）i Move backward in turn （i++） Move to greater than 6 The element of stops ,j Move forward （j--） Move to less than 6 The elements of , And will i,j Corresponding element exchange .

 （3） according to （2） Step by step until i,j coincidence ; And because the element referred to in coincidence is 3,3<6 In exchange ; here 6 The left side of is smaller than 6,6 The right side of is larger than 6.

（4） The sequence element at this time 6 The left side of is smaller than 6, The right side is larger than 6; take 6 Repeat the left part of （1）（2）（3） Until the first element of the sequence is 1;

（5）6 The right part of is the same as the left part ;

（7） Code implementation ; from （1）~（6） It can be seen that the implementation steps have been repeated , So use recursive method .

void Quick_Sort(int *arr, int begin, int end){
    if(begin > end)
        return;
    int tmp = arr[begin];
    int i = begin;
    int j = end;
    while(i != j){
        while(arr[j] >= tmp && j > i)
            j--;
        while(arr[i] <= tmp && j > i)
            i++;
        if(j > i){
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    arr[begin] = arr[i];
    arr[i] = tmp;
    Quick_Sort(arr, begin, i-1);
    Quick_Sort(arr, i+1, end);
}

3、 ... and 、 Two way sorting

         The quick sort algorithm mentioned before is to >v and <v Both partial elements are placed in the index value i The left part of the position pointed to , Our two-way quick sort algorithm is different , He uses two index values （i、j） Used to traverse our sequence , take <v Put the elements in the index i To the left of the position pointed to , And will be >v Put the elements in the index j To the right of the position pointed .

（1） Code implementation ;

 
 
import java.util.Arrays;
import java.util.Random;
 
 
public class QuickSort {
 
    private static Random random;
    private QuickSort() {
 
    }
 
    
    public static <E extends Comparable<E>> void sort2ways(E[] arr) {
        random = new Random();
        sort2ways(arr, 0, arr.length - 1);
    }
 
    private static <E extends Comparable<E>> void sort2ways(E[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int p = partition2(arr, l, r);
        sort2ways(arr, l, p - 1);
        sort2ways(arr, p + 1, r);
    }
 
    private static <E extends Comparable<E>> int partition2(E[] arr, int l, int r) {
 
        //  Generate [l,r] Random index between 
        int p = l+random.nextInt(r-l+1);
        swap(arr,l,p);
 
        // arr[l+1...i-1]<= v;arr[j+1...r]>=v
        int i = l+1,j = r;
        while (true){
 
            while (i<=j && arr[i].compareTo(arr[l])<0)
                i++;
            while (j>=i && arr[j].compareTo(arr[l])>0)
                j--;
 
            if (i>=j)
                break;
 
            swap(arr,i,j);
            i++;
            j--;
        }
        swap(arr,l,j);
        return j;
 
    }
 
 
}

Four 、 Three way sorting

         Divide the whole array into values v, Divided into less than v The area of is called smaller than area , be equal to v The area of is equal to the area and greater than v The area of is larger than the three parts of the area , In the next recursion, there is no need to deal with equal v Equal area of , Because the element equal to the area has reached the final position , For the existence of a large number equals v The three-way fast array greatly improves the efficiency .

（1） Code implementation

import java.util.*;
 
public class QuickSort3Ways {
 
    //  Use quick sort recursively , Yes arr[l...r] The scope of the order 
    private static void sort(Comparable[] arr, int l, int r){
 
        //  For small arrays ,  Use insert sort 
        if( r - l <= 15 ){
            InsertionSort.sort(arr, l, r);
            return;
        }
 
        //  Random in arr[l...r] In the range of ,  Select a value as the calibration point pivot
        swap( arr, l, (int)(Math.random()*(r-l+1)) + l );
 
        Comparable v = arr[l];
 
        int lt = l;     // arr[l+1...lt] < v
        int gt = r + 1; // arr[gt...r] > v
        int i = l+1;    // arr[lt+1...i) == v
        while( i < gt ){
            if( arr[i].compareTo(v) < 0 ){
                swap( arr, i, lt+1);
                i ++;
                lt ++;
            } else if( arr[i].compareTo(v) > 0 ){
                swap( arr, i, gt-1);
                gt --;
            } else{ // arr[i] == v
                i ++;
            }
        }
 
        swap( arr, l, lt );
 
        sort(arr, l, lt-1);
        sort(arr, gt, r);
    }
 
    public static void sort(Comparable[] arr){
 
        int n = arr.length;
        sort(arr, 0, n-1);
    }
 
    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
 
}