Sorting Algorithms

左手的ㄟ右手 2021-11-10 15:12 331阅读 0赞

Reference

[1] https://www.geeksforgeeks.org/stable-quicksort/

Stability

A sorting algorithm is said to be stable if it maintains the relative order of records in the case of equality of keys.

Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.
QuickSort is an unstable algorithm because we do swapping of elements according to pivot’s position (without considering their original positions).

If Swap is every expensive, better stability is expected.

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的

723138-20190310080707260-386583268.png

转载于:https://www.cnblogs.com/codingforum/p/10504080.html

发表评论

表情：
评论列表 （有 0 条评论，331人围观）

还没有评论，来说两句吧...

相关阅读