常见排序算法

• • 比较
  • 介绍
  • • （1）快排
    • （2）冒泡排序
    • （3）简单选择排序
    • （4）插入排序
    • （5）希尔排序
    • （6）堆排序
    • （7）归并排序
    • （8）基数排序
    • （9）计数排序
    • （10）桶排序
  • 总结

在排序前一个序列中,如果出现N个与关键字相同的数据,那么排序后仍然按照原先序列的排列顺序排列,就说这个算法稳定, 反之就是不稳定的。

代码见： 快速排序的C++实现.
分治思想，选择一个基准元素，将比基准元素小的元素放在其前面，比基准元素大的元素放在其后面，然后再将小于基准值元素的子数列和大于基准元素的子数列按原来的方法排序，直到整个序列有序。
在数据有序时，会退化成冒泡排序。序列越乱的时候，效率越高。优点：速度快，数据移动少；缺点：不稳定。

基准的选择：

• 三数取中：对待排序序列中low、mid、high三个位置上数据进行排序，取他们中间的那个数据作为枢轴，并用0下标元素存储枢轴。
• 随机选取基准：取在待排序列中任意一个元素作为基准。在待排序列是部分有序时，固定选取枢轴使快排效率低下，于是引入了该方法。

优化方法：

• 当待排序序列的长度分割到一定大小后，使用插入排序。原因：对于很小和部分有序的数组，快排不如插排好。
• 在一次分割结束后，可以把与key相等的元素聚集在一起，继续下次分割时，不必再对于key相等元素分割。

代码见： 冒泡排序的C++实现.
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现他们的排序与排序要求相反时，就将他们互换。
优点：简单，稳定。缺点：速度慢，每次只能移动两个相邻的数据。

针对冒泡排序进行优化，即在跑一趟的过程中，没必要两两交换，可以先记下最小值，跑完一趟后直接将最小值换到前面。比冒泡更快，但不稳定。

第一趟：从第一个记录开始，与后面n-1个记录进行比较，找到其中最小的记录和第一个记录进行交换；第二趟：从第二个记录开始，将后面n-2个记录进行比较，找到其中最小的记录和第2个记录进行交换；第i趟：从第i个记录开始，将后面n-i个记录进行比较，找到其中最小的记录和第i个记录进行交换；以此类推，经过n-1趟比较，将n-1个记录排到位，剩下一个最大记录排在最后。

将一个记录插入到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。即先将序列的第一个记录看成是一个有序的子序列，然后从第二个记录逐个进行插入，直至整个序列有序为止。优点：稳定，快，当数据规模较小或者数据基本有序时，效率较高。缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是数据量庞大的时候。

希尔排序是插入排序的一种高效率的实现。先将整个待排序元素序列分割成若干子序列（由相隔某个“增量”k的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（因为直接插入排序在元素基本有序的情况下，效率很高）。

比较在希尔排序中是最主要的操作，而不是交换。用已知最好的步长序列的希尔排序比直接插入排序要快，甚至在小数组中比快速排序和堆排序还快，但在涉及大量数据时希尔排序还是不如快排。

二叉堆是完全二叉树或近似完全二叉树。二叉堆满足两个特性：父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值；每个结点的左子树和右子树都是一个二叉堆。

当父结点的键值总是大于或者等于任何一个子节点的键值时为大根堆。当父结点的键值总是小于或等于任何一个子节点的键值时为小根堆。

堆的存储： 一般都用数组来表示堆，i结点的父结点下标就为（i-1）/2。它的左右子节点的下标分别为2i+1和2i+2。

堆的插入： 每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，然后将这个新数据插入到这个有序数据中。

堆排序的基本思想： 首先调用Build-Max-Heap（创建最大堆）将数组改造为最大堆，然后将堆顶和堆底元素交换，之后将底部上升，最后重新调用Max-Heapify（最大堆调整）保持最大堆性质。由于堆顶元素必然是堆中最大的元素，所以一次操作之后，堆中存在的最大元素被分离出堆，重复n-1次之后，数组排列完毕。如果是从小到大排序，用大顶堆；从大到小排序，用小顶堆。

也可以从空的堆开始，然后依次往堆中插入每一个元素，直到所有数都被插入（转移到堆中为止）。

代码见： 归并排序的C++实现.
常见的归并排序有两种，递归法（自上而下的合并，比较简单）和非递归法（自底向上的合并），都需要新开一个大小为n的数组来中转。递归的归并排序代码更简洁，代价是时间和空间复杂度上都会更大（因为有递归的logn）。

• 非递归法：首先将初始序列的n个记录看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2的有序子序列，在此基础上，再对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序子序列，以此类推，直到得到一个长度为n的有序序列为止。
• 递归法：就是中间切一刀，左右分别递归排序，最后合并两个有序数组。
  若n较大，并且要求排序稳定，则可以选择归并排序。

基数排序不需要进行关键字之间的比较，是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。多关键字排序就是有多个优先级不同的关键字。

如果对数字进行排序，那么个位、十位、百位就是不同优先级的关键字，如果要进行升序排序，那么个位、十位、百位优先级依次增加。

基排序的主要适用场景是待排元素是非负整数，且位数相差不大。此外，整数也可以用字符串等表达，所以也可以用于字符串的排序。

代码见： 计数排序的C++实现.
前提条件： 待排序的数要满足一定的范围的整数，而且需要比较多的辅助空间。其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。计数排序申请的额外空间跨度从最小元素值到最大元素值，若待排序集合中元素不是依次递增的，则必然有空间浪费情况。

计数排序主要适用场景是元素值比较集中，特别是集中在一个小区间里面。

桶排序算是计数排序的一种改进和推广。基本思想：使用映射函数将待排序的数组划分成M个的子区间(桶) 。接着对每个桶中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出每个桶中的全部内容即是一个有序序列。

桶排序之所以能够高效，其关键在于这个映射函数，它必须做到：如果关键字k1 < k2，那么f(k1) <= f(k2)。也就是说第 i 个桶中的最小数据都要大于第 i - 1 个桶中最大数据。桶排序将最小值到最大值之间的每一个位置申请空间，更新为最小值到最大值之间每一个固定区域申请空间，尽量减少了元素值大小不连续情况下的空间浪费情况。

桶排序的主要适用场景是，各元素值分布比较均匀，这样分桶时候就可以比较均匀，尽量避免把大部分元素都分到少数几个桶中。

• 当排序记录个数n较大，关键值分布较随机，且对稳定性不作要求时，采用快速排序为宜。
• 当排序记录个数n较大，内存空间允许，且要求稳定排序时，采用归并排序。
• 当排序记录个数n较大，关键值分布可能出现正序或逆序的情况，且对稳定性不作要求时，采用堆排序或归并排序。
• 当排序记录个数n较大，而只要找出最小的前几个记录，采用堆排序或简单选择排序。
• 当排序记录个数n较小（如小于100）时，记录已基本有序，且要求稳定时，采用直接插入排序。
• 当排序记录个数n较小，记录所含数据项较多，所占存储空间较大时，采用简单选择排序。