Description of algorithm

Classification algorithm

The ten common sorting algorithms can be divided into two broad categories:

  • Comparison sorting: to determine the relative order of elements by comparison, because its time complexity can not break O(Nlogn), so it is also called nonlinear time comparison sorting.
  • Non-comparative sorting: it does not determine the relative order of elements by comparison. It can break through the lower bounds of time based on comparison sorting and operates in linear time. Therefore, it is also called linear time non-comparative sorting.

Algorithm complexity

Relevant concepts

  • Stable: If a is ahead of B and a= B, a will still be ahead of B after sorting.
  • Unstable: If a is in front of B and a= B, a may appear behind B after sorting.
  • Time complexity: Total number of operations on sort data. Reflect the rule of operation times when n changes.
  • Spatial complexity: refers to the algorithm in the computer

A measure of the storage required for execution within, which is also a function of data size N.

Bubble Sort

Bubble sort is a simple sorting algorithm. It repeatedly walks through the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The task of visiting an array is repeated until no more exchanges are needed, that is, the array has been sorted. The algorithm gets its name because smaller elements slowly “float” to the top of the list through swapping.

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.

== GIF demo ==

== code implementation ==

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

Selection Sort

Selection-sort is a simple and intuitive sorting algorithm. It works by first finding the smallest (largest) element in the unsorted sequence and storing it at the beginning of the sorted sequence, then continuing to find the smallest (largest) element from the remaining unsorted elements and placing it at the end of the sorted sequence. And so on until all the elements are sorted.

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.

== GIF demo ==

== 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

Algorithm analysis

One of the most stable sorting algorithms, because whatever data goes in is O(n2) time, so when you use it, the smaller the data, the better. The only benefit might be that it doesn’t take up any extra memory. Theoretically speaking, the choice sort may also be the usual sort ordinary people think of the most sorting method.


Insertion Sort

Insertion Sort algorithm is a simple and intuitive sorting algorithm. It works by building an ordered sequence, scanning back to front in the sorted sequence for unsorted data, finding the appropriate location and inserting it.

Algorithm Description Generally, insert sort is implemented on an array using in-place. 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.

Dynamic graph demonstration Code implementation

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (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

In the implementation of algorithm analysis insertion sort, in-place sort is usually adopted (that is, the sort only needs O(1) extra space). Therefore, in the process of scanning from back to front, the sorted elements need to be repeatedly moved backward step by step to provide insertion space for the latest elements.

Shell Sort

1959 Shell invention, the first breakthrough O(N2) sorting algorithm, is an improved version of simple insertion sort. It differs from insertion sort in that it compares distant elements first. Hill sort is also called reduced increment sort.

Algorithm description Firstly, the whole record sequence to be sorted is divided into several sub-sequences for direct insertion sorting respectively. The specific algorithm description is as follows:

  • 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.

== GIF demo == Code implementation

Function shellSort(arr) {var len = arr.length; for (var gap = Math.floor(len / 2); gap > 0; Gap = math.floor (gap / 2)) {var I = gap; 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

The core of hill sort analysis is the setting of interval sequence. You can either set the interval sequence in advance or define the interval sequence dynamically. The algorithm for dynamically defining interval sequences was developed by Robert Sedgewick, co-author of Algorithms (4th Edition).


Merge Sort

Merge sort is an efficient sorting algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer. The ordered subsequences are combined to obtain a fully ordered sequence. That is, each subsequence is ordered first, and then the subsequence segments are ordered. If two ordered tables are joined into one ordered table, it is called 2-way merge.

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.

Dynamic graph demonstration Code implementation

function mergeSort(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>0 && right.length>0) {
        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

Algorithm analysis merge sort is a stable sorting method. As with select sort, merge sort performs independently of the input data, but performs much better than select sort because it is always O(nlogn) time. The trade-off is extra memory.

Quick Sort

The basic idea of quicksort is that the records to be sorted are separated into two independent parts through a sort. If the keywords of one part of the records are smaller than those of the other part, the two parts of the records can be sorted separately to achieve the order of the whole sequence. Algorithm Description Quicksort uses divide-and-conquer to divide a list into two sub-lists. The specific algorithm is described 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.

Dynamic graph demonstration Code implementation

function quickSort(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); } return arr; } function partition(arr, left, right) {var index = 1; for (var i = index; i <= right; i++) { if (arr[i] < arr[pivot]) { swap(arr, i, index); index++; } } swap(arr, pivot, index - 1); return index-1; } function swap(arr, i, j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }Copy the code

Heap Sort

Heapsort refers to a sort algorithm designed by using heap data structure. Heap is a nearly complete binary tree structure, and also satisfies the property of heap: that is, the key value or index of the child node is always smaller (or larger) than its parent node. 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.

Dynamic graph demonstration

Code implementation

var len; Function buildMaxHeap(arr) {function buildMaxHeap(arr) {len = arr.length; for (var i = Math.floor(len/2); i >= 0; i--) { heapify(arr, i); }} function 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); for (var i = arr.length - 1; i > 0; i--) { swap(arr, 0, i); len--; heapify(arr, 0); } return arr; }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.

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.

Dynamic graph demonstration 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

Algorithm analysis counting sort is a stable sorting algorithm. When the input elements are n integers between 0 and k, the time complexity is O(n+k) and the space complexity is also O(n+k), which is faster than any comparison sorting algorithm. Counting sort is a very efficient sorting algorithm when k is not very large and the sequence is relatively concentrated.


Bucket Sort

Bucket sort is an updated version of counting sort. It makes use of the mapping relation of functions, and the key of efficiency lies in the determination of the mapping function. Bucket sort works by dividing the data into a finite number of buckets, assuming that the input data is evenly distributed, and sorting each Bucket separately (it is possible to use another sorting algorithm or to continue sorting using Bucket sort recursively).

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.

Images demonstrate 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]; 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] = []; } for (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]); // Insert sort for (var j = 0; j < buckets[i].length; j++) { arr.push(buckets[i][j]); } } return arr; }Copy the code

The optimal linear time for bucket sorting is O(n). The time complexity of bucket sorting depends on the time complexity of sorting data between buckets, because the time complexity of all other parts is O(n). Obviously, the smaller the bucket, the less data there is between the buckets, and the less time it takes to sort. But the corresponding space consumption will increase.


Radix Sort

Radix sort is sorted by low order and then collected; And then sort it in order, and then collect it; And so on, all the way to the highest place. Sometimes some attributes are prioritized, first by low priority, then by high priority. The final order is that the higher-priority ones come first, and the lower-priority ones come first.

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 sorting is suitable for small range numbers);

Dynamic graph demonstration Code implementation

Code implementation

Help document Shortcut key catalogue title text style list Link code sheet table footnote Note custom list LaTeX mathematical formula Insert Gantt diagram Insert UML diagram Insert Flowchart Flowchart Insert Class diagram code sheet replication

Here are some inline code slices.

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

The algorithm analyzes radix sort based on sorting separately and collecting separately, so it is stable. However, the performance of radix sort is slightly worse than that of bucket sort. It takes O(n) time complexity for each bucket allocation of keywords, and O(n) time complexity for obtaining new keyword sequences after allocation. If the data to be sorted can be divided into D keywords, the time complexity of radix sort will be O(D *2n). Of course, D is much smaller than N, so it is basically linear.

The space complexity of radix sort is O(n+k), where K is the number of buckets. Generally n>> K, so you need about n extra Spaces.