1. Bubble sorting
The origin of this term is easy to understand. Generally, the bubbles in the river water are relatively small when the bottom just comes out, and will gradually increase as they slowly float to the surface. I won't explain this physical law too much, you just need to understand it.
The operation law of bubbling algorithm is as follows:
① compare adjacent elements. If the first one is bigger than the second, exchange them.
② do the same work for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end. After this step is completed, the last element will be the maximum number (that is, the first wave of bubbling is completed).
③ repeat the above steps for all elements except the last one.
④ continue to repeat the above steps for fewer and fewer elements each time until there is no pair of numbers to compare.
<script>
function bubbleSort(arr){
var i,j,k;
console.log('Initial array'+arr);
// this for The loop represents the total number of rounds to compare
for(i = 0;i<arr.length;i++){
// this for Loop is used to loop through the values in the array
// yes arr[0,......,length-i]Sort the array between
// j The range of is critical because each time a larger value is placed on the right, the range will gradually narrow
for(j = 0;j<arr.length-i;j++){
console.log('The first'+j+'Comparison times:'+arr[j]+':'+arr[j+1]);
if(arr[j]>arr[j+1]){
k = arr[j];
arr[j] = arr[j+1];
arr[j+1] = k;
}
}
console.log('The first'+i+'Round sorting result:'+arr);
}
return arr;
}
var arr = [4,1,8,6,2,9,3,7];
var arrSorted = bubbleSort(arr);
console.log("Final result:"+arrSorted);
</script>
The results are as follows:
It should have been 8 rounds of sorting. Here we only have 7 rounds of sorting, because after the seventh round of sorting, it is already an ordered array.
Bubble sorting explanation:
Bubble sorting consists of two for loops. The variable I of the first for loop indicates how many rounds of comparison are needed in total, and the variable j of the second for loop indicates the subscript [0,1,..., length-i] of the elements participating in each round of comparison. Because a maximum value is placed on the far right in each round of comparison, the number of elements after each round of comparison will be one less, which is why the range of j is gradually reduced. I believe it is not difficult to write a bubble sort quickly after you understand it.
Bubble sorting performance analysis:
Assuming that the number of array elements participating in the comparison is N, the first round of sorting has N-1 comparisons, the second round has N-2 comparisons, and so on. The summation formula of this sequence is:
(N-1)+(N-2)+...+1 = N*(N-1)/2
When the value of n is large, the comparison times of the algorithm is about N2/2, ignoring minus 1.
Assuming that the data is random, the positions may be exchanged and may not be exchanged in each comparison. Assuming that the probability is 50%, the number of exchanges is N2/4. However, in the worst case, if the initial data is in reverse order, the position should be exchanged for each comparison.
The number of exchanges and comparisons is directly proportional to N2. Since the constant is not large and 2 and 4 are ignored in the O representation, the bubble sorting operation requires O(N2) time level.
In fact, whenever we see a loop nested in another loop, we can doubt that the running time of this algorithm is O(N2) level. The outer loop executes n times, and the inner loop executes n times (or a fraction of N times) for each outer loop. This means that a basic operation needs to be performed approximately N2 times.
2. Select sort
Selective sorting is to select the smallest element from the data elements to be sorted each time and store it at the beginning of the sequence until all the data elements to be sorted are finished.
There are three steps:
① find the element with the smallest keyword from the sequence to be sorted
② if the smallest element is not the first element of the sequence to be sorted, exchange it with the first element
③ from the remaining N - 1 elements, find the element with the smallest keyword and repeat steps (1) and (2) until the sorting is completed
The code is as follows:
<script>
function ChoiceSort(arr){
var i,j,minIndex,k;
console.log('Initial array'+arr);
// The outer loop indicates the number of cycles and is used to take out the value of comparison. It is set to A value
for(i = 0;i<arr.length-1;i++){
// The internal circulation is to remove the division A Compare values other than
// Since the smallest value is placed first every time, you only need to compare the value after the last comparison value
// Reassign the subscript to the second i The number of subscripts continues to be compared
minIndex = i;
for(j = i+1;j<arr.length;j++){
console.log('The first'+i+'Wheel comparison:'+minIndex+':'+arr[minIndex]+'=>'+j+':'+arr[j]);
// Judge whether the previous value will be greater than the next value
if(arr[minIndex]>arr[j]){
// If it is greater than, the subscript of the previous value is assigned to the original latter number, and then compared with the subsequent values
minIndex = j;
}
}
// Judge whether the compared value is in the same subscript, and insert if it is not the same subscript
if(i != minIndex){
k = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = k;
}
console.log('The first'+i+'The result of the sorting round is:'+arr);
}
}
var arr = [4,1,8,6,2,9,3,7];
var arrSorted = ChoiceSort(arr);
console.log("Final result:"+arrSorted);
</script>
You can see that the number of sorting here has become less.
Select sorting performance analysis:
The selection sort and bubble sort performed the same number of comparisons: N * (N-1) / 2, but only N exchanges were performed at most.
When the n value is large, the comparison times are the main, so like bubble sorting, using large o represents the O(N2) time level. However, due to the small number of times of selective sorting exchange, selective sorting is undoubtedly faster than bubble sorting. When the value of n is small, if the exchange time is much larger than the selection time, the selection sorting is quite fast.
3. Insert sort
The basic idea of direct insertion sorting is to insert a record to be sorted into the ordered sequence that has been arranged in front until all elements are inserted.
Insertion sort is also divided into direct insertion sort, binary insertion sort, linked list insertion sort, Hill sort, etc. Here we just explain it with direct insertion sort, and others will be introduced later when talking about advanced sort.
The code is as follows:
<script> function InsertSort(arr){ var i,j,k;console.log("Initial sort:"+arr);for(i = 0;i<arr.length;i++){ // Value to be assigned to k k = arr[i]; j = i; // If the extracted value is not the first value and is smaller than the previous value, judge // Compare the value with the previous value one by one, until the previous value is smaller than the value, stop the comparison, take out the subscript at this time, and insert the value while(j>0 && k < arr[j-1]){ arr[j] = arr[j-1]; j-- }; arr[j] = k; } return arr } var arr = [4,1,8,6,2,9,3,7]; var arrSorted = InsertSort(arr); console.log("Final result:"+arrSorted); </script>
Operation results:
Insert sort performance analysis:
In the first round of sorting, it can be compared once at most, the second round can be compared twice at most, and so on. In the nth round, it can be compared n-1 at most. So there are 1 + 2 + 3 ++ N-1 = N*(N-1)/2.
Suppose that when the insertion point is found in each round of sorting, on average, only half of all data items are really compared. We divide it by 2 to get: n * (N-1) / 4. The O(N2) time level is roughly required in the large o representation.
The number of copies is roughly equal to the number of comparisons, but the time-consuming of one copy and one exchange is different. Therefore, compared with random data, insertion sorting is twice as fast as bubbling and slightly faster than selection sorting.
It should be noted here that if you want to arrange in reverse order, each comparison and movement will be carried out. At this time, it will not be faster than bubble sorting.
4. Summary
The three sorting methods mentioned above, bubbling, selection and insertion, which are expressed by large O, all require O(N2) time level. Generally, bubble sort is not selected. Although bubble sort writing is the simplest, the average performance is not as good as selection sort and insertion sort.
Selective sorting reduces the number of exchanges to a minimum, but the number of comparisons is still very large. When the amount of data is small and the exchange of data is more time-consuming than the comparison of data, selective sorting can be applied.
In most cases, assuming that the amount of data is relatively small or basically orderly, insertion sorting is the best choice among the three algorithms.
Later, we will explain advanced sorting. The time level of large O representation will be smaller than O(N2).