- Insertion sort: The most common sort algorithm iterates from the element with subscript 1 in the array. Take the current element and compare it to all previous elements. If the current element is less than the previous element, swap places, otherwise break out of the loop.
The animation is shown as follows:
The code is as follows:
function sort(array) {
let arg = array.slice(0); // Copy elements to avoid contaminating the original array
for (let i = 1; i < arg.length; i++) {
let j = i
while (j > 0) {
if (arg[j] < arg[j - 1]) {
let temp = arg[j]
arg[j] = arg[j - 1]
arg[j - 1] = temp
j--
} else {
break}}}return arg;
}
Copy the code- Binary lookup: The premise is that the array is ordered. 1. Search for the middle element of an ordered array. If it is equal to the middle element, return the index. 2. If the specified element is greater than or less than the intermediate element, search for the greater than or less than half of the region, and repeat the first step until the target element is found. If no one is found, -1 is returned
The code is shown as follows:
function sort(array, target) {
let i = 0;
let len = array.length - 1;
let mid;
while (i <= len) {
mid = Math.floor((len + i) / 2)
if (array[mid] == target) {
return mid
} else if (array[mid] < target) {
i = mid + 1
} else {
len = mid - 1}}return -1
}
console.log(sort([10.12.14.18.19].10))
Copy the code- Binary insertion sort:
Before each insertion operation, adopt the binary search method described above. To find the location of the insert, and then insert element (insert) to move again after first if you don’t understand you can refer to b station video: www.bilibili.com/video/BV1iE…
The code is as follows:
function binaryInsertSort(arr) {
var i, cur, left, right, mid;
for (i = 1; i < arr.length; i++) {
left = 0;
right = i - 1;
cur = arr[i];
while (left <= right) {
mid = Math.floor((left + right) / 2);
if (cur < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
arr.splice(left, 0, arr.splice(i, 1) [0]);
}
return arr;
}
binaryInsertSort([10.12.14.18.1])
Copy the code- Hill sorting
The graphic explanation is clearer as follows:
function shellSort(arr) {
let len = arr.length;
// gap is an increment
for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (let i = gap; i < len; i++) {
let j = i;
let current = arr[i];
while (j - gap >= 0 && current < arr[j - gap]) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = current;
console.log(arr)
}
}
}
shellSort([15.4.1.32.33.5]);
Copy the code- Bubble sort
1. Compare two adjacent elements, and if the former is larger than the latter, swap places. 2. After the first round of comparison, the last element is the largest. 3. The last element is the largest, so the last element does not need to compare sizes. The code is as follows:
function shellSort(arr) {
for (let j = 0; j < arr.length - 1; j++) {
for (let i = 0; i < arr.length - j - 1; i++) {// Because there is no need to compare the last digit
if (arr[i] > arr[i + 1]) {
let temp = arr[i]
arr[i] = arr[i + 1]
arr[i + 1] = temp
}
}
}
return arr
}
shellSort([15.4.1.10.33.5]);
Copy the code- Selection sort
Defining a minimum minIndex initializer is the first, iterating through the set of numbers to find the transposition position smaller than minIndex, and continuing through the elements after I +1
function shellSort(arr) {
for (let i = 0; i < arr.length; i++) {
let minIndex = i
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j
}
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
}
console.log(arr)
}
console.log(shellSort([15.4.1.10.33.5]));
Copy the code- Merge sort
The implementation idea is shown in the figure below. (I always think that there is no need to divide and conquer, but only need to merge. Maybe the code is not easy to write, so divide and conquer.)
Js code implementation:
function mergeSort(arr) {
let len = arr.length
if (len < 2) {
return arr
}
let middle = Math.floor(len / 2)
// Split into two subarrays
let left = arr.slice(0, middle)
let right = arr.slice(middle, len)
// recursive split
let mergeSortLeft = mergeSort(left)
let mergeSortRight = mergeSort(right)
/ / merge
return merge(mergeSortLeft, mergeSortRight)
}
const merge = (left, right) = > {
const result = [];
while (left.length && right.length) {
// Note: the judgment condition is less than or equal to, if only less than, then the sorting will be unstable.
if (left[0] <= right[0]) {
result.push(left.shift()); // Remove the first element from left or right and add it to result
} else{ result.push(right.shift()); }}// Add the remaining elements
while (left.length) result.push(left.shift());
while (right.length) result.push(right.shift());
return result;
};
console.log(mergeSort([15.4.15.10.33.5]));
Copy the code- Quick sort
The principle is simple: take the first element of the array and make it the middle element (theoretically any element). Loop through the list of numbers, placing those greater than the middle element to the right and those less than or equal to the middle element to the left. Repeat the above steps until the array length is 0. The sorting method another describes can refer to the following link: www.bilibili.com/video/BV1at… The js code is as follows:
function sort(arr) {
if (arr.length < 1) {
return arr
}
let mid = arr.shift()
let left = [],
right = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] > mid) {
right.push(arr[i])
} else {
left.push(arr[i])
}
}
return sort(left).concat(mid, sort(right))
}
console.log(sort([5.4.11.2.1]));
Copy the code- Counting sort (not comparing sort)
How it works: first get the maximum value of the array, create an array whose length is the maximum value +1 and fill it with 0 (called the statistical array). The number of occurrences of each value is iterated over (length is the length of the statistical array). If the count of a nested loop is greater than zero (for repeating elements), add it to the new array.
function sort(arr) {
let max = Math.max.apply(null, arr)
let arg = new Array(max + 1).fill(0) // Count arrays
let array = [];
for (let i = 0; i < arr.length; i++) {
let idx = arr[i]
arg[idx]++
}
for (let h = 0; h < max + 1; h++) {
for (let k = arg[h]; k > 0; k--) { array.push(h); }}console.log(array)
}
sort([0.5.5.5.77.1.8.7])
Copy the code