From today on, I plan to record the whole process of learning algorithm from shallow to deep, hoping to help me understand the algorithm, and also hope to help the front end students who need to learn from the basics like me.
Today, I will first study five common sorting algorithms. When I study alone, I have encountered some problems and some thoughts. I am glad to discuss with you.
selectionSort
Selection sort is the simplest and intuitive algorithm, and the time complexity of any data calculation is O(n²), so when using it, try to use it in the case of small data size, the only advantage we can think of may be that there is no extra memory space.
The definition of selection sort I understand is that in each round you just look at the smallest number, put it first, and in the second round you look for the smallest number in the remaining array, all at once.
The first code I wrote looked like this
function selectionSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j])[arr[i], arr[j]] = [arr[j], arr[i]]
}
}
console.log(arr);
}
Copy the codeThis kind of situation is not set intermediate variable, theoretically should also selection sort algorithm, do not know or do not reasonable, I every time after printing, is indeed a selection, definition of each value of the minimum ranked the first, but the value of the other element of an array location has changed, first seen most of the other person’s writing are set up an intermediate variable, The inner loop only compares and does not assign.
function selectionSort(arr) {
let minIndex;
for (let i = 0; i < arr.length - 1; i++) {
minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) minIndex = j;
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
}
console.log(arr);
}
Copy the codeThis avoids the situation where I had to swap every comparison the first time.
Insertion sort
Insertion sort is also a simple and intuitive sorting method. He sorted the cards from left to right, just as he sorted the cards in poker, meaning that after each cycle, the cards that had been sorted should be in order. For uninserted cards, look back and forward from the sorted cards to find where they should be inserted.
So when I’m doing an insert sort, I’m going to loop twice, and each loop will insert the first item in the unordered array into the appropriate place in the ordered array, so the time of the insert sort should also be O(n ^ 2).
This is the first way I wrote it
function insertionSort(d) {
let len = d.length;
for (let i = 1; i < len; i++) {
for (let j = i; j > 0; j--) {
if (d[j] < d[j - 1]) {
[d[j], d[j - 1]] = [d[j - 1], d[j]]
}
}
}
console.log(d);
}
Copy the codeAs with the selection sort above, the way I write it causes the inner loop to assign each time it compares.
function insertionSort(arr) {
const len = arr.length;
let preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--
}
arr[preIndex + 1] = current
}
console.log(arr);
}
Copy the codeThis is more consistent with the definition of insertion sort, where the number greater than the current value is moved backward, and the current value is inserted when it finds a suitable place for the current value.
Hill sorting
Hill sort, also known as the descending incremental sort algorithm, is a more efficient and improved version of insertion sort.
- Insertion sort has high efficiency when it operates on almost ordered data, that is, it can achieve the efficiency of linear sort
- But insert sort is generally inefficient because it can only move data one bit at a time
The basic idea of Hill sorting is that the whole sequence of records to be sorted is divided into several sub-sequences for direct insertion sorting respectively. When the records in the whole sequence are “basically ordered”, the direct insertion sorting of all records is carried out successively.
The first way I wrote it
function shellSort(arr) { let len = arr.length; let gap = len; while (gap > 1) { gap = Math.floor(gap / 2); For (let n = 0; n < gap; N ++) {for (let I = n; i < len; I += gap) {// Insert sort for (let j = I; j > 0; j -= gap) { if (arr[j] < arr[j - gap]) { [arr[j], arr[j - gap]] = [arr[j - gap], arr[j]] } } } } } console.log(arr); }Copy the codeDirect insertion sort and Hill sort are compared:
- Direct insertion sort is stable, whereas Hill sort is unstable (where equal data may interact)
- Direct insertion sort is more suitable for basically ordered sets of original records
- Hill sort has fewer comparisons and moves than direct insertion sort, and the effect is more obvious when N is larger
- In Hill sort, the gap of increment sequence (interval) must satisfy: the last step must be 1
- Direct insert sort also works with chained storage; Hill ordering does not apply to chain structures
Sort out the solution after thinking
function shellSort(arr) {
const len = arr.length;
let gap = Math.floor(len / 2);
for (gap; gap > 0; gap = Math.floor(gap / 2)) {
for (let i = gap; i < len; i++) {
temp = arr[i];
for (let j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
arr[j + gap] = arr[j]
}
arr[j + gap] = temp
}
}
console.log(arr);
}
Copy the codeIn the following method, the step size is judged first, and then the insertion sort is done from the second step of the step size.
Bubble sort
Bubble sort is like bubbles, one of the biggest bubbles to rise little by little, finally float to the top (finally), which is compares it to the adjacent two, the former is greater than the latter swaps, or continue to find back, every search to find the largest of the unsorted array, array finally.
The way I wrote it the first time is this
function bubbleSort(arr) {
const len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1])[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
}
console.log(arr);
}
Copy the codeBy definition, bubble sort requires that the elements after the current element be sorted each time, so no optimization is required.
Quick sort
Quick sort the sort of big can be divided into several small order, first selected a benchmark, and then puts about pointer array on either side, from right to left first, look at the size of the array elements and the benchmark, is greater than the benchmark pointer moves left, less than the benchmark put in the numerical benchmark position, then calculated pointer to the left and right now the benchmark size, less than the benchmark pointer moves to the right, the cursor position is greater than the benchmark in the right, Until the left and right Pointers overlap. Then recurse, and then look for the two arrays left and right of the base again, left and right classification, until the recursive array contains only one number, the end of the recursion. (Due to the time and the fact that I can’t do animation, the description may not be very clear. If there is an animation at this time, it should be more accurate.)
This is the first way I wrote it
function sort(arr) { let len = arr.length; quick(arr, 0, len - 1) console.log(arr); function quick(arr, l, r) { if (l == r) return; let left = l, right = r; Let n = arr[left] while (left < right) {while (n < arr[right] &&left < right) {right--} [arr[left], arr[right]] = [arr[right], arr[left]]; while (n > arr[left] && left < right) { left++ } [arr[left], arr[right]] = [arr[right], arr[left]]; } arr[right] = n; if (l < left) { dg(arr, l, left); } if (r > right) { dg(arr, right + 1, r) } } }Copy the codeAfter finishing, we get
function sort(arr, left, right) {
const len = arr.length;
let partitionIndex;
left = left >= 0 ? left : 0;
right = right >= 0 ? right : len - 1;
if (left < right) {
partitionIndex = partition(arr, left, right);
sort(arr, left, partitionIndex - 1);
sort(arr, partitionIndex + 1, right);
}
return arr
}
function partition(arr, left, right) {
let pivot = left;
let index = pivot + 1;
for (let i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index)
index++
}
}
swap(arr, pivot, index - 1)
return index - 1;
}
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
console.log(sort([5, 8, 4, 7, 1, 9, 2, 6]));
Copy the codeI didn’t write ≥0 in line 4 and line 5 at the beginning of this method
left = left ? left : 0;
right = right ? right : len - 1;
Copy the codeDue to the recursion of some data left=0,right=0 ([5, 8, 4, 7, 1, 9, 2, 6], my test data),right=0 at this time will be judged as a Boolean value, resulting in right= len-1, and thus an error occurs. So I added greater than or equal to 0.