Stable sorting algorithms include: 1. Bubble sort; 2. Selection sort; 3. Insertion sort; 4. Quick sort; 5. Merge sort; 6. Radix sort; 7. Hill sort (shell ); 8. Heap sorting.
The operating environment of this tutorial: Windows 10 system, Dell G3 computer.
Analyze the stability of common sorting algorithms, and give simple reasons for each.
Stable sorting algorithm:
1. Bubble sorting
Bubble sorting Bubble sorting is to move small elements forward or move large elements backward. Comparison is a comparison of two adjacent elements, and exchange also occurs between these two elements. So, if two elements are equal, I don't think you would just swap them boringly.
If two equal elements are not adjacent, then even if the two are adjacent through the previous pairwise exchange, they will not be exchanged at this time, so the order of the same elements has not changed, so there is a risk Bubble sort is a stable sorting algorithm.
2. Selection sorting
Selection sorting selects the smallest current element for each position, for example, selects the smallest for the first position, and selects the smallest among the remaining elements. Select the second smallest element for the second element, and so on, until then-1th element. The nth element does not need to be selected, because it is the only largest element left. Then, in a selection, if the current element is smaller than an element, and the small element appears after an element that is equal to the current element, then the stability will be destroyed after the exchange.
is a bit difficult to pronounce. For example, in the sequence5 8 5 2 9, we know that selecting the1th element5in the first pass will If exchanged with2, then the relative order of25in the original sequence will be destroyed, so selection sorting is not a stable sorting algorithm.
3. Insertion sort
Insertion sort inserts one element at a time based on an already ordered small sequence. Of course, at the beginning, this small ordered sequence only had one element, which was the first element. The comparison starts from the end of the ordered sequence, that is, the element you want to insert is compared with the largest one that is already sorted. If it is larger than it, insert it directly behind it, otherwise keep looking forward until you find the element it should be inserted into. Location.
If you encounter an element that is equal to the inserted element, then the inserted element will place the element you want to insert after the equal element.
So, the order of equal elements has not changed. The order from the original unordered sequence is the sorted order, so insertion sort is stable.
4. Quick sort
Quick sort has two directions. The i subscript on the left goes all the way to the right. Whena[i] <= a[center_index], wherecenter_indexis the array subscript of the center element, which is generally taken as the0element of the array. Thejsubscript on the right goes all the way to the left, whena[j]>a[center_index].
If both i and j can't walk,i<=j, exchangea[i]anda[j], repeat The above process untili>j. Swapa[j]anda[center_index]to complete a quick sort. When the central element is exchanged witha[j], it is very likely to disrupt the stability of the previous elements. For example, the sequence is5 3 3 4 3 8 9 10 11, Now the exchange of the pivot elements5and3(the5th element, the subscript starts from1) will change the element 3 The stability is disrupted, so quick sort is an unstable sorting algorithm. The instability occurs at the moment when the central element and a[j] are exchanged.
5. Merge sort
Merge sort is to recursively divide the sequence into short sequences. The recursive exit is that the short sequence has only1elements (think directly ordered) or2sequences (1comparisons and exchanges), and then merge each ordered segment sequence into an ordered long sequence, and continue to merge until the original sequence All sorted. It can be found that when there are1or2elements,1elements will not be exchanged, and2elements will not be exchanged if they are equal in size. No one is intentionally swapping, it doesn't destroy stability.
So, in the process of merging short ordered sequences, is stability destroyed?
No, during the merging process we can ensure that if the two current elements are equal, we will save the element of the previous sequence in front of the result sequence, thus ensuring stability. Therefore, merge sort is also a stable sorting algorithm.
6. Radix sorting
Radix sorting is sorting by low order first, and then collecting;
Then sorting by high order, and then collecting;
And so on, until the highest position. Sometimes some attributes have a priority order. They are sorted by low priority first, then by high priority. The final order is that those with high priority come first, and those with the same high priority and low priority come first. Radix sorting is based on separate sorting and separate collection, so it is a stable sorting algorithm.
7. Hill sorting (shell)
Hill sorting is to insert and sort elements according to different synchronization lengths. When the elements are very disordered at the beginning, The step size is the largest, so the number of elements in insertion sort is small and the speed is very fast.
When the elements are basically ordered and the step size is small, insertion sort is very efficient for ordered sequences. Therefore, the time complexity of Hill sorting will be better thanO(n^2). Due to multiple insertion sortings, we know that one insertion sorting is stable and will not change the relative order of the same elements. However, in different insertion sorting processes, the same elements may move in their respective insertion sortings, and finally their stability will change. are scrambled, so shell sorting is unstable.
8. Heap sorting
We know that the structure of the heap is that the children of nodeiare2 * iand2 * i 1node, the large top heap requires the parent node to be greater than or equal to its2child node, and the small top heap requires the parent node to be less than or equal to its2child node. In a sequence of lengthn, the heap sorting process is to select the largest (largest) value starting fromn / 2and its child nodes in total3Heap) or minimum (small top heap), the choice between these3elements will certainly not destroy stability. But when selecting elements forn / 2-1,n/2-2,...1, the stability will be destroyed . It is possible that then/2th parent node exchanges the following element, while then/2-1th parent node does not exchange the following same element, then The stability between these two identical elements is destroyed. Therefore, heap sort is not a stable sorting algorithm.
For more related knowledge, please visit theFAQcolumn!
The above is the detailed content of What are the stable sorting algorithms?. For more information, please follow other related articles on the PHP Chinese website!