On the stability of common sorting

About the stability of common sorting

1. Bubble sort

Obviously, for two adjacent and identical elements , Will not exchange relative positions , So it's stable .

2. Insertion sort

The arrangement is also based on the exchange of adjacent elements , So it's stable .

3. Selection sort

There may be options $i$ When small elements , Destroy the relative position of the original same element .

4. Merge sort

When merging , Do not change the relative order , Because it's on the left + Right stitching .

5. Quick sort

Different cardinality , It may lead to different sorting results , The relativity of the same element is destroyed .

6. Heap sort

Heap sort is unstable , Because operations on the heap can change the relative order of equal items .

7. Shell Sort

The essence is grouping, inserting and sorting , The relative order within the group remains unchanged , The relative order between groups may have changed , So it's not stable .

8. Radix sorting

The stability of the , At first, the subscript will be used as the second keyword .

9. Bucket sort

The stability of the , Same as cardinality sorting .

10. Count sorting

The stability of the , Open the auxiliary array to record the number of occurrences of each number , Count sorting is not based on element comparison , Instead, it uses array subscripts to determine the correct position of the elements .