目录

排序算法（Sorting algorithm）:)

一、定义

二、分类

三、评价标准

---

排序算法（Sorting algorithm）:)

一、定义

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法（Sorting algorithm），就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。

所谓排序算法，即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率。对于排序，我们首先要求其具有一定的稳定性，即当两个相同的元素同时出现于某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。换言之，即便是两个完全相同的元素，它们在排序过程中也是各有区别的，不允许混淆不清。

二、分类

排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。排序就是把集合中的元素按照一定的次序排序在一起。

一般来说有升序排列和降序排列2种排序，在算法中有8中基本排序：

(1)冒泡排序；(2)选择排序；(3)插入排序；(4)希尔排序；(5)归并排序；(6)快速排序；(7)基数排序；(8)堆排序；(9)计数排序；(10)桶排序。

排序分为 内部排序 和 外部排序。

内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

三、评价标准

稳定性是一个特别重要的评估标准。稳定的算法在排序的过程中不会改变元素彼此的位置的相对次序，反之不稳定的排序算法经常会改变这个次序，这是我们不愿意看到的。我们在使用排序算法或者选择排序算法时，更希望这个次序不会改变，更加稳定，所以排序算法的稳定性，是一个特别重要的参数衡量指标依据。就如同空间复杂度和时间复杂度一样，有时候甚至比时间复杂度、空间复杂度更重要一些。所以往往评价一个排序算法的好坏往往可以从下边几个方面入手：

（1）时间复杂度：即从序列的初始状态到经过排序算法的变换移位等操作变到最终排序好的结果状态的过程所花费的时间度量。

（2）空间复杂度：就是从序列的初始状态经过排序移位变换的过程一直到最终的状态所花费的空间开销。

（3）使用场景：排序算法有很多，不同种类的排序算法适合不同种类的情景，可能有时候需要节省空间对时间要求没那么多，反之，有时候则是希望多考虑一些时间，对空间要求没那么高，总之一般都会必须从某一方面做出抉择。

（4）稳定性：稳定性是不管考虑时间和空间必须要考虑的问题，往往也是非常重要的影响选择的因素。

关于时间复杂度：

1. 平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。

2. 线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序。

3. O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。希尔排序。

4. 线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

关于稳定性：

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

名词解释：

n：数据规模

k：“桶”的个数

In-place：占用常数内存，不占用额外内存

Out-place：占用额外内存

稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同。

学习来源：一文详解十大经典排序算法