Why learn quicksort

Quick sorting, can be said to be the most efficient sort of a sort, the time complexity of O(nlogn), Java, JS and other languages of the array object sort method bottom, is to use fast sorting to achieve (when the array length is greater than 10 with fast sorting, less than 10 with insertion sort), and large plant interview also often see the figure of fast sorting, So it is necessary to learn fast scheduling

The basic idea of fast row

There are a lot of different perspectives on the Internet to understand the quick platoon, however, all changes are inseparable from the same

The basic idea of fast sorting is to randomly select a base element, place all elements smaller than the base element to its left, and all elements larger than the base element to its right, and then recursively fast-sort the left and right arrays of the base element respectively

Keep that in mind. You’re almost there

But the idea seems pretty straightforward, and actually, it’s hard to write code, but how do you get the most efficient way to move everything in the array that’s less than the base to the left of it, and everything in the array that’s greater than the base to the right of it? This is where the quicksort gets tricky.

The implementation code

With that said, let’s start with the code

function QuickSort(arr,start,end){
  if(start<end){
    let left = start;
    let right = end;
    let flag = arr[start];
    while(left < right){
      while(left < right && arr[right] >= flag){
        right--;
      }
      if(left<right)arr[left++] = arr[right];
      while(left < right && arr[left] <= flag){
        left++;
      }
      if(left<right)arr[right--] = arr[left];
    }
    arr[left] = flag;
    QuickSort(arr,start,left - 1);
    QuickSort(arr,left + 1,end); }}Copy the code

It doesn’t matter, I’m going to go through it line by line, but first of all, just to give you a sense of how it works, our goal is to move all the numbers in the array that are less than the base element to the left of it, and all the numbers in the array that are greater than the base element to the right of it.

All right, so at the beginning of the text, we’re using a sort of disassembling and replenishing idea here, randomly selecting the base elements, right? Then we can choose the most directly to the left of the element as a benchmark elements, the next step, to highlight, we define two pointer, left pointer is used to find than the base element, the element pointer is used to find elements smaller than benchmark element right, left pointer pointing to the starting point at the beginning, right pointer pointing at the beginning of the end exactly what’s down the east side to the west to fill? Because we chose the first leftmost element as the base element, we saved it with another variable flag

At this point you can imagine that the element that the left pointer now points to (the base element) is a bug because its element has already been saved. Now we move the right pointer slowly to the left. When we find the first point smaller than the base element, we add the element that the right pointer points to to the left pointer

while(left < right && arr[right] >= flag){
  right--;
}
if(left<right)arr[left++] = arr[right];
Copy the code

Do you understand this step? Select a value smaller than the base element and add it to the left pointer. And then!! Did the right pointer become a loophole again? Its element has gone somewhere else and needs to be completed, so we move the left pointer slowly to the right, find the first element that is larger than the base element, and fill the right pointer

while(left < right && arr[left] <= flag){
  left++;
}
if(left<right)arr[right--] = arr[left];
Copy the code

By now, you should have understood the method of dismantling the east and repairing the west? When the left and right Pointers collide, you can put the base element in the left or right pointer, because it is both a bug, and fill in the base element. This completes the round of removing the base element from the left and the base element from the right.

Note, however, that the numbers on the left and right sides of the base element are not yet ordered, they are just larger or smaller than the base element, so we need to do the next round of quicksort:

QuickSort(arr,start,left - 1);
QuickSort(arr,left + 1,end);
Copy the code

Finally, the recursive end condition: if the array you want to sort has only one element, don’t you need to sort? So, we only sort when start<end

  if(start<end){
  	.....
  }
Copy the code

Here, if there are still do not understand, you can leave a comment, or my code is not good place are welcome to advise everyone god