八种排序算法的稳定性分析

TIPs:

一个算法稳定是指，如果A=B，A在B前面，在进行排序算法后，仍然保持A在B前面。

算法分类：

常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

算法复杂度：

冒泡排序：稳定，因为相同的数不会交换位置，只有后面的大于等于前面的数的数才会往后交换位置。也就是说如果A=B,A在B的前面，冒泡排序会将B往后放，A的位置不变。


选择排序：不稳定，选择排序遍历数组将选中未排序的数组中最小的数，然后将这个数和未排序的第一个数交换，这样的话可能存在一种情况，如(7) 2 5 9 3 4 [7] 1，其中1会和(7)换位置，所以这种算法不稳定。


插入排序：稳定，插入排序会往后遍历未排序的数，然后把这个数插入到前面排序的数组中的合适的排序位置，因此仅仅会产生排序数组的向后一位的移动以及某一个数的向前移动，但是这个数可以控制放入在不超过在他前面被排序的相同数的位置。


归并排序：稳定，因为归并排序遇到两个一样的数的时候，其比较的两个数组是原始顺序（两个数组是对一个数组的两段数组的抽象，如a数组是x索引从0到5的子数组）因此遇到两个相同的数时，处理方式是先把“前面”的一个数组的值放在新的归并数组前面。因此归并排序是稳定的。


快速排序：不稳定，一般快排使用交换的方法进行排序，这样就涉及到一个pivot分界元素和其他元素比较的问题，如果这个pivot是随机选取的，那么根据算法实现的不同，有可能会将相同的值和自己的位置交换，从而打乱相同值的原始排序。但是如果使用插入的实现，则可能快排是稳定的排序算法，但是由于数组的插入很慢所以一般不会这样实现。


堆排序：不稳定，堆排序首先是大顶堆在建立大顶堆的过程中就可能丢失原始顺序，而如果左子树小于右子树则比较右子树和根节点，那么就存在左右子树相同的情况，那么根据实现就可能丢失左右子树的原始顺序。


希尔排序：不稳定，希尔排序是插入排序的变种。可以说是根据不同的间隔将数组分组之后再每个组进行排序，然后不断缩小间隔的过程。相同元素如果分到不同组进行排序，就有可能改变原始排序。因此不稳定。下面是间隔为4的排序。


桶排序（基数排序，计数排序）：稳定，桶排序是按照数值区间对数组进行划分，每个区间称为桶。基数排序按照数位进行划分，可以看做是多轮桶排序。计数排序则是最大化的桶排序，它适用于相同值很多的数组的排序。他们对数的排序都是按照它在数组中出现的先后进行排序的，所以怎样都是稳定的。