1、排序算法必知必会

厨子大约 4 分钟数据结构算法算法基地面试排序算法

袁记菜馆内

袁厨：小二，最近快要过年了，咱们店也要给大家发点年终奖啦，你去根据咱们的红黑豆小本本，看一下大家都该发多少的年终奖，然后根据金额从小到大排好，按顺序一个一个发钱，大家回去过个好年，你也老大不小了，回去取个媳妇。
小二：好滴掌柜的，我现在马上就去。

上面说到的按照金额从大到小排好就是我们今天要讲的内容 --- 排序。

排序是我们生活中经常会面对的问题，体育课的时候，老师会让我们从矮到高排列，考研录取时，成绩会按总分从高到底进行排序（考研的各位读者，你们必能收到心仪学校给你们寄来的大信封），我们网购时，有时会按销量从高到低，价格从低到高，将最符合咱们预期的商品列在前面。

概念：将杂乱无章的数据元素，通过一定的方法（排序算法）按关键字（k）顺序排列的过程叫做排序。例如我们上面的销量和价格就是关键字

排序算法的稳定性

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

因为我们待排序的记录序列中可能存在两个或两个以上的关键字相等的记录，排序结果可能会存在不唯一的情况，所以我们排序之后，如果相等元素之间原有的先后顺序不变。则称所用的排序方法是稳定的，反之则称之为不稳定的。见下图

例如上图，我们的数组中有两个相同的元素 4，我们分别用不同的排序算法对其排序，算法一排序之后，两个相同元素的相对位置没有发生改变，我们则称之为稳定的排序算法，算法二排序之后相对位置发生改变，则为不稳定的排序算法。

那排序算法的稳定性又有什么用呢？

在我们做题中大多只是将数组进行排序，只需考虑时间复杂度空间复杂度等指标，排序算法是否稳定，一般不进行考虑。但是在真正软件开发中排序算法的稳定性是一个特别重要的衡量指标。继续说我们刚才的例子。我们想要实现年终奖从少到多的排序，然后相同年终奖区间内的红豆数也按照从少到多进行排序。

排序算法的稳定性在这里就显得至关重要。这是为什么呢？见下图

第一次排序之后，所有的职工按照红豆数从少到多有序。

第二次排序中，我们使用稳定的排序算法，所以经过第二次排序之后，年终奖相同的职工，仍然保持着红豆的有序（想对位置不变），红豆仍是从小到大排序。我们使用稳定的排序算法，只需要两次排序即可。

稳定排序可以让第一个关键字排序的结果服务于第二个关键字排序中数值相等的那些数。

上述情况如果我们利用不稳定的排序算法，实现这一效果是十分复杂的。

我们根据元素是否依靠与其他元素的比较来决定元素间的相对次序。以此来区分比较类排序算法和非比较类排序算法。

内排序是在排序的整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存中，整个排序过程需要在内外存之间多次交换数据才能进行，常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

对我们内排序来说，我们主要受三个方面影响，时间性能，辅助空间，算法的复杂性

在我们的排序算法执行过程中，主要执行两种操作比较和交换，比较是排序算法最起码的操作，移动指记录从一个位置移动到另一个位置。所以我们一个高效的排序算法，应该尽可能少的比较和移动。

执行算法所需要的辅助空间的多少，也是来衡量排序算法性能的一个重要指标

这里的算法复杂度不是指算法的时间复杂度，而是指算法本身的复杂度，过于复杂的算法也会影响排序的性能。