The so-called sorting algorithm, namely through a specific algorithm to factor a group or groups of data in accordance with the established pattern to reorder. The new sequence follows certain rules and reflects certain rules. Therefore, the processed data is easy to be screened and calculated, which greatly improves the calculation efficiency. For sorting, we first require it to have a certain stability, that is, when two identical elements appear in a sequence at the same time, after a certain sorting algorithm, the relative position of the two does not change before and after sorting. In other words, even if two elements are exactly the same, they are different in the sorting process, and there is no room for confusion.
Bubble sort
Bubble sort is an entry-level algorithm, but it has some interesting gameplay. In general, there are three ways to write bubble sort:
Compare and switch back, bubbling the Max/min to the last bit; Optimized writing method: a variable is used to record whether the current round of comparison has been exchanged. If no exchange has occurred, it indicates that the order has been ordered and the order is no longer continued.
Based algorithm
The space is O(1)O(1)O(1), and the time is O(n2)O(n^2)O(n2).
const sort = (arr) = > {
for (let i = 0, len = arr.length; i < len-1; i++){
for (let j = 0; j < len-1-i; j++) {
if (arr[j] > arr[j+1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]; }}}return arr
}
Copy the codeAfter each round of the outermost for loop, the largest of the remaining digits is moved to the last digit of the current round, and some neighboring digits are exchanged to become ordered along the way. The total number of comparisons is (n-1)+(n-2)+(n-3)+… + 1 (n – 1) + (n – 2) + (n – 3) +… + 1.
The second writing method is improved on the basis of the basic algorithm:
const sort = (arr) = > {
for (let i = 0, len = arr.length; i < len - 1; i++) {
let isSwap = false
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
isSwap = true}}if(! isSwap) {break; }}return arr;
};
Copy the codeThe space complexity is O(1)O(1)O(1); O(n2)O(n^2)O(n2)- preferably O(n);
After each round of the outermost for loop, the maximum of the remaining digits is still moved to the last digit of the current round. The advantage of this writing over the first is that if no exchange occurs in a round of comparison, the ordering stops immediately, since the remaining numbers must already be in order.
Selection sort
The idea of selection sort is: double loop through the number group, after each round of comparison, find the subscript of the smallest element, and exchange it to the first place.
Based algorithm
const sort = (arr) = > {
for (let i = 0, len = arr.length; i < len - 1; i++) {
let minIndex = i
for (let j = i+1; j < len; j++) {
if (arr[i] > arr[j]) {
minIndex = j
}
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
};
Copy the codeBinary selection sort – optimization
The selection sorting algorithm can also be optimized, since we found the minimum value in each round, why not find the maximum value by the way? That’s the idea of binary choice sort.
Using binary selection sort, which records the minimum and maximum values for each selection round, can double the size of the array that needs to be traversed.
const sort = (arr) = > {
for (let i = 0, len = arr.length; i < len / 2; i++) {
let minIndex = i;
let maxIndex = i;
for (let j = i + 1; j < len-i; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
if(arr[maxIndex] < arr[j]) { maxIndex = j; }}if (minIndex === maxIndex) break;
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
if (maxIndex === i) {
maxIndex = minIndex;
}
const lastIndex = len - i - 1;
[arr[maxIndex], arr[lastIndex]] = [arr[lastIndex], arr[maxIndex]];
}
return arr;
};
Copy the codeInsertion sort
The idea of insertion sort is very simple, there is a very common scene in life: in playing poker, we draw cards while sorting cards, every time a card, it will be inserted into the hand of the existing cards in the appropriate position, gradually complete the whole sort.
Insertion sort can be written in two ways:
- Exchange method: In the process of inserting new numbers, constantly exchange with the previous numbers until they find their proper position.
- Moving method: in the process of inserting a new number, the number in front is constantly compared with the previous one, and the number in front is constantly moving out of the position. When the new number finds its position, it can be inserted once.
Commutative insertion sort
const sort = (arr) = > {
for (let i = 1, len = arr.length; i < len; i++) {
let j = i;
while (j >= 1 && arr[j] < arr[j - 1]) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
j--
}
}
return arr;
};
Copy the codeWhen the number is less than two, there is no sorting problem, and of course there is no insertion, so we just start with the second number and insert it forward.
Mobile method
And what we found is that in commutative insertion sort, you swap numbers every time. But in practice, the newly inserted number does not necessarily fit where the number it is swapped with is. In other words, soon after it is switched to the new position, after the next comparison, if it needs to be switched again, it will immediately be switched back to the previous position.
From this, we can think of an optimal solution: let the newly inserted number be compared first, and the first larger number move backward until it finds a position suitable for the new number.
In this scenario we need to temporarily store the newly inserted number as follows:
const sort = (arr) = > {
for (let i = 1, len = arr.length; i < len; i++) {
let j = i-1;
let cur = arr[i];
while (j >= 0 && cur < arr[j]) {
arr[j+1] = arr[j]
j--;
}
arr[j+1] = cur
}
return arr;
};
Copy the code