Shell small curtilage according to 】 【 sort also known as narrowing the incremental sorting, is the improvement of insertion sort algorithm, its working principle is to define an interval sequence to represent the sort to compare elements in the process of how far is it between interval, interval will have the same number is divided into a set of insertion sort, most of the scenario, the interval can be defined in advance, It can also be generated dynamically. In large data sets, the optimization effect of Hill sorting on interpolation is very obvious.

One. Hill sort

Shell sort also known as narrowing the incremental sorting, is the improvement of insertion sort algorithm, its working principle is to define an interval sequence to represent the sort to compare elements in the process of how far is it between interval, interval will have the same number is divided into a set of insertion sort, most of the scenario, the interval can be defined in advance, can also be dynamically generated. In large data sets, the optimization effect of Hill sorting on interpolation is very obvious.

*/function shellSort(gaps, arr) {for(let g = 0; g < gaps.length; g++){ let h = gaps[g]; for(let i = gaps[h]; i < arr.length ; i++){ for(let j = i; j >= h; j = j - h){ if (arr[j] < arr[j-h]) { swap(arr, j, j-h); } } } } }function swap(arr, a, b) { let temp; temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; }Copy the code

If you think the algorithm is abstract, see the following GIF to get a feel for hill’s sorting process:

Two. Merge sort

Merge sort The basic idea of merge sort is divide and conquer. Suppose we have two sorted sets of size T(n/2), and now we want to merge the two sets into one ordered set using the following method:

function merge(set1, set2) {    let result = [];    let p1 = 0;    let p2 = 0;    let index = p1;    while (p1 < set1.length && p2 < set2.length){        if (set1[p1] < set2[p2]) {
            result.push(set1[p1++]);
        } else {
            result.push(set2[p2++]);
        }
    }    if(p1 === set1.length){
        result = result.concat(set2.slice(p2,set2.length))
    } else {
        result = result.concat(set1.slice(p1, set1.length));
    }    return result;
}Copy the code

Is every time compare two sorted sequence of the first element, take out your smaller into the result array, when a sequence of elements after all is take out, put the rest of another sequence elements one-time out to join the result array, that is, the algorithm by a linear order (i.e., the time complexity is O (n)) will be merged two sorted collection.

The idea of divide and conquer is to divide a problem into several smaller problems with the same solution in essence. For example, in the above example, sorting a set of N elements can be divided into sorting two sets of N /2 size, and then combine them using the above algorithm. Each problem of n/2 size can be split into two problems of N /4 size to solve. When splitting into a set with only one element, there is no need for in-set sorting, only bottom-up merging.

The main logical code for merge sort is as follows:

function mergeSort(Arr) { let left; let right; let pos; let result; if (Arr.length === 1) { return Arr; } else { pos = Math.floor(Arr.length / 2); left = Arr.slice(0, pos); right = Arr.slice(pos, Arr.length); result = merge(mergeSort(left), mergeSort(right)); console.log('merge step:',result); return result; }} / / tested using array unSortArr =,2,4,16,7,23,28,56,12,19 [5]; console.log(mergeSort(unSortArr));Copy the code

The results are as follows:


Quicksort

Quick Sort is one of the fastest sorting algorithms for large data sets (note that sorting performance can degrade when dealing with small data sets), and it also uses the idea of divide-and-conquer. The basic process of Quick sort is to select an element as pivot value, and then split the larger and smaller elements into two groups respectively. That is to say, the subsequence split by the fast sort algorithm is not necessarily equal in size. The quicksort process can be visualized as replicating a binary search tree.

*/function quickSort(arr) {if (arr. Length <= 1) {return arr; } let pivot = arr[0]; let left = []; let right = []; for(let i = 1; i < arr.length; i++){ if (arr[i] >= pivot) { right.push(arr[i]); } else { left.push(arr[i]); } } return quickSort(left).concat(pivot).concat(quickSort(right)); } let arr =,54,58,30,31,78,2,77,82,72 [72]; console.log(quickSort(arr));Copy the code

demo


For more exciting content, please click on the top right corner to follow the small house

Source: Huawei Cloud Original