Shulou(Shulou.com)06/02 Report--

This article is to share with you about stable sorting algorithms in programming development. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

The stable sorting algorithms are: 1, bubble sorting; 2, selection sorting; 3, insertion sorting; 4, quick sorting; 5, merging sorting; 6, cardinality sorting; 7, Hill sorting (shell); 8, heap sorting.

The operating environment of this tutorial: windows10 system, Dell G3 computer.

Analyze the stability of common sorting algorithms, each giving a simple reason.

Stable sorting algorithm:

1. Bubble sorting

Bubble sorting is to move the small elements forward or the large elements back. A comparison is a comparison of two adjacent elements, and the exchange also takes place between the two elements. So, if the two elements are equal, I don't think you'll be bored to exchange them again.

If two equal elements are not adjacent to each other, then even if they are adjacent by the previous pairwise exchange, they will not be exchanged, so the order of the same elements has not changed, so bubbling sorting is a stable sorting algorithm.

2. Select sort

The selection sort is to select the smallest current element for each location, such as the smallest for the first location, the second smallest for the second element among the remaining elements, and so on until the n-1 element, the nth element does not have to be selected. because it's only the largest element left. So, in a selection, if the current element is smaller than an element, and the small element appears after an element equal to the current element, then the stability is destroyed after the exchange.

Compare mouthful, for example, sequence 58 529, we know that the first selection of the first element 5 and 2 will be exchanged, then the relative order of the two 5s in the original sequence will be destroyed, so selective sorting is not a stable sorting algorithm.

3. Insert sort

Insert sort is to insert one element at a time on the basis of an ordered small sequence. Of course, at the beginning, this ordered small sequence has only one element, which is the first element. The comparison starts at the end of the ordered sequence, that is, the element you want to insert is compared to the largest one that is already ordered, and if it is larger than it, insert directly behind it, otherwise keep looking forward until you find where it should be inserted.

If you encounter one that is equal to the insert element, the insert element places the element you want to insert after the equivalent element.

Therefore, the order of the equal elements has not changed, and the order out of the original unordered sequence is the ordered order, so the insertion sort is stable.

4. Quick sort

The quick sort has two directions, and the I subscript on the left goes straight to the right when a [I] a [center _ index].

If I and j can't walk, ij. Swap a [j] and a [center _ index] to complete a quick sort. When the hub element is exchanged with aj, it is likely to disrupt the stability of the previous element, for example, the sequence is 5 3 3 4 3 8 9 10 11, and now the exchange of the hub element 5 and 3 (the fifth element, the subscript starts from 1) will disrupt the stability of element 3, so quick sorting is an unstable sorting algorithm, and instability occurs when the hub element is exchanged with AJ.

5. Merge and sort

Merge sorting is to recursively divide the sequence into short sequences. the recursive exit is that the short sequence has only one element (considered to be directly ordered) or two sequences (one comparison and exchange), and then merge each ordered segment sequence into an ordered long sequence. keep merging until the original sequence is all sorted. It can be found that when there are one or two elements, one element will not be exchanged, and if the two elements are of the same size, no one will deliberately exchange them, which will not destroy the stability.

So, is the stability destroyed in the process of merging short ordered sequences?

No, during the merge process, we can ensure that if the two current elements are equal, we save the elements in the previous sequence in front of the result sequence, thus ensuring stability. Therefore, merge sorting is also a stable sorting algorithm.

6. Cardinality sort

The cardinality sort is sorted first according to the low order, and then collected

Then sort by high order, and then collect

And so on, up to the highest level. Sometimes some attributes have priority order, first by low priority, then by high priority, the last order is high priority, low priority, high priority. Cardinal sorting is based on separate sorting and collection, so it is a stable sorting algorithm.

7. Hill ranking (shell)

Hill sort is to insert and sort elements according to different step sizes, and when the elements are out of order at the beginning, the step size is the largest, so the number of elements in insertion sorting is very small, and the speed is very fast.

When the elements are basically ordered and the step size is very small, insertion sorting is very efficient for ordered sequences. Therefore, the time complexity of Hill sorting is better than O (n ^ 2). Due to multiple insertion sorting, we know that one insertion sort is stable and will not change the relative order of the same elements, but in different insertion sorting processes, the same elements may move in their respective insertion sorting, and finally their stability will be disturbed, so shell sorting is unstable.

8. Heap sort

We know that the structure of the heap is that the children of node I are 2 * I and 2 * I + 1 nodes, the large top heap requires the parent node to be greater than or equal to its 2 child nodes, and the small top heap requires the parent node to be less than or equal to its 2 child nodes. In a sequence with a length of n, the process of heap sorting is to choose the largest (large top heap) or the smallest (small top heap) with three values of its child nodes starting from n / 2. of course, the choice between these three elements will not destroy the stability. However, when the elements are selected for the parent nodes, such as nmax 2-1, nmax 2-2. 1, the stability will be destroyed. It is possible that the n / 2 parent node exchange swaps the latter element, while the n / 2-1 parent node does not swap the latter same element, then the stability between the two same elements is destroyed. Therefore, heap sorting is not a stable sorting algorithm.

Thank you for reading! This is the end of this article on "what are the stable sorting algorithms in programming development?". I hope the above content can be of some help to you, so that you can learn more knowledge. If you think the article is good, you can share it for more people to see!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.