排序算法
排序算法
说明
术语
- 稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
- 不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
- 内排序 ：所有排序操作都在内存中完成；
- 外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
- 时间复杂度 ： 一个算法执行所耗费的时间。
- 空间复杂度 ：运行完一个程序所需内存的大小。
算法总结
上图片名词解释：
n: 数据规模
k: “桶”的个数
In-place: 占用常数内存，不占用额外内存
Out-place: 占用额外内存
算法分类
比较和非比较
比较排序：快速排序、归并排序、堆排序、冒泡排序
在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置 。
在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。
比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。
非比较排序：计数排序、基数排序、桶排序
非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置 。
非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。
非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
十大排序算法
冒泡排序（Bubble Sort）
冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。这种方法主要是通过对相邻两个元素进行大小的比较，根据比较结果和算法规则对该二元素的位置进行交换，这样逐个依次进行比较和交换，就能达到排序目的。
算法步骤
1 首先将第1个和第2个记录的关键字比较大小，如果是逆序的，就将这两个记录进行交换；
2 再对第2个和第3个记录的关键字进行比较，依次类推，重复进行上述计算，直至完成第(n一1)个和第n个记录的关键字之间的比较。这步做完后，最后的元素会是最大的数；
3 再按照上述过程进行第2次、第3次排序，持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
说明：当相邻两个元素大小一致时，这一步操作就不需要交换位置，因此也说明冒泡排序是一种严格的稳定排序算法，它不改变序列中相同元素之间的相对位置关系。。
JAVA代码实现
public static void main(String[] args) {
int[] a={12,14,2,155,2,5,17,56,555,534534,887};
bubbleSort(a);
// selectionSort(a);
// insertionSort(a);
// quickSort(a,0,a.length-1);
// shellSort(a);
// heapSort(a);
// mergeSort(a,new int[a.length],0,a.length-1);
// int[] a={98,93,98,90,97,91,98,93,92,92,90,99,95,97,98,93,96,93};
// countingSort(a);
// bucketSort(a);
// radixSort(a);
System.out.println(Arrays.toString(a));
}
//冒泡排序算法实现
public static void bubbleSort(int[] a){
for (int i = 0; i <a.length ; i++) {
for (int j = 1; j <a.length-i ; j++) {
// 若前面的数字大于后边的数字则交换位置
if (a[j-1]>a[j]){
int temp=a[j-1];
a[j-1]=a[j];
a[j]=temp;
}
}
}
}
选择排序（Selection Sort）
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
选择排序算法的基本思路是为每一个位置选择当前最小的元素。
算法步骤
1 首先从第1个位置开始对全部元素进行选择，选出全部元素中最小的给该位置；
2 再对第2个位置进行选择，在剩余元素中选择最小的给该位置即可；
3 以此类推，重复进行“最小元素”的选择，直至完成第(n-1)个位置的元素选择，则第n个位置就只剩唯一的最大元素，此时不需再进行选择；
4 每次遍历的时候，将前面找出的最小值，看成一个有序的列表，后面的看成无序的列表，然后每次遍历无序列表找出最小值。
说明：举例，序列5 8 5 3 9．我们知道第一遍选择第1个元素“5”会和元素“3”交换，那么原序列中的两个相同元素“5”之间的前后相对顺序就发生了改变。因此，我们说选择排序不是稳定的排序算法，它在计算过程中会破坏稳定性。
JAVA代码实现
// 选择排序算法实现
public static void selectionSort(int[] a){
for (int i = 0; i <a.length ; i++) {
//首先将第i个值定义为最小的值
int k=i;
int min=a[i];
//找到最小值的标
for (int j = i+1; j <a.length ; j++) {
if(min>a[j]){
min=a[j];
k=j;
}
}
//将i与k值互换
if(i!=k)
{
int t=a[i];
a[i]=a[k];
a[k]=t;
}
}
}
插入排序（Insertion Sort）
插入排序算法是基于某序列已经有序排列的情况下，通过一次插入一个元素的方式按照原有排序方式增加元素。这种比较是从该有序序列的最末端开始执行，即要插入序列中的元素最先和有序序列中最大的元素比较，若其大于该最大元素，则可直接插入最大元素的后面即可，否则再向前一位比较查找直至找到应该插入的位置为止。
插入排序的基本思想是，每次将1个待排序的记录按其关键字大小插入到前面已经排好序的子序列中，寻找最适当的位置，直至全部记录插入完毕。
算法步骤
1 从第一个元素开始，该元素可以认为已经被排序；
2 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5 将新元素插入到该位置后；
6 重复步骤2~5。
说明：执行过程中，若遇到和插入元素相等的位置，则将要插人的元素放在该相等元素的后面，因此插入该元素后并未改变原序列的前后顺序。我们认为插入排序也是一种稳定的排序方法。
JAVA代码实现
// 插入排序的算法实现
public static void insertionSort(int[] a){
//从第二个数据开始判断，比较当前的数据与之前所有数据判断适合的插入位置
for (int i = 1; i <a.length ; i++) {
for (int j = i; j >0 ; j--) {
if(a[j]<a[j-1]){
//交换
int t=a[j];
a[j]=a[j-1];
a[j-1]=t;
}else{
break;//插入完毕
}
}
}
}
希尔排序（Shell Sort）
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。同时该算法是冲破O(n2）的第一批算法之一，但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
算法步骤
我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
1 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2 按增量序列个数k，对序列进行k 趟排序；
3 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
说明：基本原理和插入排序类似，不一样的地方在于。通过间隔多个数据来进行插入排序。希尔排序是非稳定排序算法
JAVA代码实现
//希尔排序的算法实现
public static void shellSort(int[] a){
int len=a.length; //数组长度
//每次分组的步长为上一次1/2,step为每组数的跨度
for (int step = len/2; step >0 ; step/=2) {
//每组数据为i，i+step,i+2step...,对数据进行排序
for (int i = 0; i <=step ; i++) {
int k=i;//当前待确认的位置
int temp=a[k];//当前待确认位置的数据
//当前的值大于下一个值，则当前位置数据被下一个位置的值替换
while ((k+step)<len&&a[k]>a[k+step]){
a[k]=a[k+step];
k=k+step;
}
//最终位置k为最终确定的位置
a[k]=temp;
}
}
}
归并排序（Merge Sort）
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。
归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
归并排序算法就是把序列递归划分成为一个个短序列，以其中只有1个元素的直接序列或者只有2个元素的序列作为短序列的递归出口，再将全部有序的短序列按照一定的规则进行排序为长序列。归并排序融合了分治策略，即将含有n个记录的初始序列中的每个记录均视为长度为1的子序列，再将这n个子序列两两合并得到n/2个长度为2(当凡为奇数时会出现长度为l的情况)的有序子序列；将上述步骤重复操作，直至得到1个长度为n的有序长序列。
算法步骤
1 将列表按照对等的方式进行拆分
2 拆分小最小快的时候，在将最小块按照原来的拆分，进行合并
3 合并的时候，通过左右两块的左边开始比较大小。小的数据放入新的块中
说明：简单一点就是先对半拆成最小单位，然后将两半数据合并成一个有序的列表。在进行元素比较和交换时，若两个元素大小相等则不必刻意交换位置，因此该算法不会破坏序列的稳定性，即归并排序也是稳定的排序算法
JAVA代码实现
//归并排序算法实现
public static void mergeSort(int[] a,int[] res,int start,int end){
if(start>=end)//结束递归的判断,分割为一个的情况
return;
int len=end-start;//当前待排序数组的长度
int mid=start+len/2;//数组的中间位置
int start1=start,end1=mid;//数组的前半部分
int start2=mid+1,end2=end;//数组的后半部分
mergeSort(a,res,start1,end1);
mergeSort(a,res,start2,end2);
//执行的最小单元的时候
//start1--end1与start2--end2数据位置是连续的合并到一起组成有序的序列
//将数据排序后存入res
int k=start;//res的起始位置
//将两组数按照从小到大顺序进行存储到res
do {
if(start1>end1)//第一组数据已经排序完,放入第二组数据
{
res[k++]=a[start2++];
continue;
}
if(start2>end2)//第二组数据已经排序完，放入第一组数据
{
res[k++]=a[start1++];
continue;
}
res[k++]=((a[start1]<=a[start2])?(a[start1++]):(a[start2++]));
}while (start1<=end1||start2<=end2);
//res只是一个临时性的存储，下次比较的时候还是比较的原始数据
//所以将res数据放入到a中
for (int x = start; x <=end ; x++) {
a[x]=res[x];
}
}
快速排序（Quick Sort）
快速排序(Quick Sort)使用分治法策略。它的基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序流程：
(1) 从数列中挑出一个基准值。
(2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。
(3) 递归地把”基准值前面的子数列”和”基准值后面的子数列”进行排序。
算法步骤
1 从数列中挑出一个基准值。
2 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。
3 递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。
说明：
下面以数列a={30,40,60,10,20,50}为例，演示它的快速排序过程(如下图)：
只是给出了第1趟快速排序的流程。在第1趟中，设置x=a[i]，即x=30。
(01) 从"右 --> 左"查找小于x的数：找到满足条件的数a[j]=20，此时j=4；然后将a[j]赋值a[i]，此时i=0；接着从左往右遍历。
(02) 从"左 --> 右"查找大于x的数：找到满足条件的数a[i]=40，此时i=1；然后将a[i]赋值a[j]，此时j=4；接着从右往左遍历。
(03) 从"右 --> 左"查找小于x的数：找到满足条件的数a[j]=10，此时j=3；然后将a[j]赋值a[i]，此时i=1；接着从左往右遍历。
(04) 从"左 --> 右"查找大于x的数：找到满足条件的数a[i]=60，此时i=2；然后将a[i]赋值a[j]，此时j=3；接着从右往左遍历。
(05) 从"右 --> 左"查找小于x的数：没有找到满足条件的数。当i>=j时，停止查找；然后将x赋值给a[i]。此趟遍历结束！
按照同样的方法，对子数列进行递归遍历。最后得到有序数组！
JAVA代码实现
//快速排序算法的实现
public static void quickSort(int[] a,int l,int r){
if(l<r){
int x=a[l];//定义最左边的为基准数据
int i=l;//左边界
int j=r;//右边界
while(i<j){
// 由于定义的最左边数据为基准，首先把基准数的位置空出来
// 所以先从右向左直到找到小于基准数数移到左边
while(i<j&&a[j]>x)
j--;
if(i<j)//找到则把当前值移到最左边的空位，并把左边界右移
a[i++]=a[j];
//在从左到右直到找到大于基准数移到右边
while (i<j&&a[i]<x)
i++;
if(i<j)//找到则把当前值移到最右边的空位，并把右边界左移
a[j--]=a[i];
}
//进行循环直到i==j,此处一定是空位则把基准值移到此处
a[i]=x;
//此时基准数位于中间，小于基准的无序数在左边，大于基准的无序数在右边，两组数进行递归
quickSort(a,l,i-1);
quickSort(a,i+1,r);
}
}
堆排序（Heap Sort）
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
- 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
- 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时，称之为堆：
(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
其中i=1,2,…,n/2向下取整;
设当前元素在数组中以R[i]表示，那么，
(1) 它的左孩子结点是：R[2*i+1];
(2) 它的右孩子结点是：R[2*i+2];
(3) 它的父结点是：R[(i-1)/2];
(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。
算法步骤
1 根据初始的数构造初始的堆：大根堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）
2 将堆首（最大值）和堆尾互换，此时确保了堆尾数据为当前堆中最大的数；
3 将堆的尺寸缩小1，然后把剩下元素重新调整为大根堆，调整后堆首依旧是当前堆最大值；
4 重复步骤2，每次重复都会将最大值放到堆尾，直到堆的尺寸为1，则全部排好。
JAVA代码实现
//堆排序的算法实现
public static void heapSort(int[] a){
//首先创建大顶堆，从最后一个非叶子节点从下至上，从右到左开始调整结构
int len=a.length;
int first=(len-1)/2;//第一个非叶子节点
for (int i = first ; i >=0 ; i--) {
//调用调整结构的公共方法
topHeap(a,first,a.length);
}
//创建大顶堆之后，将第一个元素与最后元素互换，然后剩余元素重新构造大顶堆
for (int i = len-1; i >0 ; i--) {
//交换第一个元素和最后一个元素
int temp=a[i];
a[i]=a[0];
a[0]=temp;
topHeap(a,0,i);
}
}
/**
* 构造大顶堆的方法
* @param parent 待调整的节点，一直调整到叶子节点
* @param length 数组的长度，用于判断是否到达叶子节点
*/
public static void topHeap(int[] a ,int parent,int length){
//初始化最大节点为当前待确认位置节点
int max=parent;
//左子节点
int lChild= 2*parent+1;
//右子节点
int rChild=lChild+1;
if(lChild<length&&a[lChild]>a[max])
max=lChild;
if (rChild<length&&a[rChild]>a[max])
max=rChild;
//节点互换则执行递归操作直到最底层
if (max!=parent){
//交换数据
int temp=a[max];
a[max]=a[parent];
a[parent]=temp;
//将当前的数据进行递归操作
topHeap(a,max,length);
}
}
计数排序（Counting Sort）
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
算法步骤
1 找出待排序的数组A中最大max和最小的元素min
2 定义新数组C长度(max-min+1)
3 将原数组A中的数据与最小值min的差值作为新数组C的下标，C数组的值为元素出现的次数
4 输出C中的数据到A中，C数组的下标i+min为原数据的值，C[i]的值为多少就输出多少次
注意：若出现非稳定则反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1
JAVA代码实现
//计数排序算法实现
public static void countingSort(int[] a){
//首先找到最大值与最小值
int min=a[0];
int max=a[0];
for (int i = 1; i < a.length; i++) {
if (a[i]<min)
min=a[i];
if(a[i]>max) {
max=a[i];
}
}
int len=max-min+1;
//定义新的数组C，大小为len,初始化数组元素的值都为0
int[] C=new int[len];
Arrays.fill(C,0);
//将原来数组的数据都放到新定义的数组中
for (int i = 0; i < a.length; i++) {
C[a[i]-min]++;//将数据与最小值的差值作为下标，没处理一个数据则此位置的值+1
}
//此时所有的值都已经放到C中，遍历输出
for (int i=0,k = 0; i < C.length; i++) {
while (C[i]>0){
a[k++]=min+i;//设置结果的值为最小值加上下标值
C[i]--;//当前的数组值-1
}
}
}
桶排序（Bucket Sort）
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
算法步骤
1 设置一个定量的数组当作空桶子;
2 遍历输入数据，并且把项目一个一个放到对应的桶子去;
3 对每个不是空的桶子进行排序,可以使用其它排序方法，也可以递归使用桶排序;
4 从不是空的桶子里把项目再放回原来的序列中。
桶排序假设数据会均匀入桶，在这个前提下，桶排序很快！
JAVA代码实现
//桶排序算法实现
public static void bucketSort(int[] a){
//桶的定义根据实际的情况确认，当前以随意的数据为例子
// 例如：数据在[0,100）整数，则初始化10个桶，数据/10为桶的下标
// 例如：数据在[0,1)，则初始化10个桶，数据*10为桶的下标
//定义桶数
int max=a[0];
int min=a[0];
for (int i = 1; i < a.length; i++) {
if (max<a[i])
max=a[i];
if (min>a[i])
min=a[i];
}
int bucketCount=(max-min)/a.length+1;
ArrayList<Integer>[] buckets=new ArrayList[bucketCount];
//初始化桶
for (int i = 0; i < bucketCount; i++) {
buckets[i]=new ArrayList();
}
//将数据放入到桶中
for (int i = 0; i < a.length; i++) {
//首先确定放入的桶的下标
int num=(a[i]-min)/a.length;
//放入桶中
buckets[num].add(a[i]);
}
//对每个桶中的数据进行排序
for (int i = 0,k=0; i < buckets.length; i++) {
//桶中的数据
ArrayList<Integer> bucket=buckets[i];
//排序,此处自定义方法进行链表的排序
Collections.sort(bucket);
//排序后的数据放回到数组中
for (int value:bucket
) {
a[k++]=value;
}
}
}
基数排序（Radix Sort）
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序。基数排序有从低位到高位的排序LSD，也有按照先高位后低位的排序MSD。
这里介绍LSD：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
算法步骤
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
1 首先确定最大值，并计算最大值的位数；
2 初始化0-9号十个桶，按个位数字，将关键字入桶，入完后，依次遍历10个桶，按检出顺序回填到数组中
3 然后取十位数字将关键字入桶，入完后，依次遍历10个桶，按检出顺序回填到数组中
4 假如数组中最大的数为三位数那么再将百位数字作关键字入桶，这样就能实现基数排序了
JAVA代码实现
//基数排序算法的实现
public static void radixSort(int[] a){
//首先确定最大值及最大位数
int max=a[0];//初始化最大值为a[0]
for (int i = 1; i < a.length; i++) {
if(a[i]>max)
max=a[i];
}
int maxDig=(max+"").length();
//定义10个桶并初始化，每个桶存储每个位数与下标相同的数据链表
ArrayList<Integer>[] buckets=new ArrayList[10];
for (int i = 0; i < 10; i++) {
buckets[i]=new ArrayList<>();
}
//排序的次数为最大位数
for (int i = 1,k=0; k < maxDig;k++, i*=10) {
//进行第i位数的排序
for (int j = 0; j < a.length; j++) {
//第i位数的值放入对应的桶中
int value=a[j]/i%10;
buckets[value].add(a[j]);
}
//取出桶中的数据放回到原数组a中，并将桶清空
for (int j = 0,l=0; j < buckets.length; j++) {
ArrayList<Integer> bucket=buckets[j];
for (int value:bucket
) {
a[l++]=value;
}
buckets[j]=new ArrayList<>();//初始化
}
}
}