Classification algorithm
The ten common sorting algorithms can be divided into two broad categories:
Nonlinear time comparison sorting: to determine the relative order of elements by comparison, because its time complexity can not break O(Nlogn), so called nonlinear time comparison sorting.
Linear time non-comparative sorting: it does not determine the relative order of elements by comparison. It can break through the lower bounds of time based on comparison sorting and run in linear time, so it is called linear time non-comparative sorting.
Algorithm complexity
Relevant concepts
Stable: If a is ahead of B and a= B, a will still be ahead of B after sorting.
Unstable: If a is in front of B and a= B, a may appear behind B after sorting.
Time complexity: Total number of operations on sort data. Reflect the rule of operation times when n changes.
Spatial complexity: A measure of the storage space required for an algorithm to execute within a computer, and a function of data size N.
Bubble Sort
Principle:
Compare two adjacent elements, swapping the one with the highest value to the right
Algorithm description
- Compare the first place with the second place. If the first place is larger than the second place, switch places
- Continue to compare the following numbers, using the same method, to the last digit, the largest number will be ranked last
- Repeat the comparison until the sorting is complete. Note that the last digit was already the largest in the last sorting, so after each sorting, the next comparison can be reduced accordingly
Dynamic graph demonstration
Code parsing
let arr = [3.45.16.8.65.15.36.22.19.1.96.12.56.12.45];
let flag;
let len = arr.length;
let num1 = 0; // The number of comparisons
let num2 = 0; // The number of swaps
// There are 15 numbers, just pick the 14 largest numbers, the last number is the smallest, no need to compare
for(let i = 0; i < len - 1 ; i++){
// After each I change, the maximum value of j is sorted to the last digit, so there is no need to compare the last digit, so the maximum value of j is len-i-1
for(let j = 0; j < len - i - 1; j++){
num1 += 1;
// If the number of the current position is greater than the number of the next position, the position is switched
if(arr[j] > arr[j+1]){
num2 =+ 1;
flag = arr[j];
arr[j] = arr[j+1];
arr[j+1] = flag
}
}
}
console.log(arr,num);
Copy the codeThe output is:
The counters NUM1 and num2 are 105 and 46, respectively
As can be seen from the code, the required temporary variables have not changed during the sorting process, so the space complexity is O(1); The code goes through the for loop twice and is nested, so the time complexity is O(n²).
The optimal situation of bubble sort is that the original array is sorted by default, num1 is still 105, num2 is 0, and the time complexity is still O(n²). Why is it said in the previous complexity table? After some research, a simple optimization of the above code was found.
If the sorted array is: [1, 2, 3, 4, 5], now completely conforms to the complexity of the optimal conditions, when the first cycle, we found that the data of two adjacent exchanged a all have no, that is to say, all the number is greater than before a number, at this point is the positive sequence, no need to order was the next, so we only need to add a variable to determine:
// No swap occurred initially
let isSwap = false;
for(let i = 0; i < len - 1 ; i++){
// After each I change, the maximum value of j is sorted to the last digit, so there is no need to compare the last digit, so the maximum value of j is len-i-1
for(let j = 0; j < len - i - 1; j++){
num1 += 1;
// If the number of the current position is greater than the number of the next position, the position is switched
if(arr[j] > arr[j+1]){
num2 =+ 1;
isSwap = true;
flag = arr[j];
arr[j] = arr[j+1];
arr[j+1] = flag
}
}
// If an exchange occurs, end the loop directly
if(! isSwap){return}}Copy the codeWhen swapping occurs, isSwap becomes true. After the first loop, if isSwap is still false, the array is in positive order and no longer needs to be sorted. At this point, the time complexity is O(n).
In the process of comparison, only the number greater than the latter is judged. If two numbers are equal, there is no need to swap, so bubble sort is stable sort.
Selection Sort
The principle of
The sequence is divided into unsorted and sorted, the smallest number in the unsorted sequence is found, and the smallest number is placed at the beginning of the unordered sequence, and then the smallest number is found in the remaining unsorted sequence
Algorithm description
- The initial unordered sequence is to be sorted, and the ordered sequence is empty
- Find the minimum value from the unordered sequence, put it at the beginning of the unordered sequence, that is, swap it with the starting position
- Push the unordered sequence start bit back one position, continuing 2 steps
Dynamic graph demonstration
Code parsing
// Select the smallest value in the unordered sequence and place it in the unordered first
let arr = [3.45.16.8.65.15.36.22.19.1.96.12.56.12.45];
let len = arr.length;
let minIndex;
let flag;
let num1 = 0; // The number of comparisons
let num2 = 0; // The number of swaps
for(let i = 0; i < len - 1; i++){// After each selection of the minimum value, the start position of the unordered region is pushed back 1
minIndex = i;
// j loops to the last digit and selects the smallest index in the current unordered array
for(let j = i + 1; j < len; j++){ num1 +=1;
if(arr[minIndex]>arr[j]){
minIndex = j;
}
}
num2 += 1;
flag = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = flag;
}
console.log(arr,num1,num2)
Copy the codeThe output is:
The counters NUM1 and num2 are 105 and 14, respectively
That is, the number of comparisons for selection sort is the same as if bubble sort was not optimized, and the number of swaps is only 14
[1,2,3,4,5], positive sequence, without any swap, we optimize the last swap code:
if(minIndex == i){
num2 += 1;
flag = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = flag;
}
Copy the codeNo data exchange is taking place at this time.
In fact, as you can see from the code, the selection sort always goes through N^2/2 comparisons, and the number of swaps is at most N-1 and at least 0 depending on the original sequence.
Therefore, the time complexity of selection sort is always O(n squared), and the space complexity is O(1).
[5,3,8,5,2] [5,3,8,5,2]
Insertion Sort
The principle of
Build an ordered sequence. For unordered data, scan forward from behind the ordered sequence to find the corresponding position to insert
Dynamic graph demonstration
Code implementation
let arr = [3.45.16.8.65.15.36.22.19.1.96.12.56.12.45];
let len = arr.length;
// Define the starting position of the current unsorted data, that is, the data to be inserted
let currentValue;
// The ordered sequence traverses the position
let preIndex;
let num1 = 0; // The number of comparisons
let num2 = 0; // The number of swaps
for(let i = 1; i < len; i++){// Define the raw data second as the unsorted data first. By default the raw data first is sorted
currentValue = arr[i];
// The maximum index of the current ordered sequence
preIndex = i - 1;
// When the index is greater than or equal to 0 and the current index value is greater than the data to be inserted
for(letj = preIndex; j>=0; j--){// For the first comparison, if the maximum index value of the ordered sequence is actually one bit before the data to be inserted, then it will be moved one bit later
num1+=1;
if(arr[preIndex]>currentValue){
arr[preIndex+1] = arr[preIndex];
preIndex --;
// Index decrement by 1 to continue the comparison}}// If the value of the index position is smaller than that of the data to be inserted, the data to be inserted will be inserted
// Why preIndex+1, because the current index has changed after moving one bit in the while loop
num2 += 1;
arr[preIndex+1] = currentValue;
}
console.log(... arr,num1,num2)Copy the codeThe output is:
The counters NUM1 and num2 are 105 and 14, respectively
In the implementation of insertion sort, in-place sort is usually adopted (that is, the sort only needs to use O(1) extra space). Therefore, in the process of scanning from back to front, the sorted elements need to be moved backward step by step repeatedly to provide insertion space for the latest elements.
In terms of time complexity, if the above writing method is followed, The Times of execution are in order of 1,2,3…. N minus 1, so the time is order n squared.
The optimal complexity of bubble sort becomes smaller after optimization. Look at the previous table, the optimal time complexity of insert sort is O(n), so what is the reason?
We use a for loop and an if loop to determine if the value to be inserted is less than the value of the current index position. Can we rewrite that?
while(preIndex>=0&&arr[preIndex]>currentValue){
arr[preIndex+1] = arr[preIndex];
preIndex --;
}
Copy the codeIn this way, if in the positive order case: [1,2,3,4,5], each comparison does not enter the while loop, so only n-1 comparison is performed, so the time complexity is O(n), then the worst complexity is actually the reverse case, requiring 1,2,3… N times, so the worst time is order n ^ 2.
conclusion
Compare the three easiest sorting methods:
Selection sort is optimized for bubble sort, which selects a maximum value for each round by pairwise comparison, while selection sort directly selects the minimum value from the sequence and inserts it into the head of the unordered sequence (swap), which reduces unnecessary transposition operations compared to bubble sort.
Insertion sort is similar to selection sort in idea. Selection sort is to find the minimum value from the unordered sequence and exchange it with the first place of the unordered sequence to generate an ordered sequence, while insertion sort directly selects the first place from the unordered sequence, compares the first place with the ordered sequence and inserts the corresponding position.
Usage scenarios
For the average job, there is no difference in experience between these three uses, right
If you have to choose, insert sort has less comparison times than select sort, but select sort sometimes moves less than insert sort. It is recommended to use insert sort when the data is large, and select sort when the data is small. (Actually, they’re similar –)
reference
- Top ten classic front-end algorithms
- Understand the instability of selection sorting
- Thoroughly understand bubbling sort in three minutes
Novice on the road for advice, if there is a mistake, gently spray
Fixation of trailer
【 Small front end 】 Front end sort algorithm second phase (round hill sort)