“This is the first day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021”
How w does sorting ™ have so many kinds? Why learn algorithms? Aside from a bunch of elaborate reasons, perhaps the most realistic one is that… The front end is too ™ volume, big factories are interviewing algorithms, you have to follow the volume.
Selection sort
Selection is to arrays into order and disorder, will first as a minimum, disorderly array traversal disorderly array, compared with the minimum value, if is smaller than the current setting the minimum, as a minimum, after the loop will be the minimum and disorderly array first exchange, orderly array length + 1, disorderly array length 1, cycling, until a disorderly array length is zero. The core is to select a minimum value from an unordered array
For example, the array [1,3,4,8,2,5,7] is sorted from smallest to largest, as in the following examples
Treat [] as an ordered array and [1,3,4,8,2,5,7] as an unordered array
Step 1: loop the minimum value of unordered array is 1 and place it at the end of the ordered array. The length of the unordered array is reduced by one. The ordered array is [1] and the unordered array is [3,4,8,2,5,7].
Step 2: loop the minimum value of unordered array is 2, same as above, ordered array is [1,2], unordered array is [3,4,8,5,7]
.
After N loops, the array sort is complete, and the code is as follows:
function selectSort(arr) {
const len = arr.length;
if (len <=1 ) return arr
let minIndex, temp;
// go through N times
for (let i=0; i<len-1; i++) {// Iterate over the unordered array, taking the first digit of the array as the minimum value, and then compare it to fetch the minimum subscript
minIndex = i;
for (let j=i+1; j<len; j++) {if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
temp = arr[i]
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr
}
Copy the codeThe time complexity of this algorithm is O(n²) and the space complexity is O(1). Because selection sort requires swapping in an unordered array, it is unstable sort
Insertion sort
Core of insertion sort is inserted, also like the selection sort, an array can be divided into ordered arrays and disorder, the difference is that he is a disorderly array first inserted into the orderly array of appropriate location, and the position of orderly array unified mobile a back, continue to traverse a disorderly array until disorderly array length is zero. The core algorithm is to find the right place in an ordered array
Array [1,3,4,8,2,5,7]
Initially, we treat [1] as an ordered array and [3,4,8,2,5,7] as an unordered array
Finally, the ordered array becomes [1,3], and the unordered array is [4,8,2,5,7].
Insert the first digit 4 into the ordered array [1,3,4] and the unordered array [8,2,5,7].
Step 3: same as above, ordered array is [1,3,4,8], unordered array is [2,5,7]
First step 4: disorderly array to 2, then need to find the orderly array in the appropriate location, from the last an orderly array traversal, if the value is greater than 2, the move followed a, the second from bottom in an orderly array, cycles, until the order has a value in the array is less than 2, because the number greater than 2 are moved back a, will be placed directly on the current location, 2: Ordered arrays are [1,2,3,4,8] and unordered arrays are [5,7]
.
The code is as follows:
function insertSort(arr) {
const len = arr.length;
if (len <= 1) return arr;
for (let i=1; i<len; i++) {const value = arr[i];
let j=i-1;
for(; j>=0; j--) {if (arr[j] > value) {
arr[j+1] = arr[j]
} else {
break;
}
}
arr[j+1] = value;
}
return arr;
}
Copy the codeThe time complexity of this algorithm is O(n²), and the space complexity is O(1). Because it inserts the unordered array after the ordered array, it does not disturb the sequence relation of the unordered array’s equivalence, so it is stable sorting
Bubble sort
Bubble, bubble sort, of course, the core is how bubble, we put the array from the first beginning, let two adjacent data comparison, according to the relationship between the size of exchange or exchange, continue to back, until all the data exchange of two adjacent to complete, at this time of the maximum (or minimum) have to array the tail, as from a location in the array bubbling to the tail. We do this N times (N= array length) and the array is sorted.
Array [1,3,4,8,2,5,7]
First loop: Compare 1 with 3, do not swap, compare 3 with 4, do not swap, and so on, until 8 is compared with 2, the two are swapped, and the array becomes [1,3,4,2,8,5,7]. Then swap 8 with 5, and become [1,3,4,2,5,8,7]. Then swap 8 with 7, and get the result of the first loop.
.
Do this N times, and the code is as follows:
function bubbleSort(arr) {
const len = arr.length;
if (len <= 1) return arr;
for (let i = 0; i < len -1; i++) {// Indicates whether there is an element exchange in this loop. If not, there is no need to continue the loop
let flag = false;
// The required bubble length decreases as the loop value increases
for (let j = 0; j < len - 1- i; j++) {if (arr[j] > arr[j+1]) {
const temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
flag = true; }}if(! flag)break;
}
return arr
}
Copy the codeThe time complexity of this algorithm is O(n²), space complexity is O(1), because bubble sort is commutative sort, if two values are equal, there is no need to swap, so it is stable sort
Quick sort
Quicksort uses the idea of divide-and-conquer, taking a random value from an unordered array as the pivot point, placing the value less than pivot on the left side of the array, and the value greater than Pivot on the right side of the array. Then, using the idea of recursion, sort the left and right arrays until the length of the partition is 1, and the array is sorted.
For example, with the array [1,3,4,8,2,5,7], we take the middle of the array as pivot
The array smaller than pivot is [1,3,4,2,5,7] on the left, [8] in the middle, and [] on the right
Continue to partition the left, take 4 as pivot, divide into [1,3,2], [4], [5, 7], and continue
Quick_sort (L,r) = quick_sort(L, pivot – 1) + [pivot] + quick_sort(pivot + 1, r)
The termination condition is l >= r
The code is as follows:
funciton quickSort(arr) {
const len = arr.length;
if (len <= 1) return arr;
// Take the pivot point as the pivot point. You can also take the value of the head position and the end position. There are no hard and fast conditions
const pivotIndex = Math.floor(len/2);
// Remove the pivot from the array, with the array length -1
const pivot = arr.splice(pivotIndex, 1) [0];
const left = [], right = [];
for (let i = 0; i < len -1; i++) {if (arr[i] < pivot) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return sortArray(left).concat([pivot], sortArray(right))
}
Copy the codeThe problem with this algorithm is that it has a high space complexity, and each partition creates a new array. We can reduce the space complexity to O(1) by sorting in place. If we want to sort in place, we use a method similar to selection sort to divide the left and right arrays so that the left array is smaller than pivot and the right array is larger than Pivot. We need to pass the array and optimize:
function quickSort(arr) {
const len = arr.length;
if (len <= 1) return arr;
quick_sort(arr, 0, len -1)}function quick_sort(A, l, r) {
if (l >= r) return;
// Take the last number as pivot
const pivot = A[r];
let i=l,j=l;
// Divide the array into ordered and unordered arrays, I as the delimiter of the ordered and unordered arrays, j traversal the unordered array
while (j < r) {
if (A[j] < pivot) {
if(i ! == j) {const temp = A[j];
A[j] = A[i];
A[i] = temp;
}
// The ordered array length is incremented by 1, and the delimited cursor is I +1
i++;
}
j++;
}
// Since only j = povit subscript -1 is traversed, the pivot needs to replace the value of the boundary cursor with the true boundary value of I
if(i ! == r) { A[r] = A[i]; A[i] = pivot; } quick_sort(A, l, i-1);
quick_sort(A, i+1, r);
}
Copy the codeThe time complexity of this algorithm is O(nlogn), and the space complexity is O(1), because it needs to do the exchange operation similar to selection sort, such as the number group [6,7,6,8,3,4,5], with 5 as pivot, when j=4, it needs to exchange A[I] and A[j], and the order of the two 6s is reversed, so quicksort is unstable sort
Merge sort
Merge sort is also a divide-and-conquer idea. You divide an array down the middle into two arrays, and then you continue to divide until you have nothing to divide it into. Then you sort the left and right, and then you merge the arrays until you have an ordered array. As shown in the figure:
StateDiagram - v2,4,7,8,6,5 [3] - > [3,4,7],4,7,8,6,5 [3] - > [8,6,5],4,7 [3] - > [3],4,7 [3] - > [4, 7] [8,6,5] - > [8] ,6,5 [8] - > [6, 5) [4, 7] - > [4] [4, 7] - > [7] [4] - > [4, 7] * [7] - > [4, 7] * [3] - > [3,4,7] * [4, 7] * - >,4,7 [3] * (6, 5) - > [6] [6, 5] - > [5] [6] - > [5, 6] * [5] - > [5, 6] * [8] - > [5,6,8] * * [5, 6] - > [5,6,8] * *,4,7 [3] - > [3,4,5,6,7,8] * ,6,8 [5] * -- - > *,4,5,6,7,8 [3]Recursive formula of merging algorithm is: Merge_sort (L, R) = Merge_sort (L, mid) + mergeSort(mid+1, R)
If l >= r, the splitting does not need to continue
function mergeSort(arr) {
return merge_sort(arr)
}
function merge_sort(arr) {
const len = arr.length;
if (len <= 1) return arr;
const mid = Math.floor(len/2);
const left = merge_sort(arr.splice(0, mid));
const right = merge_sort(arr);
return merge_sort_f(left, right);
}
function merge_sort_f(left, right) {
// Add sentry after array to reduce out of bounds judgment
left.push(Infinity)
right.push(Infinity)
const temp = [];
let i= 0, j = 0;
while(left[i] < Infinity || right[j] < Infinity) {
if (left[i] <= right[j]) {
temp.push(left[i])
i++;
} else{ temp.push(right[j]) j++; }}return temp;
}
Copy the codeThe time complexity of the algorithm is O(nlogn), the space complexity is O(n), and the merging algorithm is stable sorting
There is a better optimization scheme to trouble you to put forward, I will improve ~
In addition, I can not draw pictures, I see others are the combination of text and text, very egg pain, do not know which big guy to provide a good way ~
Comments and suggestions are welcome in the comments section!