稳定和不稳定的排序

面经里边有稳定排序和不稳排序的介绍吗？

答：这两天在准备面试，看到好多面经里边有稳定排序和不稳定排序的介绍，找到这篇不错的文章，作为参考。 首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。

常见的排序算法的稳定性是什么？

答：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。 基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。 另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些（个人感觉，没有证实）。 回到主题，现在分析一下常见的排序算法的稳定性，每个都给出简单的理由一下常见的排序算法的稳定性，每个都给出简单的理由。 冒泡排序就是把小的元素往前调或者把大的元素往后调。 比较是相邻的两个元素比较，交换也发生在这两个元素之间。

基数排序是稳定的吗？

答：基数排序基于分别排序，分别收集，所以是稳定的。 排序算法在一趟选择中，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。 光说可能有点模糊，来看个小实例：858410，第一遍扫描，第1个元素8会和4交换，那么原序列中2个8的相对前后顺序和原序列不一致了，所以选择排序不稳定。

稳定排序和插入排序有什么区别？

答：能够节约时间，稳定性算法会减少一次交换时间（但多了不交换这个限制后，稳定排序的冒泡／插入／选择都是O (n^2);而不稳定排序快排／堆排却是O (nlogn)）;2. 排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用; 冒泡排序就是把小的元素往前调或者把大的元素往后调。 比较是相邻的两个元素比较，交换也发生在这两个元素之间。 所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。 插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。