1. arr.sort(fn)
// Sort in ascending order
arr.sort((a, b) => a - b);
// Sort in descending order
arr.sort((a, b) => b - a);
2. Bubble sort
Bubble sort-ascending order principle:
eg: [1, 6, 7, 9, 10, 3, 4, 5, 2]
1) First traverse the array for the first time. If the previous number is greater than the next number, the positions are swapped. The final maximum value 10 is placed at the end of the array. At this time, it is [1, 6, 7, 9, 3, 4, 5, 2 , 10];
for (let j = 0; j < arr.length-1; j + + ) {
preNum = arr[j];
const nextNum = arr[j + 1];
if (preNum > nextNum) { // The number on the left is greater than the number on the right, swap positions
// Move the smaller numbers forward, move the larger numbers backward
arr[j] = nextNum;
arr[j + 1] = preNum;
}
}
2) The second pass is: if the previous number is greater than the next number, the positions are swapped, and finally the second largest value is placed in the penultimate position of the array. This time it is [1, 6, 7, 3, 4, 5, 2, 9, 10];
for (let j = 0; j < arr.length-2; j + + ) {
preNum = arr[j];
const nextNum = arr[j + 1];
if (preNum > nextNum) { // The number on the left is greater than the number on the right, swap positions
// Move the smaller numbers forward, move the larger numbers backward
arr[j] = nextNum;
arr[j + 1] = preNum;
}
}
3) The third pass is: if the previous number is greater than the next number, the positions are swapped. Finally, the third largest value is placed in the third to last position of the array. At this time, it is [1, 6, 3, 4, 5, 2, 7, 9, 10];
for (let j = 0; j < arr.length-3; j + + ) {...}
And so on…
4) The last pass: If the previous number is greater than the next number, the positions are swapped. Finally, the second smallest value is placed at the second position of the array. This time it is [1, 2, 3, 4, 5, 6, 7, 9 , 10]
for (let j = 0; j < 1; j + + ) {...}
5) Because for (let j = 0; j < x; j + + ) {...}; it can be deduced that the value range of x is (0, arr.length-1];
so:
for (let j = arr.length – 1; i > 0; i–) {
for (let j = 0; j < i; j + + ) {...}
}
?
Sorting.js:14 First calculation:
- (9) [1, 6, 7, 9, 3, 4, 5, 2, 10]
Sorting.js:14 Second calculation:
- (9) [1, 6, 7, 3, 4, 5, 2, 9, 10]
Sorting.js:14 The third calculation:
- (9) [1, 6, 3, 4, 5, 2, 7, 9, 10]
Sorting.js:14 The 4th calculation:
- (9) [1, 3, 4, 5, 2, 6, 7, 9, 10]
Sorting.js:14 The 5th calculation:
- (9) [1, 3, 4, 2, 5, 6, 7, 9, 10]
Sorting.js:14 The 6th calculation:
- (9) [1, 3, 2, 4, 5, 6, 7, 9, 10]
Sorting.js:14 The 7th calculation:
- (9) [1, 2, 3, 4, 5, 6, 7, 9, 10]
Sorting.js:14 The 8th calculation:
- (9) [1, 2, 3, 4, 5, 6, 7, 9, 10]
No need to calculate for the last time, the minimum value is 1
[1, 2, 3, 4, 5, 6, 7, 9, 10]
Bubble sorting–ordinary double-level traversal loop version:
//Bubble sort-ascending order
const bubbleSort = (arr) => {
let preNum = null;
//The reason i>0 is because when the sorting interaction positions reach the last two, it only needs to be compared once, and the last number does not need to be compared.
for (let i = arr.length - 1; i > 0; i--) {
for (let j = 0; j < i; j + + ) {
preNum = arr[j];
const nextNum = arr[j + 1];
if (preNum > nextNum) { // The number on the left is greater than the number on the right, swap positions
// Move the smaller numbers forward, move the larger numbers backward
arr[j] = nextNum;
arr[j + 1] = preNum;
}
}
}
return arr;
}
// Bubble sort-descending order
const bubbleSort = (arr) => {
let preNum = null;
//The reason i>0 is because when the sorting interaction positions reach the last two, it only needs to be compared once, and the last number does not need to be compared.
for (let i = arr.length - 1; i > 0; i--) {
for (let j = 0; j < i; j + + ) {
preNum = arr[j];
const nextNum = arr[j + 1];
if (preNum < nextNum) { // The number on the left is smaller than the number on the right, swap positions
//Move the larger numbers forward, and move the smaller numbers backward.
arr[j] = nextNum;
arr[j + 1] = preNum;
}
}
}
return arr;
}
Bubble sort-ascending-recursive
//Bubble sort-ascending order
const bubbleSort0 = (arr, i = arr.length - 1) => {
let preNum = null;
//The reason i>0 is because when the sorting interaction positions reach the last two, it only needs to be compared once, and the last number does not need to be compared.
for (let j = 0; j < i; j + + ) {
preNum = arr[j];
const nextNum = arr[j + 1];
if (preNum > nextNum) { // The number on the left is greater than the number on the right, swap positions
// Move the smaller numbers forward, move the larger numbers backward
arr[j] = nextNum;
arr[j + 1] = preNum;
}
}
i--;
if (i > 0) return bubbleSort0(arr, i);
return arr
}
// Bubble (ascending sort)
var arr = bubbleSort0([1, 6, 7, 9, 10, 3, 4, 5, 2])
console.log(arr, 'Bubble sort-ascending-recursive');
// Bubble sort - descending order
const bubbleSort0 = (arr, i = arr.length - 1) => {
let preNum = null;
//The reason i>0 is because when the sorting interaction positions reach the last two, it only needs to be compared once, and the last number does not need to be compared.
for (let j = 0; j < i; j + + ) {
preNum = arr[j];
const nextNum = arr[j + 1];
if (preNum < nextNum) { // The number on the left is smaller than the number on the right, swap positions
//Move the larger numbers forward, and move the smaller numbers backward.
arr[j] = nextNum;
arr[j + 1] = preNum;
}
}
i--;
if (i > 0) return bubbleSort0(arr, i);
return arr
}
// Bubble (descending order)
var arr = bubbleSort0([1, 6, 7, 9, 10, 3, 4, 5, 2])
console.log(arr, 'Bubble sort-ascending-recursive');
3. Selection sort
eg: [6, 7, 9, 10, 3, 4, 5, 2, 1]
When i equals 0:
1) min=the first element 6, compared with the rest of the elements in the array, the original first element 6 is exchanged with the first element 3 that is smaller than 6 in if (nextNum < preNum){...} The position at this time is [3, 7, 9, 10, 6, 4, 5, 2, 1];
2) min becomes 3, and the first element smaller than 3 is 2, which is [2, 7, 9, 10, 6, 4, 5, 3, 1];
3) min becomes 2, and the element smaller than 2 is 1, so the positions are swapped, this time it is [1, 7, 9, 10, 6, 4, 5, 3, 2];
5) Counting to the right, there is no element smaller than 1, end
When i equals 1:
1) min=The second element of the array is 7, compared with the third and subsequent elements, the first element smaller than 7 is 6, swap positions, now it is: [1, 6, 9, 10, 7, 4, 5, 3, 2];
2) min becomes 6, and the first element smaller than 6 is 4, which is [1, 4, 9, 10, 7, 6, 5, 3, 2];
3) min becomes 4, and the first element smaller than 4 is 3, which is [1, 3, 9, 10, 7, 6, 5, 4, 2];
4) min becomes 3, and the first element smaller than 3 is 2, which is [1, 2, 9, 10, 7, 6, 5, 4, 3];
5) Counting to the right, there is no element smaller than 2, end
When i equals 2:
1) min is equal to the third element of the array, 9. Compared with the fourth and subsequent elements, the first element smaller than 9 is 7, which is [1, 2, 7, 10, 9, 6, 5, 4, 3];
2) min becomes 7, and the first element smaller than 7 is 6, which is [1, 2, 6, 10, 9, 7, 5, 4, 3];
3) min becomes 6, and the first element smaller than 7 is 5, which is [1, 2, 5, 10, 9, 7, 6, 4, 3];
4) min becomes 5, and the first element smaller than 7 is 4, which is [1, 2, 4, 10, 9, 7, 6, 5, 3];
5) min becomes 4, and the first element smaller than 4 is 3, which is [1, 2, 3, 10, 9, 7, 6, 5, 4];
5) Counting to the right, there is no element smaller than 3, end
And so on…
so:
// The smaller ones move further and further to the left, and so on.
/**
*Select sort:
Principle: Select the smallest current element for each position;
* For example, select the smallest one for the first position, select the second smallest one for the second element among the remaining elements, and so on.
* Until the n-1th element, the nth element does not need to be selected because it is the only largest element left.
* The essence of selection sorting: Every big loop is to select the smallest value. You can record the process of selecting the smallest value by subscripting
* You can also exchange values every time
*/
Selection sort-double-level traversal version:
//Select sort-ascending order
const selectSort = arr => {
const len = arr.length;
for (let i = 0; i < len; i + + ) {
let min = arr[i];
for (let j = i + 1; j < len; j + + ) {
const nextNum = arr[j];
const preNum = min;
// If the current value is smaller than the minimum recorded value, swap the positions of these two numbers.
if (nextNum < preNum) {
arr[j] = preNum;
min = nextNum; // min is assigned the smaller value compared
continue;
}
}
arr[i] = min; // Because min was modified in the inner loop, the value of arr[i] should be modified in its own loop body after jumping out of the inner loop.
}
return arr
}
//Select (sort in ascending order)
var arr = selectSort([6, 7, 9, 10, 3, 4, 5, 2, 1])
console.log(arr, 'Select sort-ascending');
Selection sort-recursion + for loop
//Select sort
const selectSort0 = (arr, i=0) => {
const len = arr.length;
let min = arr[i];
for (let j = i + 1; j < len; j + + ) {
const nextNum = arr[j];
const preNum = min;
console.log(preNum, 'preNum======')
// If the current value is smaller than the minimum recorded value, swap the positions of these two numbers.
if (nextNum < preNum) {
arr[j] = preNum;
min = nextNum; // min is assigned the smaller value compared
continue;
}
}
arr[i] = min; // Because min was modified in the inner loop, the value of arr[i] should be modified in its own loop body after jumping out of the inner loop.
i + + ;
if(i<=2) selectSort0(arr, i);
return arr
}
//Select (sort in ascending order)
var arr = selectSort0([6, 7, 9, 10, 3, 4, 5, 2, 1])
console.log(arr, 'Select sort-ascending order 00000');
4. Quick sort:
If the number of elements in the array is less than 2, return the original array;
If the number of array elements is greater than or equal to 2:
1) flag = a ruler element (usually the first element); left = an array composed of elements to the left of flag (initialization); right = an array composed of elements to the right of flag (initialization);
2) Traverse arr, push values smaller than flag into the left array, push values larger than flag into the right array
3) Perform the above steps (1) and (2) on the left and right arrays
4) Use concat to splice left array, flag, right array
Quick sort-for loop + recursion + concat
//Quick sort
const quickSort = (arr) => {
const len = arr.length;
if (len < 2) {
return arr;
}
//Select ruler element
let flag = arr[0];
let left = [];
let right = [];
let preNum = null;
// Because flag takes the element with subscript 0, the traversal starts from subscript 1
for (let i = 1; i < len; i + + ) {
preNum = arr[i];
if (preNum < flag) {
// Place smaller than flag on the left
left.push(preNum);
}
else {
// Place the one larger than the flag on the right
right.push(preNum);
}
}
// do recursion
return quickSort(left).concat(flag, quickSort(right));
}
Quick sort-divide and exchange in-place
// Quick sort in-place (exchange)--divide and exchange sort:
const quickInPlaceSort = (arr) => {
//The array specifies two positions for value exchange
let exchange = (arr, i, j) => {
const preNum = arr[i];
const nextNum = arr[j];
arr[i] = nextNum;
arr[j] = preNum;
}
//Complete a division and exchange
let findCenter = (arr, leftIdx, rightIdx) => {
let flag = arr[leftIdx];
let centerIdx = leftIdx + 1;
for (let i = centerIdx; i <= rightIdx; i + + ) {
if (arr[i] < flag) {
exchange(arr, centerIdx, i); //Exchange positions
centerIdx + + ; // swapped subscript + 1
}
}
exchange(arr, leftIdx, centerIdx - 1);
return centerIdx;
}
// recursive sorting
let sort = (arr, leftIdx, rightIdx) => {
if (leftIdx < rightIdx) {
let center = findCenter(arr, leftIdx, rightIdx);
sort(arr, leftIdx, center - 1);
sort(arr, center, rightIdx);
}
}
sort(arr, 0, arr.length - 1);
return arr;
}
var arr = quickInPlaceSort([1, 6, 7, 9, 10, 3, 4, 5, 2]);
console.log(arr, 'Quick sort-ascending order-partition exchange'); // [1, 2, 3, 4, 5, 6, 7, 9, 10] 'Quick sort-ascending order-partition exchange' '
console.log('----------------------------------------') ;