Quicksort is another typical application of the idea of divide and conquer in sorting algorithms. Quicksort uses a Divide and conquer strategy to Divide a list into two sub-lists. The specific algorithm is described as follows:

  • It picks an element from the sequence, called the pivot;
  • Reorder the sequence so that all elements smaller than the base value are placed in front of the base value, and all elements larger than the base value are placed after the base value (the same number can be on either side). After the partition exits, the benchmark is in the middle of the series. This is called a partition operation;
  • The subsequence of elements less than the base value is recursively sorted from the subsequence of elements greater than the base value.

Time complexity

On average, order n items and compare them nlogn times. In worst case, however, this is not common enough for any of the o (N2) comparisons to be made. In fact, quicksort is usually significantly faster than any other o (nlogn) algorithm, since its inner loop can be implemented efficiently on most of the architectures.

The worst case of quicksort is O(n ^ 2), for example, quicksort in an ordered sequence. But its amortized expected time is O(nlogn), and the constant factor implied in the O(nlogn) notation is very small, much smaller than the merge sort whose complexity is stable and equal to O(nlogn). Therefore, quicksort is always better than merge sort for most random sequences with weak ordering.

Classic fast row

code

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

    public static void process1(int[] arr, int L, int R){
        if (L>=R){
            return;
        }
        int M =partition(arr,L,R);
        process1(arr,L,M-1);
        process1(arr,M,R);

    }

    private static int partition(int[] arr,int L,int R) {
        if (L>R){
            return -1;
        }
        if (L ==R){
            return L;
        }
        int lessEqual = L-1;//小于等于的位置
        int index = L;//当前位置
        while (index<R){
            if (arr[index]<=arr[R]){
                //如果当前位置的数据小于等于 目标数据 ，则把当前位置的数据和 小于等于位置的的下一个位置进行交换
                //同时 小于等于位置往下移动一位
                swap(arr,index,++lessEqual);
            }
            index++; //当前位置往后移动一位
        }
        //最后，小于等于位置和 目标数据进行交换
        swap(arr,++lessEqual,R);
        return lessEqual;

    }

    public static void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
Copy the code

The while loop section of the code is illustrated

Optimized a version of quicktype

Advantages: Divided into three parts

code

public static void quickSort2(int[] arr){ if (arr == null || arr.length<2){ return; } process2(arr,0,arr.length-1); } private static void process2(int[] arr, int L, int R) { if (L>=R){ return; Int [] equalArea = netherLandsFlag(arr,L,R); process2(arr,L,equalArea[0]-1); process2(arr,equalArea[1]+1,R); } private static int[] netherLandsFlag(int[] arr, int L, int R) { if (L>R){ return new int[]{-1,-1}; } if (L == R){ return new int[]{L,R}; } int less = L-1; Int more = R; Int index = L; While (index<more){if (arr[index] == arr[R]){index++; }else if (arr[index] < arr[R]){ // swap(arr,index,less+1); //less++ // index++; // swap(arr,index++,++less); }else {// Swap (arr,index,--more); // swap(arr,index,--more); } } swap(arr,more,R); // <[R] =[R] >[R] return new int[]{less+1,more}; } public static void swap(int[] arr,int i,int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }Copy the code

int more = R; // The number at position R is the target number for comparison, and this position is reserved. R-1 is the left boundary greater than R, and the target number is compared at position [L– r-1], so the boundary is: L-1) L…. R-1(R

The illustration

Improved version of random quicktype

Classical quicksort always specifies the last element in the array or part as the base value, while random quicksort specifies random values in the array or part as the base value.

The good thing about this is that it avoids the worst case run of quicksort being order n squared.

The illustration

code

private static void quickSort3(int[] arr){ if (arr ==null || arr.length<2){ return; } process3(arr,0,arr.length-1); } private static void process3(int[] arr, int L, int R) { if (L>=R){ return; } / / choose a random number and target number exchange swap (arr, L + (int) (Math. The random () * (R - L + 1)), R); int[] equalArea = netherLandsFlag(arr,L,R); process3(arr,L,equalArea[0]-1); process3(arr,equalArea[1]+1,R); }Copy the code

The difference is the random factor.