排序

排序（Sorting）是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。

十种常见排序算法可以分类两大类别：比较类排序和非比较类排序。

常见的快速排序、归并排序、堆排序以及冒泡排序等都属于比较类排序算法。比较类排序是通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。在冒泡排序之类的排序中，问题规模为 n，又因为需要比较 n次，所以平均时间复杂度为 O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为 logn次，所以时间复杂度平均 O(nlogn)。

比较类排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

而计数排序、基数排序、桶排序则属于非比较类排序算法。非比较排序不通过比较来决定元素间的相对次序，而是通过确定每个元素之前，应该有多少个元素来排序。由于它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度 O(n)。

非比较排序时间复杂度低，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

十大排序算法

一算法介绍

1选择排序

选择排序的思想就是：从当前数中选出一个最大或者最小的值排在最前面，然后从剩下的数 中选出剩下数的最值排在已经排序的数的后面，算法时间复杂度O(n²),

2冒泡排序

冒泡排序的思想就是：比如说要升序排列，那么就依次相邻两个数比较大小，然后把大的数 放在后面，依次类推。冒泡排序时间复杂度0(n²)

3插入排序

插入排序思想就是：依次遍历数组，假设前面已经有一部分排过序的，当前待排数字跟前面 的数字依次比较大小，将其插在对应顺序位置，算法时间复杂度0（n²）在实际工作中这种 排序算法不可取。

4希尔排序

希尔排序的思想就是：希尔排序是对插入排序的改进，可以把当前数据分组，每个分组都有 一定间隔，比如说原来数组的小标范围是0,1,2,3,4,5,6,7,8,9.我彳门把它们分成两组，0-4 一组，5-9 一组，这样的话，间隔就是5,我们令0,5,；1,6；2,7；3,8；4,9,它们两两比较大小。然 后再减小间隔范围，或者说增多分组个数，比如此时，间隔为2,那么比较下标为024,6,8 的大小，然后比较下标为1,3,5,7,9的大小。到最后间隔变为1,就变成了完全的插入排序了。希尔排序的算法时间复杂度0(n²)

5快速排序

快速排序利用分治的思想，在数组中设置一个游标，从数组的两端来遍历数组，将元素和游 标相比，意图达到两组数据一边游标小，一边比游标大。那么此时的游标就处于两组数组的 中间。然后依次对前后两组数据排序，此时当然可以利用递归了。时间平均复杂度是 O(n*logn),排序算法貌似是公认最实用最好的排序算法，在大多数情况下都能解决问题，提 高效率，当然也有糟糕的时候，此时的算法时间复杂度达到0(n²)

6归并排序

归并排序的思想就是把数组分成两组，前后两组分别排序，两组排完序后再把两组合并起来， 当然可以利用递归的思想来实现归并排序，算法时间复杂度是O(n*logn)

7堆排序

首先说明什么是堆，堆其实就一个二叉树，其中要满足父节点大于或者小于子节点。把数组 中元素按照堆来遍历，修正堆后，那么最大或者最小的元素就在根节点上了。我们把根节点 移除，按照相同的方法再次得到最值，依次类推，直到剩下一个元素位置。算法时间复杂度 是 O(n*logn)

8基数排序

基数排序和后面要说的计数排序，桶排序都是非比较排序，因此他们能够突破比较排序的时 间上限O(n*logn),达到时间复杂度为O(n)的程度，但是这几种排序都有限制性条件，不能 看到他们的时间复杂付貌似比别的低一个等级就觉得他们是最好的排序算法了。三者的思想 类似，都是用到了桶的概念。基数排序针对的是非负整数，将所有的数字依次比较个位，十 位，百位，直到最高位，每一次比较都能得到一个排序，由于越往高位，这个位上数字影响 权重越大，所以能够起到对前面顺序的修正。

9计数排序

计数排序的思想也很简单，就是针对所有的整数。取一个从最小值到最大值的间隔，然后遍 历数组，把当前元素放在下标为(当前元素值-最小值）的位置。

10桶排序

桶排序的思想就是先把数据分成一个个分组，这一个个分 组就是一个个桶，当然这些桶是有顺序的，要不然桶排序作为非比较排序算法，连唯一的顺序都没有并且也不比较还排什么序啊。对于首次分桶后的数据可以采用递归或者其他的排序 算法实现对每个桶内数据排序。最后按照桶号将所有数据依次连接就是排完顺序的数据了.

排序的稳定性

举例：有一张成绩表，记录着许多学生的成绩，要将他们按成绩排序，但成绩相同者的相对顺序不能改变。换句话说，ABCDE 五人，A、C、D 成绩相同，显然排序完之后会排在一起，现在的要求是：他们排在一起的顺序也必须是ACD，不能是 ADC、CAD...。这样的实际问题涉及到排序的稳定性。

排序的稳定性：一个排序算法，若可使排序前后关键字相同的项相对顺序不变，则称该排序算法是稳定的排序算法。

在编写合理的情况下，简单排序算法是稳定的；快速排序、堆排序是不稳定的。在CSP中，往往排序是没有附带其他项目的，也就不要求排序稳定。快速排序、堆排序仍然是最佳选择。可是有没有时间复杂度为O(nlogn)的稳定的排序算法呢？有的。归并排序基于分治思想：把要排序的数组平分两半，对两部分分别排序（递归地）后再合并起来。合并时，将一个数组按顺序插入另一个数组中，需要开辟一个暂存数组。利用空间优化，可只用开辟一个与原数组等大的数组。归并排序的优缺点都很明显。无论情形如何，它的比较次数、赋值次数都稳定在nlogn，没有最差情况，运行时间与快速排序、堆排序相当。而且，它是稳定的排序算法。但是，它的内存占用会达到快速排序、堆排序的两倍，

合理选用排序算法

下面是一些主排序算法的优缺点比较：竞赛时使用容易造成内存超出限制。