Front-end necessary algorithm: quick sort, two different ideas to solve, will!!

There are two ways to think about quicksort, but they take different time, and I’ll talk about them separately; The complexity is order nlog^n.

All code is based on leetCode 912. Sort array validation

First: base on the first number of the array:

Implementation idea:

Set two Pointers I and J to the head and tail of the array respectively. First move I to the right, array[I] is less than the reference value arr[0], get the subindex I greater than the reference number and stop traversing on the left.

Similarly: move the pointer J to the left to find the subscript j less than the reference value. At this point the two values are swapped. You put less than the base value on the left and more than the base value on the right.

Details:

To end up with the base number somewhere in the middle of the array, its left digit is smaller than it is, and its right digit is larger than it is. Swap the datum and subscript I, and recursively quicksort the elements to the left and right of I.

Specific code implementation:

var sortArray = function(nums) {
    quickSort(0, nums.length - 1, nums)
    return nums;
};
var quickSort = function (left, right, arr){
    var temp = arr[left];
    var i = left;
    var j = right;
    if(i > j) return
    while(i < j) {
        while(arr[j] >= temp && j > i) {
            j--;
        }
        while(arr[i] <= temp && i < j) {
            i++;
        }
        
        [arr[i], arr[j]] = [arr[j], arr[i]]
    }
    // The left side is smaller than temp and the right side is larger than temp.
    [arr[left], arr[i]] = [arr[i], arr[left]]
    
    quickSort(left, i-1, arr);
    quickSort(j+1, right, arr);
}
Copy the code

Base on the middle value of the array:

Implementation idea:

Set two Pointers I and J to the head and tail of the array respectively. First move I to the right, array[I] is less than the reference value arr[0], get the subindex I greater than the reference number and stop traversing on the left.

Similarly: move the pointer J to the left to find the subscript j less than the reference value. At this point the two values are swapped. You put less than the base value on the left and more than the base value on the right. The elements to the left and right of the recursive reference value are then quicksorted separately.

What’s the difference between the first number and the middle number? For a nearly sorted array, using the first number as the base number is the least efficient performance.

Specific code implementation:

var sortArray = function(nums) {
     quickSort(0, nums.length - 1, nums);
    return nums
};
var quickSort = function(left, right, arr) {
   if(left >= right) return
　　var temp = arr[Math.floor((left + right) / 2)]var i = left;
    var j = right;
    while(i <= j) {
        while(arr[i] < temp) {
            i++
        }
        while(arr[j] > temp) {
            j--
        }
         if(i <= j) {
         [arr[i], arr[j]] = [arr[j], arr[i]]
           i++;
            j--;
            
        }
     }
        quickSort(left, i-1, arr);
        quickSort(i, right, arr);
}
Copy the code

The elapsed time and memory consumption are completely different when comparing the two different baseline processing methods.