1. Introduction
Algorithm is king.
Want to learn front end, first practice good internal skills, internal skills is not good, even if the move practice again fancy, after all, can not become a master; Only deep internal work, the front end of the road will go further.
This article contains the ideas, code implementation, some examples, and complexity analysis of the top ten classical sorting algorithms. This should be the most complete JavaScript ten classic sorting algorithm explain it.
To prepare
Stability of sorting algorithm: when the relative position of two equal numbers before and after sorting is unchanged, the algorithm is stable.
Time complexity: simply understood as the time taken to execute an algorithm, usually using big O notation, see time complexity for more details
Space complexity: The amount of memory required to complete a program.
Complexity of common algorithms (image from network)
The most frequent operation of the following algorithm is to swap the positions of two elements in an array (in either positive or reverse order), simply extracting a function as follows:
* * @param {Array} ary * @param {*} x * @param {*} y */ function swap(ary, x, x) y) { if (x === y) return var temp = ary[x] ary[x] = ary[y] ary[y] = temp }Copy the codeBubble-sort
Bubble sort is a simple sorting algorithm. It repeatedly goes through the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The work of visiting the sequence is repeated until no more exchanges are needed, that is, the sequence has been sorted. The algorithm gets its name from the fact that the smaller elements will slowly “float” to the top of the sequence by swapping.
Start at the beginning of the array and compare the sizes of the adjacent elements backward. If the first element is smaller than the next, then switch the two until the end of the array. Add 1 to the starting position of the next round of comparison, and repeat step 1. Repeat 1 to 2 until the sorting is complete.
//bubbleSort.js
Array.prototype.bubbleSort = function(){// If an instance of an array does not have this method, but its prototype does, we can still call this method
for(let i=0; i<this.length-1-i; i++){// After sorting one round, you don't need that much interval. You get rid of the last bit and the interval gets smaller every time you sort
// j < length-i-1; // j < length-i-1;
for(let j =0; j<this.length-1; j+=1) {// Length -1 is to prevent the array length from overflow
// if I < length-1, I < length-1, I < length-1, I < length-1
// Print adjacent elements
if(this[j]>this[j+1]) {const temp = this[j];
this[j]=this[j+1];
this[j+1]=temp
}
}
//this is an array
console.log(this[j],this[j+1])}}const arr = [5.4.3.2.1]
arr.bubbleSort();
// Time complexity O(n^2)
// Space complexity O(1)
Copy the codeOptimization: When no data is exchanged during a bubble operation, the data is in complete order and no further bubble operations are required.
/ Bubble Sort (optimized)//bubbleSort.js
Array.prototype.bubbleSort = function(){// If an instance of an array does not have this method, but its prototype does, we can still call this method
for(let i=0; i<this.length-1-i; i++){// After sorting one round, you don't need that much interval. You get rid of the last bit and the interval gets smaller every time you sort
// j < length-i-1; // j < length-i-1;
for(let j =0; j<this.length-1; j+=1) {// Length -1 is to prevent the array length from overflow
// if I < length-1, I < length-1, I < length-1, I < length-1
// Print adjacent elements
let hasChange = false; // The flag bit for exiting the bubble cycle early
if(this[j]>this[j+1]) {const temp = this[j];
this[j]=this[j+1];
this[j+1]=temp;
hasChange = true; // Indicates a data exchange}}if(! hasChange)break; // If false means all elements are in place and no data is exchanged, exit early
//this is an array
console.log(this[j],this[j+1])}}const arr = [5.4.3.2.1]
arr.bubbleSort();
Copy the codeSelection sort
Selection sort is to find the largest or smallest element in the data and put it at the beginning of the sequence. Then from the rest of the data to continue to find the largest or smallest elements, in order to put the sorting sequence, until all data samples are sorted. Complexity analysis: Obviously, selection sort is also a time-consuming sorting algorithm, no matter what data, need O(n* N) time complexity, not suitable for a large number of data sorting.
First find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence. The search continues for the smallest (large) element from the remaining unsorted elements and places it at the end of the sorted sequence. Repeat step 2 until all elements are sorted.
//selectionSort.js
Array.prototype.selectionSort = function(){
for(let i=0; i<this.length-1; i++){let indexMin = 0;// Set the first digit to the minimum value first
for(letj =i; j<this.length; j+=1) {if(this[j]<this[indexMin]){
// Look for the smallest number
indexMin =j;// Save the index with the smallest number}}if(indexMin ! == i){const temp = this[i];
this[i]=this[indexMin];
this[indexMin]=temp
//this is an array}}}const arr = [5.4.3.2.1]
arr.selectionSort();
// Time complexity O(n^2)
// Space complexity O(1)
Copy the codeInsertion sort
Insertion sort treats the first element of the sequence to be sorted as an ordered sequence, and the second element to the last element as an unsorted sequence; The unsorted sequence is then scanned from beginning to end, and each scanned element is inserted into the appropriate place in the ordered sequence until all the data is sorted. If the element to be inserted is equal to an element in the ordered sequence, the element to be inserted is inserted after the equal element.
答 案 : Start with the first element, which can be thought to have been sorted to take the next element. Scan the sequence of sorted elements backwards and forwards. If the element (sorted) is larger than the new element, move the element to the next position and repeat Step 3. Until the sorted element is found to be less than or equal to the position of the new element, insert the new element into the position and repeat steps 2 through 5
//insertionSort.js
Array.prototype.insertionSort = function(){
for(let i =0; i<this.length; i++) {const temp = this[1]
let j =1;
while(j>0) {if(this[j-1]>temp){
this[j]=this[j-1]}else{
break;
}
j--;
}
this[j] = temp
}
}
const arr = [5.4.3.2.1]
arr.insertionSort();
// Time complexity O(n^2)
// Space complexity O(1)
Copy the codeMerge sort
Merge sort is a sorting method using the idea of merging. The algorithm uses the classic divide-and-conquer strategy (divide-and-conquer) to divide the problem into some small problems and then solve them recursively, and the stage of conquer will be divided into the stage of each answer “patch” together. Divide and conquer).
The input sequence of length n is divided into two subsequences of length n/2. Merge sort is used for the two subsequences respectively; Combines two sorted subsequences into a final collated sequence.
//mergeSort
Array.prototype.mergeSort = function(){
const rec = (arr) = >{
if(arr.length ===1) {returnarr ; }const mid = Math.floor(arr.length/2);
const left = arr.slice(0,mid);
const right= arr.slice(mid,arr.length);
const orderLeft = rec(left);
const orderRight = rec(right);
const res =[]
while(orderLeft.length||orderRight.length){
if(orderLeft.length&&orderRight.length) {
res.push(orderLeft[0]<orderRight[0]? orderLeft.shift():orderRight.shift()) }else if(orderLeft.length){
res.push(orderLeft.shift())
}else if(orderRight.length){
res.push(orderRight.shift())
}
}
return res
}
const res = rec(this)
res.forEach((n,i) = >{
this[i]=n
})
}
const arr = [5.4.3.2.1]
arr.mergeSort();
// 分 O(logn)
/ / in O (n)
// Time complexity O(nlogn)
// Space complexity O(1)
Copy the codeQuick sort
Quicksort uses a divide and conquer strategy to divide an array into two subarrays. You first pick an element from the array and call that element the “benchmark,” or pivot. Reorder the array so that all elements smaller than the base value are placed before the base value and all elements larger than the base value are placed after the base value (the same number can go to either side). After the partition ends, the benchmark is in the middle of the array. This is called a partition operation. After that, the method is repeated in the subsequence until the entire data sequence is sorted.
The idea is to pick an element from the sequence, called “pivot”. Reorder the sequence so that all elements smaller than the sentinel are placed in front of it, and all elements larger than the sentinel are placed behind it (the same number can be on either side). After the partition exits, the sentinel is in the middle of the sequence. This is called a partition operation; Recursively sort the subsequence of elements with values less than sentry and those with values greater than sentry.
//quickSort
Array.prototype.quickSort = function(){
const rec =() = >{
if(arr.length ===1) {returnarr; }const left =[]
const right = []
const mid = arr[0];
for(let i=1; i<arr.length; i+=1) {if(arr[i]<mid){
left.push(arr[i])
}else {
right.push(arr[i])
}
}
return [...rec(left),mid,rec(right)]
}
const res = rec(this)
res.forEach((n,i) = >{this[i]=n})
}
const arr = [5.4.3.2.1]
arr.quickSort();
/ / recursive O (logn)
/ / partition is O (n)
// Time complexity O(nlogn)
// Space complexity O(1)
Copy the codeconclusion
Swipe the fourth day, choose the sorting algorithm of the interview often asked, refueling together
❤️ Thank you all
If you think this content is very helpful to you: like support, let more people can also see this content (collection does not like, is playing rogue – -) follow the public number to NPY front secret, we learn together progress. If you like it, you can also read other articles (thanks to friends for their encouragement and support 🌹🌹🌹)
Start the LeetCode tour
Double pointer to LeetCode
LeetCode27, remove element
Reference:
Hand tear sort algorithm