排序算法的稳定性及其意义

╰+攻爆jí腚メ 2022-05-12 06:10 212阅读 0赞

**稳定性的定义**

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

**判断方法**

对于不稳定的[排序算法][Link 1]，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。例如，对于如下冒泡排序算法，原本是稳定的排序算法，如果将记录交换的条件改成a\[j\].key>=a\[j+1\].key，则两个相等的记录就会交换位置。

void BubbleSort(DataType a[], int n)
    
    { 
            int i, j, flag = 1;
    
            DataType temp;
    
            for(i = 1; i < n && flag == 1; i++)
    
            { 
                flag = 0;
    
                for(j = 0; j < n-i; j++)
    
                { 
                    if(a[j].key >a[j+1].key)
                    {             
                                      /*如果改为a[j].key >=a[j+1].key，就不稳定咯*/
    
                        flag = 1;
        
                        temp = a[j];
    
                        a[j] = a[j+1];
    
                        a[j+1] = temp; 
                    }
    
                }
    
            }
    
    }

**常见算法的稳定性（要记住）**

**[堆排序][Link 2]、[快速排序][Link 3]、[希尔排序][Link 4]、[直接选择排序][Link 5]不是稳定的排序算法，而[基数排序][Link 6]、[冒泡排序][Link 7]、[直接插入排序][Link 8]、[折半插入排序][Link 9]、[归并排序][Link 10]是稳定的排序算法。**

**稳定性的意义**

1、如果只是简单的进行数字的排序，那么稳定性将毫无意义。  
2、如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义（所谓的交换操作的开销已经算在算法的开销内了，如果嫌弃这种开销，不如换算法好了？）  
3、如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。  
4、除非要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。（当然，如果需求不需要保持初始的排序意义，那么使用稳定性算法依旧将毫无意义）。

[Link 1]: http://baike.baidu.com/view/297739.htm
[Link 2]: http://baike.baidu.com/view/157305.htm
[Link 3]: http://baike.baidu.com/view/115472.htm
[Link 4]: http://baike.baidu.com/view/178698.htm
[Link 5]: http://baike.baidu.com/view/3632419.htm
[Link 6]: http://baike.baidu.com/view/1170573.htm
[Link 7]: http://baike.baidu.com/view/254413.htm
[Link 8]: http://baike.baidu.com/view/1193395.htm
[Link 9]: http://baike.baidu.com/view/9681546.htm
[Link 10]: http://baike.baidu.com/view/90797.htm