排序算法

排序算法的整理和比较。

一、基本概念

  排序算法就是将一序列对象根据某个关键字进行排序。各个排序算法的时间复杂度和空间复杂度不尽相同，所需的条件和适用范围也不同。一般根据元素的相对位置分为稳定排序算法和非稳定的排序算法。也可根据执行情况分为内排序和外排序。另外还有分为比较类型的排序算法和非比较类型的算法。

稳定排序算法:指具有相等键的两个对象在排序输出中出现的顺序与它们在要排序的输入序列中出现的顺序相同。排序的稳定性可以适应于多次排序的情况，比如第一次根据特定的属性排序，第二次要在原来的基础上按另一个属性排序。那么第二次排序就应该使用稳定性算法。常见的稳定排序算法有冒泡排序、插入排序、归并排序、计数排序、桶排序、基数排序。
非稳定排序算法:与稳定的概念相反，不保证相等键的两个对象在排序输出后相对位置保持不变。非稳定排序算法有选择排序、希尔排序、快速排序、堆排序。

内排序:所有的排序操作都在内存中完成。
外排序:多由于数据量太大，因此数据存放在磁盘中。排序通过磁盘和内存的数据传输才能进行。

比较排序:指的是在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位置 。常见的有快速排序、归并排序、堆排序、冒泡排序。
非比较排序:通过确定每个元素之前，应该有多少个元素来排序。如针对数组，计算某个下标元素之前有多少个元素，则唯一确定了该元素的位置。因此非比较排序的时间复杂度可以达到O(n),但是对对数据规模和数据分布有一定的要求。常见的非比较排序有计数排序、基数排序、桶排序。

其中n为数据规模、k是桶的个数、In-place指占用常数内存,不占用额外内存、Out-place指占用额外内存

二、冒泡排序

冒泡排序:是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

  基本步骤就是对于整个序列，每次比较相邻的两个元素，如果第一个比第二个大就交换两个元素。那么遍历一次序列最大的元素就会出现在序列末尾。之后只需要遍历前n-1个元素，第二大的元素就出现在n-1的位置。不断重复,直至全部元素有序即可。

三、选择排序

选择排序:是表现最稳定的排序算法之一 ,因为无论什么数据进去都是O(n²)的时间复杂度,所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

  选择排序的工作原理就是在未排序的序列中找到最小(大)的元素，排在未排序序列的起始(末尾)位置。此时该位置就归到排序序列中，不断重复操作，直至全部元素均变为排序序列就实现了有序。

四、插入排序

插入排序:通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

  排序过程首先归到首元素是以及被排序，之后往后每次遇到新的元素。找到排序序列中对应位置插入，同时大的元素往后移位(方便插入)。最后所以元素遍历完实现有序。

五、希尔排序

希尔排序:希尔排序也是插入排序的一种，由简单插入排序经过改进后的高效版本，也称为缩小增量排序。而与插入排序不同之处在于其会优先比较距离较远的元素。同时该算法是冲破O(n²)的第一批算法之一。

  希尔排序过程中,把记录按一定的增量分组。因此需要先选定增量序列如{n/2、n/4...、1}。之后对每组直接使用插入排序进行处理，随着增量的减少，每组包含的关键词越来越多。当增量减至1时，整个文件恰被分成一组，算法便终止。

六、归并排序

归并排序:建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列。即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2路归并。

  整个算法的步骤就是先把长度为n的序列分成2个长度为n/2的序列，这一过程不断递归调用归并排序二分，直至不能二分(即单个元素，也是默认有序)。之后将每个子序列(此时每个子序列都是有序的，因为最先处理的是长度为1的子序列)合并成一个有序子序列(需要额外的空间)。最后的操作就是将两个长度为n/2的有序子序列合并为长度为n的序列实现有序。

七、快速排序

快速排序:通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

  快速排序也是采用分治法将一个序列分成两个子序列。但是这两个子序列满足左边的子序列所有元素都是小于右边子序列的元素的。就可以发现只要两个子序列内部各自有序，总体的排序就实现了。因此可对这两个子序列递归调用分区算法。最后长度为1或者0的子序列就是默认有序，也是递归的出口。所有处理完即实现了排序。

八、堆排序

堆排序:利用堆这种数据结构所设计的一种排序算法。堆本身是一个近似完全二叉树的结构，并同时满足堆积的性质，即子结点的键值或索引总是小于（或者大于）它的父节点。

  因此整个堆排序算法就是先将无序的序列建成大顶堆，之后每次往堆中取出堆顶元素和最后一个元素交换表示出堆操作。同时重新调整堆结构保证性质。最后全部元素出堆就实现了排序。

九、计数排序

计数排序:核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

  计数排序的思路便是序使用一个额外的数组C，且有数组中第i个元素是待排序数组A中值等于i的元素的个数。由此根据数组C就可以确定出对应值在有序序列中的偏移位置。之后填充原数组就实现了有序。

十、桶排序

桶排序:是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

  基本原理就是将数据分到有限数量的桶里，每个桶在分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。最后把所以非空的桶连接成新的序列就是有序的序列。

十一、基数排序

基数排序:也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),n为数组长度，k为数组中的数的最大的位数。

  基数排序就是按照低位先排序，然后收集。再按照高位排序，然后再收集。依次类推，直到最高位。

  可以发现基数排序、计数排序和桶排序都使用到了桶的概念，但对桶的使用上却有差异。基数排序是根据键值的每位数字来分配桶，计数排序每个桶只存储单一键值。而桶排序每个桶存储一定范围的数值。