preface

Recently I am preparing for the fall recruitment interview, the basic algorithm of course should be well stable, although I have written sorting algorithm before, but I have forgotten it for a long time, record here, and review it well by the way.

The basic idea

  1. Select the first value in the array as the base number.
  2. We go through the array, putting anything larger than the base number on the left and anything less than the base number on the right. In this way, the original array can be divided into left and right arrays based on the base number.
  3. Repeat one or two recursive steps until only one element exists in the array.

Dynamic graph display

Code implementation

/* by author: Lvjianyou */ public class QuickSort2 {public static void sort(int[] arr,int start,int end){ Because we're recursing, we can't change the parameters that we're passing. int i,j,privt; i = start; j = end; If (start<=end) return; if(start<=end) return; Privt = arr[start]; privt = arr[start]; While (I <j){// start from the right and start from the left; // start from the right and start from the left. // Why? Because the first digit on the left is already copied, starting from the left will overwrite the number on the right. while (i<j){ if(arr[end]>privt){ end--; }else{// the right number is less than or equal to the base number, move! arr[i++] = arr[end]; // There is no swap operation, directly overwrite, the first digit is copied out, so overwrite doesn't matter. break; }} while(I <j){// if(arr[I]<privt){// if(arr[I]<privt); }else{// If the number on the left is larger than the base number, put the number on the right side of the array and switch to the right side for traversal. arr[j--] = arr[i]; break; }}} arr[I] = privt; // Repeat the operation ========= for step 3 sort(arr,start,i-1); sort(arr,i+1,end); }}Copy the code

Complexity analysis

Time complexity: O(nlogn) on average, and O(n^2) at worst