Implementation approach

  • Quicksort is the fastest sorting method known in practice.
  • Quicksort uses the idea of divide and conquer, which also means recursion in your code.
  1. Select any element in A, pivot, that serves as the base.
  2. Move elements less than the base to the left of the base, and elements greater than the base to the right of the base.
  3. A is divided into two parts by Pivot, and you do the same thing for the remaining two parts.
  4. Use recursion to continue the above two parts in the same order.

The implementation code

The three arguments are the array that you want to sort, the first index of the array, the last index of the array

function Quick_Sort(nums,left,right) {

    if (left >= right) return;
    let pivot = nums[left];
    let l = left;
    let r = right;

    while (l < r) {
        while (l < r && nums[r] >= pivot) {
            r--;
        }
        if (l < r) {
            nums[l] = nums[r];
        }
        while (l < r && nums[l] <= pivot) {
            l++;
        }
        if (l < r) {
            nums[r] = nums[l];
        }
        if (l >= r) {
            nums[l] = pivot;
        }
    }
    Quick_Sort(nums,left,r-1);
    Quick_Sort(nums,r+1,right);
    nums
}

const nums = [17.97.9.17.1.8];
Quick_Sort(nums,0.5);
nums
Copy the code

revelation

  • Learn to use divide and conquer to solve problems.