Top 10 sorting algorithms for front-end interviews

The preface

Front-end post compared with other IT positions, algorithm requirements are relatively low. But I have experienced Tencent, Ali, Baidu and other large factory school recruitment interview, found that the basic algorithm thought or must master. Therefore, in recent years, I began to study basic algorithms and found that JavaScript Description of Data Structures and Algorithms is particularly suitable for front-end reading.

Next, let’s analyze the top 10 algorithm ideas and usage scenarios.

A, Bubble Sort

Bubble sort, exchange sort is the simplest sorting method, its main idea is: in the sequence to be sorted to choose two adjacent records of the number, if the reverse order then swap, until there is no reverse order of the sequence.

1. Algorithm description

• Compare adjacent elements. If the first one is larger than the second, swap them both;
• Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair, so that the last element should be the largest;
• Repeat for all elements except the last one;
• Repeat steps 1 to 3 until the sorting is complete.

2. Code implementation

function bubbleSort(arr) {
    var len = arr.length;
    for(var i = 0; i < len; i++) {for(var j = 0; j < len-1-i; j++) {if(arr [j] > arr [j + 1]) {/ / two adjacent elements compare var temp = arr [j + 1); // Element Exchange ArR [J]; arr[j] = temp; }}}return arr;
}
Copy the code

Quick Sort

Quicksort is an improvement on bubbling sort. In quicksort, records are compared and moved from both ends to the middle, with high values moving from front to back and low values moving from back to front in one move, thus reducing the total number of comparisons and moves.

1. Algorithm description

Quicksort divides a list into two sub-lists using divide-and-conquer. The algorithm is as follows:

• Pick an element from the sequence, called pivot;
• Reorder the array so that all elements smaller than the base value are placed in front of the base value and all elements larger than the base value are placed behind the base value (the same number can go to either side). After the partition exits, the benchmark is in the middle of the array. This is called a partition operation;
• Recursively sorts subsequences of elements less than a reference and subsequences of elements greater than a reference.

2. Code implementation

functionquickSort(arr, left, right) { var len = arr.length, partitionIndex, left = typeof left ! ='number'? 0 : left, right = typeof right ! ='number'? len -1 : right;
    if(left < right) { partitionIndex = partition(arr, left, right); quickSort(arr, left, partitionIndex-1); quickSort(arr, partitionIndex+1, right); }} // Partition operationfunctionPartition (arr, left, right) {var pivot = left, index = 1;for(var i = index; i<= right; i++){if(arr[i] < arr[pivot]){
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index-1);
    returnindex-1; } // Exchange datafunction swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
Copy the code

Insertion Sort

Insertion sort is a kind of sorting method with the help of “insertion”. Its main idea is: each time, a number to be sorted is inserted into an ordered sequence according to the size of its key code until all the numbers are sorted.

1. Algorithm description

Insertion sort is implemented on an array using in-place, and the specific algorithm is described as follows:

• Starting with the first element, the element can be considered sorted;
• Fetch the next element and scan back to front in the sorted element sequence;
• If the element (sorted) is larger than the new element, move the element to the next position;
• Repeat step 3 until you find a place where the sorted element is less than or equal to the new element;
• After inserting a new element into that position;
• Repeat steps 2 to 5.

2. Code implementation

functioninsertionSort(arr) { var len = arr.length; var preIndex, current; // Scan index from back to front, current element valuefor(var i = 1; i<len; i++) { preIndex = i-1; current = arr[i];while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}
Copy the code

Shell Sort

Hill sort is an improvement of insertion sort. The basic idea of the sort is that the whole sequence to be sorted is divided into several sub-sequences, and the sub-sequences are directly inserted respectively. When the whole sequence is basically ordered, the whole sequence is inserted again.

1. Algorithm description

• Select a delta sequence T1, T2… , where Ti >tj, tk=1;
• Sort the sequence k times according to the number of incremental sequences k;
• In each sort, the sequence to be sorted is divided into several sub-sequences of length M according to the corresponding increment TI, and each sub-table is sorted by direct insertion. Only when the increment factor is 1, the whole sequence is treated as a table, and the length of the table is the length of the whole sequence.

2. Code implementation

function SellSort(arr) {
    var len = arr.length;
    for(var gap = Math.floor(len / 2); gap > 0; Gap = math.floor (gap / 2)) {// Multiple groups are executed alternatelyfor(var i = gap; i < len; i++) { var j = i; var current = arr[i];while(j - gap >= 0 && current < arr[j - gap]) { arr[j] = arr[j - gap]; j = j - gap; } arr[j] = current; }}return arr;
}
Copy the code

Selection Sort

Selective sorting is a simple and intuitive sorting algorithm. Its basic idea is: firstly, select the minimum value in the sequence to be sorted, store it at the beginning of the sorted sequence, and then continue to find the minimum element from the remaining unsorted elements, and put it at the end of the sorted sequence. And so on until all the elements are sorted.

1. Algorithm description

Direct selection sort of N records can get ordered results after n-1 direct selection sort. The specific algorithm is described as follows:

• Initial state: the disordered region is R[1..n], and the ordered region is empty.
• Th order (I =1,2,3… N-1), the current ordered region and disordered region are R[1..i-1] and R(I.. N). This sorting selects the record R[k] with the smallest keyword from the current unordered region and exchanges it with the first record R in the unordered region, so that R[1.. I] and R[I +1..n) become the new ordered region with 1 more records and the new unordered region with 1 less records, respectively.
• N minus one is done, and the array is sorted.

2. Code implementation

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for(var i = 0; i< len-1; i++){ minIndex = i;for(var j = i+1; j<len; j++) {if(arr[j] < arr[minIndex]) {// Find minIndex = j; } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; }return arr;
}
Copy the code

Heap Sort (Heap Sort)

Heap sort is a sort algorithm designed by using heap data structure. A heap is a complete binary tree with the following properties: the value of each node is less than or equal to the value of its left and right children (called the small root heap); Or each node has values greater than or equal to those of its left and right children (called the large root heap).

1. Algorithm description

• The initial sequence of keywords to be sorted (R1,R2… .rn) is constructed into the big top heap, which is the initial unordered region;
• By exchanging the top element R[1] with the last element R[n], a new unordered region (R1,R2… Rn-1) and a new ordered region (Rn), and R[1,2… n-1]<=R[n];
• Since the new heap top R[1] after the swap may violate the heap properties, it is necessary to apply the current unordered region (R1,R2… Rn-1) adjusts to the new heap, and then swaps R[1] again with the last element of the unordered region to obtain the new unordered region (R1,R2… .Rn-2) and the new ordered region (Rn-1,Rn). This process is repeated until the number of elements in the ordered region is N-1, and the whole sorting process is complete.

2. Code implementation

Var len; var len; // Create a big top heapfunction buildMaxHeap(arr) {
    len = arr.length;
    for(var i = Math.floor(len/2); i >= 0; i--) { heapify(arr, i); }} // Heap adjustmentfunction heapify(arr, i) {
     var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;

    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
function HeapSort(arr) {
    buildMaxHeap(arr);
}
Copy the code

Merge Sort (Merge Sort)

Merge sort is a sort method with the help of “merge”. Merge means the process of merging two or more ordered sequences into one ordered sequence. The main idea of merge sort is to merge several ordered sequences step by step and finally merge into an ordered sequence.

1. Algorithm description

• The input sequence of length N is divided into two subsequences of length N /2.
• Merge sort is used for these two subsequences respectively.
• Combine two sorted subsequences into a final sorted sequence.

2. Code implementation

functionMergeSort (arr) {var len = arr.length;if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    var result = [];
 
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else{ result.push(right.shift()); }}while (left.length)
        result.push(left.shift());
 
    while (right.length)
        result.push(right.shift());
 
    return result;
}
Copy the code

Counting Sort ()

Counting sort is not a comparison-based sorting algorithm. Its core is to convert the input data values into keys and store them in an extra array space. As a sort of linear time complexity, counting sort requires that the input data must be integers with a definite range.

1. Algorithm description

• Find the largest and smallest elements in the array to be sorted;
• Count the number of occurrences of each element of value I in the array and store it in the i-th entry of array C;
• Add up all the counts (starting with the first element in C, adding each term to the previous one);
• Reverse populating the target array: place each element I in the C(I) item of the new array, subtracting C(I) by 1 for each element.

2. Code implementation

function countingSort(arr, maxValue) {
    var bucket = new Array(maxValue + 1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;
 
    for (var i = 0; i < arrLen; i++) {
        if(! bucket[arr[i]]) { bucket[arr[i]] = 0; } bucket[arr[i]]++; }for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) { arr[sortedIndex++] = j; bucket[j]--; }}return arr;
}
Copy the code

Bucket Sort

Bucket sort is a simple allocation sort. It works by assuming that the input data is evenly distributed, sorting the data into a finite number of buckets, and sorting each bucket separately (it is possible to use another sorting algorithm or recursive bucket sort).

1. Algorithm description

• Set a quantitative array as an empty bucket;
• Iterate over the input data and put the data one by one into the corresponding bucket;
• Sort each bucket that is not empty;
• Splicing together sorted data from never-empty buckets.

2. Code implementation

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }
 
    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if(arr[i] < minValue) { minValue = arr[i]; // The minimum value of input data}else if(arr[i] > maxValue) { maxValue = arr[i]; }} // bucket initialization var DEFAULT_BUCKET_SIZE = 5; / / sets the default bucket number 5 bucketSize = bucketSize | | DEFAULT_BUCKET_SIZE; var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; var buckets = new Array(bucketCount);for(i = 0; i < buckets.length; i++) { buckets[i] = []; } // Allocate data to buckets using mapping functionsfor (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }
 
    arr.length = 0;
    for(i = 0; i < buckets.length; i++) { insertionSort(buckets[i]); // Sort each bucket, using insert sortfor(var j = 0; j < buckets[i].length; j++) { arr.push(buckets[i][j]); }}return arr;
}
Copy the code

Radix Sort

Radix sort, is sorted according to the low first, then collect; And then sort it in order, and then collect it; And so on, all the way to the highest place.

1. Algorithm description

• Get the largest number in the array and get the number of digits;
• Arr is the original array, and each bit is taken from the lowest level to form the RADIX array.
• The radix is sorted by counting (taking advantage of the fact that counting sort is suitable for small range numbers).

2. Code implementation

var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]! =null) {while((value = counter[j].shift()) ! = null) { arr[pos++] = value; }}}}return arr;
}
Copy the code

conclusion

10 sorting algorithms are summarized and compared as shown in the figure below:

Quicksort is the most efficient, and is suitable for large amounts of data and random array of values. But if the data is already basically ordered, the efficiency degrades to O(n^2).

Bubble sort is the slowest sorting algorithm and the least efficient algorithm in practical application, with time complexity O(n^2).

Selection sort is almost the same as bubble sort in practice.

Insert sort is twice faster than bubble sort. Generally, it is not suitable for situations where a large amount of data or a large amount of data is repeated.

Hill sort is 5 times faster than bubble sort and roughly 2 times faster than insert sort. Shell sort is much slower than quicksort, merge sort, and heap sort. However, shell algorithm is relatively simple, especially suitable for the case where the amount of data is less than 5000 and the performance requirement is not very high.

Heapsort is suitable for very large data sequences because it does not require a lot of recursion or multi-dimensional staging arrays, but only a staging space to swap.

Merge sort is slightly faster than heapsort and requires more memory space than heapsort because it requires an extra array.

How do I choose a sorting algorithm? 1. If n is small (n<=50), direct insertion sort and selection sort can be used; 2. If n is small, considering stability, counting sort, cardinal sort and bucket sort can be selected; 3. If n is large, the sorting algorithm with O(nlog n) time complexity should be adopted: quicksort, heap sort and merge sort. (If n elements have duplicate elements, merge sort is appropriate)

The sorting algorithm of data structure is extensive and profound. At present, I only summarize 10 common algorithms, and then learn other sorting algorithms, and then continue to discuss with you ~~