Note: The comparison of sorting algorithm performance in this article is based on actual situation.
Code address: github.com/collins999/…
1. Bubble sort
Train of thought
By comparing and swapping adjacent elements, each loop finds the maximum or minimum value of the unordered array.
implementation
created() {
let array = [1, 6, 7, 4, 5, 8, 9, 0, 2, 3];
let res = this.bubbleSort(array);
console.log(res);
},
methods: {
bubbleSort(arr) {
let length = arr.length;
if(! length) {return [];
}
for (let i = 0; i < length; i++) {
for (let j = 0; j < length - i - 1; j++) {
if(arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; }} to the console. The log (` first${i+1}Subcycle ', arr); }returnarr; }}Copy the code
Optimization: One-way bubble implementation
If no data needs to be exchanged during a round of comparison summary, the array is ordered, reducing the number of sorting loops.
created() {
let array = [1, 6, 7, 4, 5, 8, 9, 0, 2, 3];
let res = this.bubbleSort(array);
console.log(res);
},
methods: {
bubbleSort(arr) {
let length = arr.length;
if(! length) {return [];
}
for (let i = 0; i < length; i++) {
let mark = true; // If there is no data to interact with during a round of comparison, the array is ordered.for (let j = 0; j < length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
mark = false; } } console.log(mark); The console. The log (` first${i+1}Subcycle ', arr);if (mark) return;
}
returnarr; }}Copy the code
Optimization: Bidirectional bubble implementation
In normal bubble sort, only one of the maximum or minimum values can be found in one cycle. In bidirectional bubble sort, multiple rounds of filtering are used to find both the maximum and minimum values.
created() {
let array = [1, 6, 7, 4, 5, 8, 9, 0, 2, 3];
let res = this.bubbleSortTow(array);
console.log(res);
},
methods: {
bubbleSortTow(arr) {
let low = 0;
let high = arr.length - 1;
while (low < high) {
let mark = true; // Find the maximum value and put it on the rightfor (let i = low; i < high; i++) {
if (arr[i] > arr[i + 1]) {
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
mark = false; } } high--; // Find the minimum value and put it on the leftfor (let j = high; j > low; j--) {
if (arr[j] < arr[j - 1]) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
mark = false; } } low++; console.log(mark); The console. The log (` first${low}Subcycle ', arr);if (mark) returnarr; }}}Copy the code
Performance comparison
The performance of three kinds of sorting algorithms is compared: unidirectional bubble sort performance > bidirectional bubble sort performance > common bubble performance. (Generation time depends on the system used)
prompt
When a large amount of data operation, do not imitate, the page has been stuck.
2. Select sort
Train of thought
Find the minimum or maximum value of the remaining elements and place them at the end or the beginning.
implementation
created() {
let array = [];
for (let i = 0; i < 10; i++) {
let number = Math.floor(Math.random() * 10);
array.push(number);
}
letres = this.selectSort(array); console.log(res); }, methods: {/** * selectSort(arr) {let length = arr.length,
minIndex;
for(let i = 0; i < length -1; i++) {
minIndex = i;
for(let j = i+1; j < length; j++) {
if(arr[j] < arr[minIndex]) { minIndex = j; } } [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; The console. The log (` first${i+1}Subcycle ', arr); }returnarr; }}Copy the code
Performance comparison
For the same amount of data, it is found that unidirectional bubble sort performance > bidirectional bubble sort performance > selection sort > common bubble performance. (Generation time depends on the system used)
prompt
Selection sort is one of the most stable algorithms in terms of time complexity, because the fastest and slowest time complexity are O(n²), the smaller the data amount, the better.
3. Insertion sort
Train of thought
The first element is an ordered array, and subsequent elements are inserted by finding the appropriate element in the ordered array.
implementation
created() {
let array = [];
for (let i = 0; i < 10; i++) {
let number = Math.floor(Math.random() * 10);
array.push(number);
}
letres = this.insertSort(array); console.log(res); }, methods: {/** * insertSort */ insertSort(arr) {let length = arr.length,
preIndex, current;
for (leti = 1; i < length; i++) { preIndex = i - 1; current = arr[i]; // Compare the sorted sequence and insert it in the appropriate positionwhile(preIndex >= 0 && arr[preIndex] > current) { arr[preIndex + 1] = arr[preIndex]; preIndex--; } arr[preIndex + 1] = current; The console. The log (` first${i}Subcycle ', arr); }returnarr; }}Copy the code
Optimization: disassemble half insertion sort implementation
On the basis of direct insertion sort, the method of split search is used to find the position to be inserted, and then the insertion is carried out.
created() {
let array = [];
for (let i = 0; i < 10; i++) {
let number = Math.floor(Math.random() * 10);
array.push(number);
}
letres = this.binsertSort(array); console.log(res); }, methods: {/** * Uninsert sort */ binsertSort(arr) {let low, high, j, temp;
for (let i = 1; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) {
temp = arr[i];
low = 0;
high = i - 1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (temp > arr[mid]) {
low = mid + 1;
} else{ high = mid - 1; }}for(j = i; j > low; --j) { arr[j] = arr[j - 1]; } arr[j] = temp; } the console. The log (` first${i}Subcycle ', arr); }returnarr; }}Copy the code
Performance comparison
>= Indicates that there is little difference in performance
In the case of the same amount of data, it is found that the disassembly insert sort >= unidirectional bubble sort performance > Bidirectional bubble sort performance > Insert sort > Select sort > is greater than the normal bubble performance. (Generation time depends on the system used)
prompt
Insertion sort is not as crudely implemented as bubble sort and selection sort, but its principles are probably the easiest to understand.
4. Hill Sort
Train of thought
Through a certain increment gap, the whole sequence is divided into several groups, and the members of the group are compared and exchanged from the back to the front, and then the increment is gradually reduced to 1. Hill sort is similar to insertion sort, except that the number of forward moves at the beginning is changed from 1 to gap.
implementation
created() {
let array = [];
for (let i = 0; i < 10; i++) {
let number = Math.floor(Math.random() * 10);
array.push(number);
}
letres = this.shellSort(array); console.log(res); }, methods: {/** * sort */ shellSort(arr) {letlen = arr.length; // Initial stepsletgap = parseInt(len / 2); // Gradually reduce the number of stepswhile(gap) {// Start with the gap elementfor (leti = gap; i < len; I++) {// gradually compare and exchange it with other previous group membersfor (let j = i - gap; j >= 0; j -= gap) {
if (arr[j] > arr[j + gap]) {
[arr[j], arr[j + gap]] = [arr[j + gap], arr[j]];
} else {
break; } } } gap = parseInt(gap / 2); }}}Copy the code
Performance comparison
In the case of the same amount of data, it is found that the disassembly insert sort >= unidirectional bubble sort performance > Bidirectional bubble sort performance > Insert sort > Hill sort > Select sort > is greater than the normal bubble performance. (Generation time depends on the system used)
Merge sort
Train of thought
The recursion divides the array into two sequences and merges the two sequences in order. As a typical application of divide and conquer algorithm, merge sort is implemented in two ways:
- Recursion from top to bottom (all recursive methods can be rewritten iteratively, hence method 2).
- Iterate from the bottom up.
implementation
created() {
let array = [];
for (let i = 0; i < 10; i++) {
let number = Math.floor(Math.random() * 10);
array.push(number);
}
letres = this.mergeSort(array); console.log(res); }, methods: {/** * mergeSort */ mergeSort(arr) {let len = arr.length;
if (len < 2) {
return arr;
}
letmiddle = Math.floor(len / 2), left = arr.slice(0, middle), right = arr.slice(middle); Console. log(' process: ', arr);returnthis.merge(this.mergeSort(left), this.mergeSort(right)); }, /** * merge sort helper */ merge(left, right) {let 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());
}
returnresult; }}Copy the code
Performance comparison
In the case of the same amount of data: It is found that the disassembly insert sort >= unidirectional bubble sort performance > Bidirectional bubble sort performance > Insert sort > Hill sort > Merge sort > Select sort > greater than the normal bubble performance. (Generation time depends on the system used)
6. Quicksort
Train of thought
Select an element as the cardinality (usually the first element), place the elements smaller than the cardinality to its left, the elements larger than the cardinality to its right (equivalent to dictation), and recurse the sequence on both sides. Quicksort is a typical application of divide and conquer in sorting algorithms. In essence, quicksort is sort of a recursive divide and conquer on top of bubble sort. The name quicksort is simple, because as soon as you hear the name, you know the meaning of its existence, is fast, and efficient! It’s one of the fastest sorting algorithms for big data.
The worst case of quicksort is O(n ^ 2), for example, quicksort in an ordered sequence. But its amortized expected time is O(n log N), and the constant factor implied in the O(n log N) notation is very small, much smaller than the merge sort whose complexity is stable to O(n log n). Therefore, quicksort is always better than merge sort for most random sequences with weak ordering.
Give an example of
For example, sort the following 10 numbers: 6 1 2 7 9 3 4 5 10 8
- Base on 6 (usually base on the first one)
- In the initial state, the number 6 is the first digit in the sequence. Our goal in the first round is to move 6 to a position (K) such that all the numbers to the left of K are <=6 and all the numbers to the right of K are >=6.
- To find the position of K, we need to perform a search process, looking from right to left for a number greater than 6 at position J, and from left to right for a number less than 6 at position I, interacting the numbers above j and I.
- Continue to move the j and I positions, and repeat 3 steps.
- When j is equal to I, you stop moving, and you move to position K, and you swap the array of position K with 6. Everything to the left of 6 is less than 6, and everything to the right of 6 is greater than 6.
- Appellate the left and right sequences of 6.
More details can be found at blog.csdn.net/qq_40941722…
To achieve 1
created() {
let array = [];
for (let i = 0; i < 10; i++) {
let number = Math.floor(Math.random() * 10);
array.push(number);
}
console.log(array);
letres = this.quickSort(array, 0, array.length - 1); console.log(res); }, methods: {/** * quickSort */ quickSort(arr, begin, end) {if (begin > end) return arr;
let temp = arr[begin],
i = begin,
j = end;
while(i ! = j) {while(arr[j] >= temp && j > i) {
j--;
}
while(arr[i] <= temp && j > i) {
i++;
}
if (j > i) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[begin], arr[i]] = [arr[i], temp];
console.log(`${arr[i]}As a reference point: ', ARR); this.quickSort(arr, begin, i - 1); this.quickSort(arr, i + 1, end);returnarr; }},Copy the code
The 2
created() {
let array = [];
for (let i = 0; i < 10; i++) {
let number = Math.floor(Math.random() * 10);
array.push(number);
}
console.log(array);
letres = this.quickSortOne(array, 0, array.length - 1); console.log(res); }, methods: {/** * quickSortOne(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 = this.partition(arr, left, right);
console.log(`${arr[partitionIndex]}As a reference point: ', ARR); this.quickSortOne(arr, left, partitionIndex - 1); this.quickSortOne(arr, partitionIndex + 1, right); }returnarr; }, /** * quicksort helper - find the base value */ partition(arr, left, right) {let pivot = left,
index = pivot + 1;
for (let i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
[arr[i], arr[index]] = [arr[index], arr[i]];
index++;
}
}
[arr[pivot], arr[index - 1]] = [arr[index - 1], arr[pivot]];
returnindex - 1; }}Copy the code
Performance comparison
In the case of the same amount of data: Found half insertion sort >= unidirectional bubble sort performance > bidirectional bubble sort performance > Insert sort > Hill sort > Merge sort > Selection sort >= Quicksort 1 > Quicksort 2 > greater than normal bubble performance. (Generation time depends on the system used)
Pay attention to
Quick row implementation method 1, although the code looks relatively simple, but in a large amount of data, overflow problems will occur.
7. Heap sort
Train of thought
When it comes to heap sorting, you first need to understand a data structure — the heap. A heap is a complete binary tree, and this structure can usually be represented as an array. In practical application, heap can be divided into minimum heap and maximum heap, the difference between the two is as follows:
-
-max-heap property: A[Parent(I)]≥A[I] for all nodes I except root
-
-min-heap property: A[Parent(I)]≤A[I] for all nodes I except root
Heap sort is a sort of selection that uses the concept of heap to sort. There are two methods:
- Large top heap: the value of each node is greater than or equal to the value of its children, used for ascending sorting in heap sorting algorithms
- Small top heap: the value of each node is less than or equal to the value of its children and is used in descending order in heapsort algorithms
implementation
created() {
let array = [];
for (let i = 0; i < 10; i++) {
let number = Math.floor(Math.random() * 10);
array.push(number);
}
console.log(array);
letres = this.quickSortOne(array, 0, array.length - 1); console.log(res); }, methods: {/** * heapSort(nums) {this.buildheap (nums); // Loop n-1 times, swapping the elements at the top and bottom of the heap and rearranging the heap structure after each loopfor (let i = nums.length - 1; i > 0; i--) {
[nums[i], nums[0]] = [nums[0], nums[i]];
this.adjustHeap(nums, 0, i);
console.log(`${nums[i]}As a heap-top element: ', nums); }returnnums; }, /** * heapsort helper method */ adjustHeap(nums, index, size) {// The heap structure may be broken after the swap, so you need to loop so that each parent is larger than the left and right nodeswhile (true) {
let max = index;
letleft = index * 2 + 1; / / the left nodeletright = index * 2 + 2; / / right nodeif (left < size && nums[max] < nums[left]) max = left;
if(right < size && nums[max] < nums[right]) max = right; // If the left and right nodes are larger than the current nodes, then switch the left and right nodes, and loop again to determine if the left and right nodes are smaller than the current nodes.if(index ! == max) { [nums[index], nums[max]] = [nums[max], nums[index]]; index = max; }else {
break; }, /** * buildHeap(nums) {// Note that the head node starts at 0, so the last non-leaf node is parseInt(nums.length/2)-1let start = parseInt(nums.length / 2) - 1;
letsize = nums.length; // Start from the last non-leaf until you reach the top of the heap.for (leti = start; i >= 0; i--) { this.adjustHeap(nums, i, size); }}}Copy the code
Performance comparison
In the case of large amount of data and small amount of data are not used, the relative performance of heap sort sort table movement is relatively large. In its own right, although heapsort is not commonly used in practice and is often beaten by quicksort’s efficiency, the advantage of heapsort is that it is independent of the input data and its time complexity is stable at O(N*lgN), unlike quicksort, which is O(N2) in the worst case.
8. Counting sort
Train of thought
Take the element value of the array as the key, store the number of occurrences as the value of a temporary array, and then iterate through the temporary array to restore the original array. Because JavaScript’s array subscripts are stored as strings, count sort can be used to arrange negative numbers, but not decimals.
The core of counting sort is to convert input data values into keys that are stored 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.
implementation
created() {
let array = [];
for (let i = 0; i < 10; i++) {
let number = Math.floor(Math.random() * 10);
array.push(number);
}
console.log(array);
letres = this.countingSort(array); console.log(res); }, methods: {/** * countingSort(nums) {let arr = [];
letmax = Math.max(... nums);letmin = Math.min(... nums); / / barrelfor (let i = 0, len = nums.length; i < len; i++) {
lettemp = nums[i]; arr[temp] = arr[temp] + 1 || 1; Console. log(' bucket key is${temp}- the value of${arr[temp]}`, arr);
}
letindex = 0; // Restore the original arrayfor (let i = min; i <= max; i++) {
while(arr[i] > 0) { nums[index++] = i; arr[i]--; }}returnnums; }}Copy the code
Performance comparison
In the case of the same amount of data: Found half insertion sort >= unidirectional bubble sort performance > bidirectional bubble sort performance > Insert sort > Count sort > Hill sort > Merge sort > Selection sort >= Quicksort 1 > Quicksort 2 > > common bubble performance. (Generation time depends on the system used)
9. Bucket sort
Train of thought
Take n buckets, confirm the number interval of each bucket according to the maximum and minimum values of the array, insert the elements of the array into the corresponding buckets, and finally merge the buckets.
Bucket sort is an updated version of counting sort. It uses the mapping of functions, and the key to efficiency lies in the determination of this mapping function. To make bucket sorting more efficient, we need to do these two things:
- Maximize the number of buckets if there is enough extra space.
- The mapping function used can evenly distribute N input data into K buckets.
When is the Best: when the input data can be evenly distributed to each bucket
When is the slowest: when input data is allocated to the same bucket
implementation
created() {
let array = [];
for (let i = 0; i < 10; i++) {
let number = Math.floor(Math.random() * 10);
array.push(number);
}
console.log(array);
letres = this.bucketSort(array); console.log(res); }, methods: {/** * bucketSort */ bucketSort(nums) {// number of buckets, as long as it is positivelet num = 5;
letmax = Math.max(... nums);letmin = Math.min(... nums); // Calculate the value range of each bucket, at least 1,letrange = Math.ceil((max - min) / num) || 1; // Create a two-dimensional array, with the first dimension representing the number of buckets and the second dimension representing the number of bucketsletarr = Array.from(Array(num)).map(() => Array().fill(0)); Nums.foreach (val => {// Calculate which bucket elements should be distributed inletindex = parseInt((val - min) / range); 5 index = index >= num? num - 1 : index;lettemp = arr[index]; // Insert sort, which inserts the elements into the bucket in orderlet j = temp.length - 1;
while(j >= 0 && val < temp[j]) { temp[j + 1] = temp[j]; j--; } temp[j + 1] = val; console.log(temp); }); // Change back to the original arraylet res = [].concat.apply([], arr);
nums.forEach((val, i) => {
nums[i] = res[i];
});
returnnums; }}Copy the code
Performance comparison
In the case of the same amount of data: Found half insertion sort >= unidirectional bubble sort performance > Bidirectional bubble sort performance > Insert sort > Count sort > Bucket sort > Hill Sort > Merge sort > Selection sort >= Quicksort 1 > Quicksort 2 > greater than normal bubble performance. (Generation time depends on the system used)
10. Radix sort
Train of thought
Using ten buckets 0 to 9, loop the maximum number of bits by putting each number in the bucket from the lowest to the highest. But you can only arrange positive integers, because you can’t compare the minus sign with the decimal point.
There are two ways to sort radix:
- MSD is sorted from the top
- LSD is sorted from low order
Radix sort vs counting sort vs bucket sort:
These three sorting algorithms all make use of the concept of buckets, but there are significant differences in the way buckets are used:
- Radix sort: Buckets are allocated according to each digit of the key value
- Count sort: Stores only a single key value per bucket
- Bucket sort: Each bucket stores a range of values
implementation
created() {
let array = [];
for (let i = 0; i < 10; i++) {
let number = Math.floor(Math.random() * 10);
array.push(number);
}
console.log(array);
letres = this.radixSort(array); console.log(res); }, methods: {/** * radixSort */ radixSort(nums) {// calculate bitsfunction getDigits(n) {
let sum = 0;
while (n) {
sum++;
n = parseInt(n / 10);
}
returnsum; } // The first dimension represents the number of bits (0 to 9), and the second dimension represents the value stored in itlet arr = Array.from(Array(10)).map(() => Array());
letmax = Math.max(... nums);let maxDigits = getDigits(max);
for (leti = 0, len = nums.length; i < len; I ++) {// Fill every number with the same number of digits with 0 nums[I] = (nums[I] +' ').padStart(maxDigits, 0); // First put each number in the corresponding bucket according to the units digitlettemp = nums[i][nums[i].length - 1]; arr[temp].push(nums[i]); } console.table(arr); // Loop to judge each bitfor (leti = maxDigits - 2; i >= 0; I --) {// loop each bucketfor (let j = 0; j <= 9; j++) {
let temp = arr[j]
letlen = temp.length; // Put the number of buckets into the corresponding bucket according to the current bit Iwhile (len--) {
letstr = temp[0]; temp.shift(); arr[str[i]].push(str); }}} // Change back to the arraylet res = [].concat.apply([], arr);
nums.forEach((val, index) => {
nums[index] = +res[index];
});
returnnums; }}Copy the code
Performance comparison
In the case of the same amount of data: Found half insertion sort >= unidirectional bubble sort performance > Bidirectional bubble sort performance > Insert sort > Count sort > Bucket sort > Hill Sort > Radix Sort > Merge sort > Selection sort >= Quicksort 1 > Quicksort 2 > > common bubble performance. (Generation time depends on the system used)
