至此，经典的排序算法的原理全部过了一遍，其中没有说明希尔排序，不过这个并不是重点，我们重点掌握的应该是快排，其次是归并和堆排，最后是插入排序和冒泡排序，在后面就是非比较的排序。本文对它们的特性做一个简单的总结。算法复杂度已经说明，所以不再赘述。

1.稳定性说明

定义：相同的数字排序前后相对位置不变。

1.冒泡排序：可以做到稳定，因为冒泡排序的思想是每次将大的数往下沉。如果我们设置每次相等也交换，那么就不是稳定的；反之，我们就可以做到稳定。

2.选择排序：不可以，考虑下面这个数组：5，5，5，5，1；那么我们选择一个最小的与第0号元素交换。那么就变成：1，5，5，5，5；此时，第一个5越过后面所有的5跑到了最后面。

3.插入排序：可以做到稳定，插入排序的基本思想是前面已经排好序，后面个数与前面已排好序的比较，小于的话就交换。相等的时候是不需要交换的。

4.归并排序：可以做到稳定，因为主要思想是分治，在merge的时候，两边数组进行比较，凑成一个排序的数组。那么我们只要设置：相等的时候，一直先考虑左边(或者右边)就可以。

5.快速排序：一般不可以，这个就很明显了，我们以三路快排为例，partition的过程中，随机选择一个数，每次形成的数组是<x =x >x这三种，显然中间的x就会打乱顺序。

6.堆排序：很显然不可以。因为每次的建堆过程中，即heapInsert过程中，由于新加入的大的值要上浮，那么就可以调换其中的顺序。比如 6 4 4，此时插入一个5建堆，那么显然第一个4要跟5交换，那么第一个4就跑到了第二个4的后面。

2.工程中的综合算法

如果是很长的基本类型数组，考虑快排；如果是很长的自定义类型的数组，考虑归并排序；如果数组很短(<60)，考虑插入排序，因为常数项小。

因为基本类型相等的是没有差异的，不需要注意原始顺序，所以直接用快排；

但是自定义类型的个体是有差异的，需要对自定义类型中的属性进行判断，关系到顺序。

3.排序问题的补充

  1. 归并排序的额外空间复杂度可以变成O(1)，但是非常难，不需要掌握。
  2. 快速排序可以做到稳定性问题，但是非常难，不需要掌握。
  3. 面试中碰到一个问题：奇数放在数组左边，偶数放在数组右边，还要求原始的相对次序是不变的。空间复杂度为O(1)，时间复杂度为O(N).

针对这个问题，其实是很难的，因为一个数不是奇数就是偶数，属于01问题，那么就跟快排的partition过程是类似的，就是小于等于某个数放左边，大于某个数放右边，那么也是01问题，就是说，荷兰国旗问题是做不到稳定的。但是快速排序做到稳定性是很难的，所以这道题目其实是比较难做到的。