The front end must know the top ten sorting algorithm

The front end must know the top ten sorting algorithm

Weekend combed ten sorting algorithm as a review, to you also review together, the following will explain 10 more sorting algorithm application, its code implementation using JavaScript.

Bubble sort

Ideas:

• Loop through the array, comparing the current element to the next element, and if the current element is larger than the next, bubbling up, so that after one loop the last number is the largest number in the array.
• The next loop continues, not through the sorted numbers.
• When a loop does not bubble, it is sorted and the loop is stopped.

function bubbleSort(array){
 for(let i = 0; i < array.length; i++){
 let flag = true;
 for(let j = 0; j < array.length - 1 - i; j++){
   if(array[j] > array[j + 1]){
     [array[j],array[j + 1]] = [array[j + 1],arr[j]];
     flag = false; }}if(flag){// If there is no bubble, the cycle is stopped
   break; }}return array;
}
Copy the code

• Time complexity: O(N2N^2N2)
• Space complexity: O(111)

Stability: stability

Quick sort

Ideas:

Through a sorting to sort the data is divided into two independent parts, one part of all the data are smaller than the other part, and then in this way to continue the two parts of the data fast, sorting process using recursion, so that the entire data becomes orderly. As you can see, fast typesetting takes advantage of the idea of divide and conquer.

• Select a base element, target (usually the first)
• Move elements smaller than target to the left side of the array, and those larger than target to the right side.
• Continue quicksort the left and right parts

/* * return the left, target, and right array */
function quickSort(array){
if(array.length < 2) return array;
const target = array[0];
const left = [], right = [];
for(let i = 1; i < array.length; i++){
 if(array[i] < target) {
   left.push(array[i]);
 }else{ right.push(array[i]); }}return quickSort(left).concat([target],quickSort(right));
}
​
/* * Array [l] < target = array[l]; array[l] < target = array[l]; array[l] < target = array[l]; Select array[r] >= target and assign it to array[r] * When l = r, all values on the left are smaller than target, and all values on the right are larger than target. Put the target in this position * saves space compared to the previous method */
function quickSort(arr,start,end){
if(end - start < 1) {
 return; 
}
const target = array[start];
let l = start, r = end;
while(l < r){
 while(l < r && array[r] >= target){
   r--;
 }
 array[l] = array[r];
 while(l < r && array[l] < target){
   l++;
 }
 array[r] = array[l];
}
array[l] = target;
quickSort(array, start, l - 1);
quickSort(array, l + 1, end);
return array;
}
Copy the code

• Time complexity: average O(nlog nlog NlogN), worst O(N2N^2N2), generally less than O(NlogN)
• Space complexity: O(logNlogNlogN), recursive call consumption

Stability: instability

Merge sort

Ideas:

MERGE SORT (Merge-sort) is the use of the idea of MERGE to achieve the SORT method, the algorithm uses the divide and conquer strategy (divide and conquer the problem into some small problems and then solve recursively, and the conquer stage will be divided into the stage of each answer “patch” together, that is, divide and conquer).

• The array is repeatedly split until there is only one element in each array
• Each array is merged in pairs, where each array is ordered

// Split the array directly into two arrays, and merge the array directly
function mergeSort(array){
if(array.length < 2) {return array;
}
const mid = Math.floor(array.length / 2);
const left = array.slice(0, mid);
const right = array.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
const 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

• Time complexity: O(nlog nlog nlog n)
• Space complexity: O(NNN)

Stability: stability

Selection sort

Ideas:

Each loop picks the smallest number and places it in the first ordered sequence.

function selectionSort(array, flag = false) { // flag indicates the selection order
for(let i = 0; i < array.length - 1; i++){
 let minIndex = i;
 for(let j = i + 1; j < array.length; j++){
     if(array[j] < array[minIndex]){
       minIndex = j;
     }
 }
 [array[minIndex], array[i]] = [array[i], array[minIndex]];
}
return flag ? arr.reverse() : arr;
}
Copy the code

• Time complexity: O(N2N^2N2)
• Space complexity: O(111)

Stability: instability

Insertion sort

Ideas:

• View the left sequence as an ordered sequence, fetch the next element, and scan the sorted sequence from right to left
• If the element is less than the new element, the scan continues, otherwise the element is moved to the next bit
• It stops when it finds a position where the element is less than or equal to the new element
• Repeat to the end of the cycle

function insertSort(array){
for(let i = 0; i < array.length; i++){
 let preIndex = i - 1, cur = array[i];
 while(preIndex >= 0 && array[preIndex] > cur){
   array[preIndex + 1] = array[preIndex];
   preIndex--;
 }
 array[preIndex + 1] = cur;
}
return array;
}
Copy the code

• Time complexity: O(N2N^2N2)
• Space complexity: O(111)

Stability: stability

Heap sort

A heap is a complete binary tree with the following properties:

• The value of each node is greater than or equal to the value of its left and right children, called the big top heap

• The value of each node is less than or equal to the value of its left and right children, called the small top heap

Note: No size relationship is required between the left and right child values of a node.

The big top heap is as follows:

The subscript of the parent node is (I −1)/2(I – 1)/2(I −1)/2 rounded

The left child subscript of a node with subscript I is: I ∗2+1i * 2+ 1I ∗2+1

The right child subscript of a node with subscript I is: I ∗2+ 2I *2+ 2I ∗2+2

Here is an example of the idea of a large top heap:

• Construct the sequence to be sorted into a large top heap, taking the top number of the heap (i.e., the maximum)
• Then build a big top heap of the remaining numbers, and take the top number of the heap (that is, the largest of the remaining values).
• Repeat the process until you have all the numbers in the heap, and you end up with a sequence from largest to smallest

/* * Properties of the maintenance heap * @param arr Array of heap storage * @param n array length * @param I subscript of the node to be maintained */
function heapify(arr,n,i){
let largest = i;
let lson = i * 2 + 1;
let rson = i * 2 + 2;
// Find the largest subscript of the parent, left child, and right child
if(lson < n && arr[largest] < arr[lson]){
 largest = lson;
}
if(rson < n && arr[largest] < arr[rson]){
 largest = rson;
}
if(largest ! == i){// Assign the maximum value to the parent node
 [arr[largest],arr[i]] = [arr[i],arr[largest]];
 // If a heap is changed, it will affect the children's heaps, so recursion is requiredheapify(arr, n, largest); }}// Heapsort entry
function heap_sort(arr, n){
let i;
[(n/2)-1] --> [(n/ 1)-1)/2] --> [(n/ 1)-1)/2
for(i = (n / 2) - 1; i >= 0; i--){
 heapify(arr, n, i);
}

// Sort the top element of the heap to swap with the last element
for(i = n - 1; i >= 0; i--){
 [arr[i], arr[0]] = [arr[0], arr[i]];
 heapify(arr, i, 0);// Maintain the elements at the top of the heap
}
return arr;
}
// let arr = [2,3,8,1,4,9,10,7,16,14];
// let n = 10;
// heap_sort(arr, n);
Copy the code

• Time complexity: O(NlogNNlogNNlogN), where the heapify complexity is O(NNN), heapify complexity is O(logNlogNlogN)
• Space complexity: O(111)

Stability: stability

Hill sorting

Hill sort is an improvement on insertion sort to speed things up, swapping non-adjacent elements to sort parts of an array.

Ideas:

• We start by grouping the entire array, usually half the total length (odd or even), and we set the interval to t.
• I’m going to order any element in the array that’s spaced t apart, and I’m going to keep sorting it by half, and I’m going to keep sorting it until t equals 1, and when t equals 1, I’m already ordered.

function shellSort(arr){
let len = arr.length, gap, temp;
// Narrow the incremental gap
for(gap = len >> 1; gap >= 1; gap>>=1) {for(let i = gap; i < len; i++){
   let preIndex = i - gap;// Insert sort is sequential, with preIndex representing the previous element
   if(arr[i] < arr[preIndex]){
     temp = arr[i];
     while(preIndex >= 0&& arr[preIndex] > temp){ arr[preIndex + gap] = arr[preIndex]; preIndex -= gap; } arr[preIndex + gap] = temp; }}}return arr;
}
// shellSort([8, 9, 1, 7, 2, 3, 5, 4, 6, 0]);
Copy the code

• Time complexity: worst is O(N2N^2N2)
• Space complexity: O(111)

Stability: instability

Count sorting

This sort is suitable for sorting integers in a range, the space depending on the largest number.

Ideas:

Count the number of occurrences of each integer in the sequence, and then derive the index of each integer in the ordered sequence

• Get the maximum and minimum value of the array to be sorted and calculate the value if the minimum value is negative
• Create an array for counting elements
• Iterate over the array of statistics, adding the elements of the original array to the result array according to the number and order of each element in the statistics array

function countingSort(arr, flag = 0){
let min = arr[0], max = arr[0], len = arr.length;
// Obtain the maximum and minimum values
for(let i = 0; i < len; i++){
max = Math.max(arr[i], max);
min = Math.min(arr[i], min);
}
// Calculate the difference
let s = max - min;
console.log(s)
// Create an array for counting elements
let count = new Array(s).fill(0);
for(let i = 0; i < len; i++){
let index = arr[i] - min;// Create a subscript
count[index] += 1;
}
console.log(count)
// Iterate through the statistics array, adding the elements of the original array to the result array according to the number and order of each element in the statistics array
let res = [];
for(let i = 0; i < s + 1; i++){
if(count[i] === 0) continue;
res.push(arr[arr.indexOf(i + min)]);
--count[i];
}
return flag ? res.reverse() : res;
}
​
// let arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]
// console.log(countingSort(arr))
Copy the code

• Time complexity: O(N+kN+kN+ K)
• Space complexity: O(N+kN+kN+ K)

Stability: stability

Bucket sort

When the range of values in an array is too large, or is not an integer, bucket sort can be used to solve the problem. Similar to the statistical array created by counting sort, bucket sort requires the creation of several “buckets” to assist in sorting.

Ideas:

• Each bucket represents a range in which one or more elements can be held. First we need to create the buckets and specify the range of each bucket.Interval size = (Max - Min)/number of buckets
• Iterate over the original array, putting each element into its own bucket
• The elements in each bucket are sorted separately
• Iterates through all buckets and outputs all elements

function bucketSort(arr, size = 10){
let max = Math.max(... arr), min =Math.min(... arr), count =Math.floor((max - min) / size) + 1;// Set the interval size
let buckets = [];
for(let i = 0; i < count; i++){
 / / create a bucket
 buckets.push([]);
}
for(val of arr){
 // Group each element. Num indicates the number of the bucket
 let num = Math.floor((val - min) / size);
 buckets[num].push(val);
}
let result = [];
for(bucket of buckets){
 // Sort by any sort algorithm, if the amount of data can be small can use insertion sortresult.push(... insertSort(bucket)); }return result;
}
// Insert sort
function insertSort(arr){
for(let i =1; i < arr.length; i++){
 let j = i;
 let target = arr[j];
 while(j > 0 && arr[j - 1] > target){
   arr[j] = arr[j - 1];
   j--;
 }
 arr[j] = target;
}
return arr;
}
​
// let arr = [3,6,3,2,87,23,673,0]
// bucketSort(arr, 5)
Copy the code

If the number of buckets is N,

• Time complexity: O(NNN)
• Space complexity: O(NNN)

Stability: stability

Radix sort

Ideas:

Sort the data first by units, then by tens, then by hundreds……

When you sort a number of bits, you sort by buckets, and when you get to the bottom, you have an ordered set of elements.

• Set 10 buckets with sizes ranging from 0 to 9, and then put the same number of buckets into the bucket
• Then take the number in the bucket in order of 0 to 9, repeat the ones, tens, hundreds……
• Finally sorting is done

Note: Add 0’s in front of the number of digits

function radixSort(arr) {
let maxLen = 0;
// Calculate the maximum number of digits
for(let val of arr){
 let len = String(val).length;
 if(len > maxLen){ maxLen = len; }}// Iterate over the bits and sort them
for(let i = 1; i <= maxLen; i++){
 arr = sort(arr, i, maxLen);
}
return arr;
}
// Sort bits
function sort(arr, index, maxLen){
let buckets = [];
for(let i = 0; i < 10; i++){
// Create ten buckets
 buckets.push([]);
}
for(let val of arr){
 / / STR. PadStart (targetLength, string) :
 // Fill the specified string in front of the target string to make it reach the target length;
 // If the number of bits is not enough, add 0
 let str = String(val).padStart(maxLen, '0');
 // Store the corresponding value in the corresponding bucket
 let num = str[maxLen - index];
 buckets[num].push(val);
}
let result = [];
for(let bucket ofbuckets){ result.push(... bucket); }return result;
}
Copy the code

• Time complexity: O(k∗Nk*Nk∗N)
• Space complexity: O(N+KN +KN +K)

Stability: stability

Moving picture source: zhuanlan.zhihu.com/p/57088609

---

Weekend liver article, writing is not easy, if you feel useful or like, point to like it ~ your support is my biggest encouragement!