Sorting algorithm
Common internal sort algorithms are: selection sort, bubble sort, insert sort, heap sort, hill sort, merge sort, quick sort, bucket sort, count sort, radix sort
1. Selection sort
Simple but least useful sorting algorithm. Because his time is n ^ 2. But you can optimize
Algorithm thought
Given an array, the first value defaults to the minimum value and minPos to 0. Then the array is iterated over, and each data is compared with the corresponding value of minPos. If it is smaller than the corresponding value of minPos, the index corresponding to the data is assigned to minPos. At the end of the cycle, the minimum index of the array can be found. Next, the value corresponding to the minimum subscript is swapped with the default minimum, the first data. In this way, the smallest value is found and placed in the first place.
Next, you need to follow the above method to find the second, third… N minima. The array that needs to be traversed becomes an array of other sorted data.
Time complexity: O(n²)
Space complexity: 1
Function selectionSort(a) {let len = a.length; for(let i=0; i<len - 1; I++) {// it's len-1 because by the last two elements, the whole array is sorted. let minPos = i; for(let j=i+1; j<len; j++) { a[j] < a[minPos] && (minPos = j) } [a[minPos], a[i]] = [a[i], A [minPos]]}} let a =,4,1,3,7,90,45,34,23,58 [5] the console, log (a) / / [5, 4, 1, 3, 7, 90, 45, 34, 23. 58] selectionSort(a) console.log(a) // [1, 3, 4, 5, 7, 23, 34, 45, 58, 90]Copy the codeOptimized version, a new type parameter, to achieve descending, ascending functions
/** * select sort * @param {*} a array to sort * @param {*} type Sort type, 'desc' : descending; 'ASC' : ascending, default ascending. Function selectionSort2(a, type = 'asc') {let len = a.length; for (let i = 0; i < len - 1; i++) { let index = i; for (let j = i + 1; j < len; j++) { let isSwitch = type === 'desc' ? a[j] > a[index] : a[j] < a[index] isSwitch && (index = j); } [a[index], a[i]] = [a[i], a[index]]; } } let a = [5, 4, 1, 3, 7, 90, 45, 34, 23, 58, 92, 9]; selectionSort2(a); console.log(a); // [1, 3, 4, 5, 7, 9, 23, 34, 45, 58, 90, 92]Copy the codeOptimize the version again, at the same time find the minimum and maximum value on both sides of the sequence, both sides gradually approach, the number of cycles will be reduced
/** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** */ function selectionSort3(a) {let len = a.length; for (let i = 0; i < len / 2; i++) { let minPos = i, maxPos = len - 1 - i; for (let j = i + 1; j < len - i - 1; j++) { a[j] < a[minPos] && (minPos = j); a[j] > a[maxPos] && (maxPos = j); } [a[minPos], a[i]] = [a[i], a[minPos]]; [a[maxPos], a[len - 1 - i]] = [a[len - 1 - i], a[maxPos]]; } } let a = [5, 4, 1, 3, 7, 90, 45, 34, 23, 58]; selectionSort3(a); console.log(a);Copy the codeAlgorithm validation, logarithm (generate enough random numbers randomly to compare your algorithm with the original result)
2. Bubble sort
Bubble Sort is also a simple and intuitive sorting algorithm.
Algorithm thought
If two adjacent data are not compared, if the previous data is greater than the next data, the two data are exchanged until the end of the traversal, and the maximum value is obtained, which is located at the end of the data.
Then, do what you did before to get the maximum number of positions divided by the array, and the array is sorted.
Time complexity: O(n²)
Space complexity: 1
Function bubbleSort(a) {let len = a.length; for (let i = 0; i < len - 1; i++) { for (let j = 0; j < len - 1 - i; j++) { a[j] > a[j + 1] && ([a[j], a[j + 1]] = [a[j + 1], a[j]]); } } } let a = [5, 4, 1, 3, 7, 90, 45, 34, 23, 58, 92, 9]; bubbleSort(a); console.log(a); // [1, 3, 4, 5, 7, 9, 23, 34, 45, 58, 90, 92]Copy the codeOptimized version, a new type parameter, to achieve descending, ascending functions
/** * bubble sort * @param {*} a array to sort * @param {*} type Sort type, 'desc' : descending; 'ASC' : ascending, default ascending. */ function bubbleSort2(a, type = 'asc') {let len = a.length; for (let i = 0; i < len - 1; i++) { for (let j = 0; j < len - 1 - i; j++) { let isSwitch = type === 'desc' ? a[j] < a[j + 1] : a[j] > a[j + 1] isSwitch && ([a[j], a[j + 1]] = [a[j + 1], a[j]]); } } } let a = [5, 4, 1, 3, 7, 90, 45, 34, 23, 58, 92, 9]; bubbleSort2(a); console.log(a); // [1, 3, 4, 5, 7, 9, 23, 34, 45, 58, 90, 92]Copy the codeOptimized version, set isSorted to check if the array isSorted, time complexity reduced to O(n)
@param {*} type sort type, 'desc' : descending order; 'ASC' : ascending, default ascending. */ function bubbleSort3(a, type = 'asc') {let len = a.length; let n = 0; for (let i = 0; i < len - 1; i++) { let isSorted = true; // <== = set isSorted to true for (let j = 0; j < len - 1 - i; j++) { n++ let isSwitch = type === 'desc' ? a[j] < a[j + 1] : IsSorted = ([a[j], a[j + 1]] = [a[j + 1], a[j + 1]] = [a[j + 1], a[j]]) && (isSorted = false); } if(isSorted) { return; }} let a = [1,2,3,4]; bubbleSort3(a); console.log(a); // [1, 3, 4, 5, 7, 9, 23, 34, 45, 58, 90, 92]Copy the code3. Insert sort
The principle of insertion sort should be the easiest to understand, because anyone who has ever played poker should be able to understand it in seconds. Insertion sort is one of the most simple and intuitive sorting algorithms. Its working principle is to build an ordered sequence and scan the unsorted data from back to front in the sorted sequence to find the corresponding position and insert it.
Algorithm thought
Treat the first data as an ordered sequence and the data after the second as an unordered sequence. Scan the unordered sequence from beginning to end, inserting each scanned element into the appropriate place in the ordered sequence. (If the element to be inserted is equal to an element in the ordered sequence, the element to be inserted is inserted after the equal element.)
Time complexity: O(n²)
Space complexity: 1
Method 1: Compare the data to be inserted with the ordered data in pairs from large to small. If the previous data is larger than the next data, swap the data until the ordered data is correct
/** * insert sort * @param {*} a insert sort */ function insertionSort(a) {let len = a.length; for(let i=1; i<len; i++) { for(j=i; j>0; j--) { a[j] < a[j-1] && ([a[j],a[j-1]] = [a[j-1], a[j]]) } } } let a = [5, 4, 1, 3, 7, 90, 45, 34, 23, 58, 92, 9]; insertionSort(a); console.log(a); // [1, 3, 4, 5, 7, 9, 23, 34, 45, 58, 90, 92]Copy the codeMode 2: Optimization point: TMP is added to store current data. If the value is greater than TMP, the value moves backwards. If not, exit the loop and assign TMP to a[j+1].
Function insertionSort2(a) {let len = a.length; for(let i=1; i<len; i++) { let j, tmp = a[i] for(j=i-1; j>=0; j--) { if(a[j] > tmp) { a[j+1] = a[j] }else { break; } } a[j+1] = tmp } } let a = [5, 4, 1, 3, 7, 90, 45, 34, 23, 58, 92, 9]; insertionSort2(a); console.log(a); // [1, 3, 4, 5, 7, 9, 23, 34, 45, 58, 90, 92]Copy the codeNote: Insertion sort can be optimized in combination with binary lookup
4. Hill sort
Hill sort, also known as the descending incremental sort algorithm, is a more efficient and improved version of insertion sort. But Hill sort is an unstable sort algorithm.
Hill sort is an improved method based on the following two properties of insertion sort:
- Insertion sort has high efficiency when it operates on almost ordered data, that is, it can achieve the efficiency of linear sort
- But insert sort is generally inefficient because it can only move data one bit at a time;
Algorithm thought
Firstly, the whole sequence of records to be sorted is divided into several sub-sequences for direct insertion sort respectively. When the records in the whole sequence are “basically ordered”, the direct insertion sort of all records is carried out successively.
Time complexity: O(n ^ 1.3)
Space complexity: 1
@param {*} a */ function shellSort(arr) {var len = arr, temp, gap = 1; While (gap < len/3) {// Dynamically define interval sequence gap =gap*3+1; } for (gap; gap > 0; gap = Math.floor(gap/3)) { for (let i = gap; i < len; i++) { temp = arr[i]; let j; for (j = i-gap; j >= 0 && arr[j] > temp; j-=gap) { arr[j+gap] = arr[j]; } arr[j+gap] = temp; } } return arr; } let a = [5, 4, 1, 3, 7, 90, 45, 34, 23, 58, 92, 9]; shellSort(a); console.log(a); // [1, 3, 4, 5, 7, 9, 23, 34, 45, 58, 90, 92]Copy the code5. Merge sort
Merge sort is an efficient sorting algorithm based on Merge operations. This algorithm is a very typical application of Divide and Conquer.
As a typical divide-and-conquer algorithm application, merge sort can be implemented in two ways:
- Top-down recursion (all recursive methods can be iteratively rewritten, hence the second method);
- Bottom-up iteration;
Algorithm thought
1. Apply for a space equal to the sum of the two sorted sequences, which is used to store the combined sequence;
2. Set two Pointers, the initial positions are respectively the starting positions of the two sorted sequences;
3. Compare the elements pointed to by the two Pointers, select the relatively small element into the merge space, and move the pointer to the next position;
4. Repeat Step 3 until a pointer reaches the end of the sequence;
5. Copy all remaining elements of the other sequence directly to the end of the merged sequence.
Time complexity: O(nlogn)
Space complexity: O(n)
Divide and conquer
Merges contiguous ordered subsequences
// function mergeSort(a) {// Let len = a.length; if (len < 2) return a; let mid = ~~(len / 2), left = a.slice(0, mid), right = a.slice(mid); return merge(mergeSort(left), mergeSort(right)); function merge(left, right) { let res = []; while (left.length && right.length) { let target = left[0] <= right[0] ? left.shift() : right.shift(); res.push(target); } while (left.length) { res.push(left.shift()); } while (right.length) { res.push(right.shift()); } return res; } } let a = [5, 4, 1, 3, 7, 90, 45, 34, 23, 58, 92, 9]; mergeSort(a); console.log(mergeSort(a)); // [1, 3, 4, 5, 7, 9, 23, 34, 45, 58, 90, 92]Copy the codeQuicksort
Quicksort uses a Divide and conquer strategy to Divide one serial (list) into two sub-lists.
Quicksort is a typical application of divide-and-conquer in sorting algorithm. Quicksort is essentially a recursive divide-and-conquer method based on bubble sort.
The worst case for quicksort is O(n ^ 2), for example, quicksort. But its amortized expected time is O(nlogn), and the constant factor implied in O(nlogn) notation is very small, much smaller than the stable complexity is O(nlogn) merge sort. Therefore, for most random sequences with weak order, quicksort is always better than merge sort.
Algorithm thought
- 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 the base value and subsequences of elements greater than the base value;
Quicksort also uses divide-and-conquer.
Divides the original array into smaller arrays (but it doesn’t split them up like merge sort does).
(1) First, select the middle entry from the array as the primary
(2) Create two Pointers, one on the left pointing to the first item and one on the right pointing to the last item of the array. Move the left pointer until we find an element larger than the pivot, then move the right pointer until we find an element smaller than the pivot, then swap them and repeat the process until the left pointer passes the right.
(3) Then, the algorithm repeats the previous two steps for the partitioned small array (the subarray of values smaller than the principal element and the subarray of values larger than the principal element) until the array is completely sorted.
Time complexity: O(nlogn)
Space complexity: O(logn)
/** * @param {*} a */ function quickSort(a) {quick(a, 0, a.length-1); return a; function quick(list, left, right) { let index = 0; if (list.length > 1) { index = partition(list, left, right); Left < index-1 && quick(list, left, index-1); index < right && quick(list, index, right); } } function partition(list, left, right) { let mid = list[(right + left) >> 1]; while (left <= right) { while (list[left] < mid) { left++; } while (list[right] > mid) { right--; } if (left <= right) { [list[left], list[right]] = [list[right], list[left]]; left++; right--; } } return left; } } let a = [7, 3, 2, 8, 1, 9, 5, 4, 6, 10]; quickSort(a); console.log(a);Copy the codeHeap sort
The heap
A heap is one that meets the following two conditions:
- The heap is a complete binary tree
- Any node on the heap must be greater than or equal to (large top heap) or less than or equal to (small top heap) its left and right child values
If any node on the heap is greater than or equal to the child node value, it is called the big top heap
If any node on the heap is less than or equal to the child node value, it is called the small top heap
That is, in the big top heap, the root node is the largest element in the heap;
In the small top heap, the root node is the smallest element in the heap;
How to create a big (small) top heap
A complete binary tree is suitable for array storage, and the heap is a complete binary tree, so it can be stored using array storage directly:
In simple terms, the heap can be represented as an array. Given A node with A subscript I (I starts at 1), its parent must be A[I /2], its left child A[2i], and its right child A[2i+1].
Algorithm thought
Heap is a complete binary tree, it can use an array of storage, and big top of the heap maximum value is stored in the root node (I = 1), so we can always choose big pile top root node and heaps of exchange, the last node in the maximum effective sequence at this time of the last, minus 1 and effective sequence, effective heap remains fully binary tree structure, and then the heap, Becomes the new big top heap and repeats until the effective heap is 0 in length and the sort is complete.
The complete steps are as follows:
- Convert the original sequence (n) into a large top heap
- Set the effective sequence length of the heap to n
- Swap the top of the heap element (the first valid sequence) with the last child element (the last valid sequence) and subtract 1 from the valid sequence length
- Heap effective sequence, so that the effective sequence is renamed a big top heap
- Repeat the above 2 steps until the valid sequence length is 1 and the sorting is complete
Time complexity: nlogn
Space complexity: 1
/** * @param {*} a */ function heapSort(a) {let len; // Since multiple declared functions require data length, set len to the global variable buildMaxHeap(a); for (let i = a.length - 1; i > 0; i--) { [a[0], a[i]] = [a[i], a[0]]; len--; heapify(a, 0); } return a; Function buildMaxHeap(a) {len = a.length; for (let i = Math.floor(len / 2); i >= 0; i--) { heapify(a, i); }} function heapify(a, I) {let left = 2 * I + 1, right = 2 * I + 2, largest = I; if (left < len && a[left] > a[largest]) { largest = left; } if (right < len && a[right] > a[largest]) { largest = right; } if (largest ! = i) { [a[i], a[largest]] = [a[largest], a[i]]; heapify(a, largest); } } } let a = [107, 107, 101, 103, 102, 108, 101, 109, 105, 104, 106, 110]; console.log(heapSort(a)); console.log(a);Copy the code8. Counting sort
The core of counting sort is to convert input data values into keys and store them in extra array space. As a sort of linear time complexity, counting sort requires that the input data must be integers with a definite range.
Counting sort characteristics
The running time is θ (n + k) when the input element is n integers between 0 and k. Counting sort is not comparison sort, which is faster than any comparison sort algorithm.
Since the length of the array C used to count depends on the range of data in the array to be sorted (equal to the difference between the maximum and minimum value of the array to be sorted plus 1), counting sort takes a lot of time and memory for arrays with a large range of data. For example, counting sort is the best algorithm for sorting numbers between 0 and 100, but it is not suitable for sorting names alphabetically. However, counting sort can be used to sort large arrays of data using the algorithm in radix sort.
Generally speaking, for example, there are 10 people of different ages, and 8 of them are statistically younger than A, so A’s age ranks ninth. By using this method, the position of everyone else can be obtained, and the order can be sorted. Of course, repeated ages require special treatment (to ensure stability), which is why we end up reverse-populating the target array and subtracting 1 from the statistics for each number.
Algorithm idea:
(1) Find the largest and smallest elements in the array to be sorted
(2) Count the number of occurrences of each element with the value of I in the array and store it into the i-th item of array C
(3) Add all the counts (starting with the first element in C, add each term to the previous one)
(4) Reverse fill the target array: place each element I in the C(I) item of the new array, and subtract 1 from C(I) for each element
Time complexity: O(n + K)
Space complexity: O(n + K)
@param {*} a @param {*} maxV */ function countSort(a, maxV) {let count = new Array(maxV + 1) len = a.length, countL = count.length, sortedIndex = 0; for (let i = 0; i < len; i++) { count[a[i]] = count[a[i]] + 1 || 1; } for (let j = 0; j < countL; j++) { while (count[j]) { a[sortedIndex++] = j; count[j]--; } } return a; } @param {*} a */ function countSort2(a) {let min = math.min (... a), max = Math.max(... a), len = a.length, count = new Array(max - min + 1).fill(0), countL = count.length, sortedIndex = 0; Arr [j] -min = 1 for (let I = 0; i < len; i++) { count[a[i] - min]++; } for (let j = 0; j < countL; j++) { while (count[j]) { a[sortedIndex++] = j + min; count[j]--; } } return a; } @param {*} a */ function countSort3(a) {let min = math.min (... a), max = Math.max(... a), len = a.length, count = new Array(max - min + 1).fill(0), countL = count.length, sortedIndex = 0, res = []; Arr [j] -min = 1 for (let I = 0; i < len; i++) { count[a[i] - min]++; } for (let j = 1; let j = 1; j < countL; J ++) {count[j] += count[j-1]; } // For (let k = len-1; k >= 0; SortedIndex = count[a[k] -min]; [sortedindex-1] = a[k]; count[a[k] - min]--; } return res; } let a = [107, 107, 101, 103, 102, 108, 101, 109, 105, 104, 106, 110]; console.log(countSort3(a)); console.log(a);Copy the code9. Radix sort
Radix sort is a kind of non-comparative integer sort algorithm. Its principle is to cut the integers into different numbers according to the number of digits, and then compare them according to each number. Since integers can also represent strings (such as names or dates) and floating-point numbers in a particular format, radix sort is not restricted to integers.
Radix sort:
- It’s a non-comparative sort
- Advanced version of counting sort
- Sort groups by the value of the same significant digit
- There is the concept of a bucket sorted by the size of each bit from right to left
- The sort of each bit follows the queue for first-in, first-out rewrites
Time complexity: O(n * k)
Space complexity: O(n + K)
Function radixSort(a) {let maxDigit = (math.max (... a) + '').length let counter = [],mod = 10,dev = 1; for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { for(let j = 0; j < a.length; j++) { let bucket = parseInt((a[j] % mod) / dev); ! counter[bucket] && (counter[bucket] = []); counter[bucket].push(a[j]); } let pos = 0; for(let j = 0; j < counter.length; j++) { let value = null; if(counter[j] ) { while ((value = counter[j].shift())) { a[pos++] = value; } } } } return a; } let a = [107, 107, 101, 103, 102, 108, 101, 109, 105, 104, 106, 110]; console.log(radixSort(a, 3)); console.log(a);Copy the code10. Bucket sorting
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. To make bucket sorting efficient, we need to do two things:
- Increase the number of barrels as much as extra space is available
- The mapping function used can evenly distribute the N input data into K buckets
Time complexity: O(n + K)
Space complexity: O(n + K)
The elements are then sorted in each bucket:
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