Java八大排序算法总结
排序是开发中应用非常广的操作，目的是使一组无序的数据根据某个关键字排列成有序的数据。
名词解释
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
时间复杂度： 一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。
排序算法分类
比较和非比较的区别
常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。
比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。
计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr之前有多少个元素，则唯一确定了arr在排序后数组中的位置。
非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。
非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
冒泡排序(bubbleSort)基本上是最简单的排序算法了，它重复地走过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来，重复地进行直到不再需要交换，也就是说该数列已经排序完成。冒泡排序是一种稳定的算法。
1.从第一个数开始比较相邻两个数的大小，如果前面的比后面的大，则交换它们两个。
2.对每一对相邻的数重复步骤1的操作，直至最后一个数，一轮交换结束后，最后一个数应该是最大的。
3.重复以上操作，除去已经排好的最后一个数，每轮排序都会使当前一轮最大的数排到最后一个。
4.当所有数据排序完成，结束排序。
/*
* 冒泡排序
*/
public static void bubbleSort(int[] arr){
/*
* 外层每轮使一个数排序完成，最后一轮两个数同时排序完成，所以一共需要进行arr.length-1轮
*/
for(int i=0;i<arr.length-1;i++){
/*
* 每轮结束，内层需要比较的次数-1，第一次需要比较arr.length-1次，所以每轮需要比较arr.length-1-i次
*/
for(int j=0;j<arr.length-1-i;j++){
/*
* 每次比较，如果前面的数比后面的数大，则交换两个数
*/
if(arr[j]>arr[j+1]){
arr[j] ^= arr[j+1];
arr[j+1] ^= arr[j];
arr[j] ^= arr[j+1];
}
}
}
}
最佳情况：T(n) = O(n) 最差情况：T(n) = O(n^2) 平均情况：T(n) = O(n^2)
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
1.首先从所有数据中找到最小(大)的放到数列的开头。
2.然后从未排序数列中找到最小(大)的数，放到已排序数列的末尾。
3.重复以上操作，直到排序完成。
/*
* 选择排序
*/
public static void selectionSort(int[] arr){
/*
* 一共树妖遍历数组长度-1次，i<arr.length-1
*/
for(int i=0;i<arr.length-1;i++){
/*
* 每次从已排序数列后一位开始遍历,j=i+1
*/
for(int j=i+1;j<arr.length;j++){
/*
* 每次找到后面比arr[i]小的数，则与arr[i]交换
*/
if(arr[i]>arr[j]){
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}
}
}
}
最佳情况：T(n) = O(n) 最差情况：T(n) = O(n^2) 平均情况：T(n) = O(n^2)
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。插入排序属于稳定排序。
1.从第一个元素开始，该元素可以认为已经被排序
2.取出下一个元素，在已经排序的元素序列中从后向前扫描
3.如果该元素（已排序）大于新元素，将该元素移到下一位置
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5.将新元素插入到下一位置中
6.重复步骤2~5
/*
* 插入排序
*/
public static void insertionSort(int[] arr){
/*
* 一共需要插入arr.length-1次
*/
for(int i=1;i<arr.length;i++){
//定义临时变量保存要插入的数的值
int temp = arr[i];
//已排序数列的最后一个是要插入的数的前面一个
int j = i-1;
//若arr[j]大于要插入的数，则将arr[j]后移，直到arr[j]《temp或j<0
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
//将temp值插入
arr[j + 1] = temp;
}
}
最佳情况：T(n) = O(n) 最差情况：T(n) = O(n^2) 平均情况：T(n) = O(n^2)
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
1.把长度为n的输入序列分成两个长度为n/2的子序列。
2.对这两个子序列分别采用归并排序。
3.将两个排序好的子序列合并成一个最终的排序序列。
/**
* 归并排序
*/
public static void mergeSort(int[] data,int left,int right) {
if(left >= right) return;
//找出中间索引
int center = (left + right)/2;
//对左边数组进行递归
mergeSort(data, left, center);
//对右边数组进行递归
mergeSort(data, center+1, right);
//合并
merge(data,left,center,right);
}
public static void merge(int[] data,int left, int center,int right) {
//临时数组
int[] tmpArr = new int[data.length];
//右数组第一个元素索引
int rightIndex = center + 1;
//third 记录临时数组的索引
int tmpIndex = left;
//缓存左数组第一个元素的索引
int leftIndex = left;
while (left <= center && rightIndex <=right) {
//从两个数组中取出最小的放入临时数组
if (data[left] <= data[rightIndex]) {
tmpArr[tmpIndex++] = data[left++];
} else {
tmpArr[tmpIndex++] = data[rightIndex++];
}
}
//剩余部分依次放入临时数组
while(rightIndex <= right) {
tmpArr[tmpIndex++] = data[rightIndex++];
}
while(left <= center) {
tmpArr[tmpIndex++] = data[left++];
}
//将临时数组中的内容拷贝回原数组中
while (leftIndex <= right) {
data[leftIndex] = tmpArr[leftIndex++];
}
}
最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
快速排序是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
1.先从数列中取出一个数作为key值；
2.将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
3.对左右两个小数列重复第二步，直至各区间只有1个数。
/*
* 快速排序
*/
public static void quickSort(int arr[],int low,int high) {
int l=low;
int h=high;
int povit=arr[low];
while(l<h) {
while(l<h&&arr[h]>=povit)
h--;
if(l<h){
arr[l]=arr[h];
l++;
}
while(l<h&&arr[l]<=povit)
l++;
if(l<h){
arr[h]=arr[l];
h--;
}
}
arr[l]=povit;
if(l-1>low)
quickSort(arr,low,l-1);
if(h+1<high)quickSort(arr,h+1,high);
}
最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n^2) 平均情况：T(n) = O(nlogn)
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2.按增量序列个数k，对序列进行k 趟排序；
3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
/**
* 希尔排序
*/
public static void shellSort(int[] a) {
int len = a.length;//单独把数组长度拿出来，提高效率。
while(len != 0) {
len = len/2;
for (int i = 0; i < len; i++) {//分组
for (int j = i + 1; j < a.length; j+=len) {//元素从第二个开始
int k = j - len;//k为有序序列最后一位的位数
int temp = a[j];//要插入的元素
while (k >= 0 && temp < a[k]) {//从后往前遍历
a[k + len] = a[k];
k -= len;//向后移动len位
}
a[k + len] = temp;
}
}
}
}
最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog2n)
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog®m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
1.取得数组中的最大数，并取得位数；
2.arr为原始数组，从最低位开始取每个位组成radix数组；
3.对radix进行计数排序（利用计数排序适用于小范围数的特点）；
/*
* 基数排序
*/
public static void radixSort(int[] arr) //d表示最大的数有多少位
{
//获取数组中最大的数
int max = arr[0];
for(int i = 0;i<arr.length;i++){
if(max < arr[i]){
max = arr[i];
}
}
//计算数组中最大数有多少位
int d=0;
while(max>0){
max /= 10;
d++;
}
int k = 0;
int n = 1;
int m = 1; //控制键值排序依据在哪一位
int[][]temp = new int[10][arr.length]; //数组的第一维表示可能的余数0-9
int[]order = new int[10]; //数组orderp[i]用来表示该位是i的数的个数
while(m <= d)
{
for(int i = 0; i < arr.length; i++)
{
int lsd = ((arr[i] / n) % 10);
temp[lsd][order[lsd]] = arr[i];
order[lsd]++;
}
for(int i = 0; i < 10; i++)
{
if(order[i] != 0)
for(int j = 0; j < order[i]; j++)
{
arr[k] = temp[i][j];
k++;
}
order[i] = 0;
}
n *= 10;
k = 0;
m++;
}
}
最佳情况：T(n) = O(n * k) 最差情况：T(n) = O(n * k) 平均情况：T(n) = O(n * k)
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
1.将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
2.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
3.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
/*
*堆排序
*/
public static void heapSort(int []arr){
//1.构建大顶堆
for(int i=arr.length/2-1;i>=0;i--){
//从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(arr,i,arr.length);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for(int j=arr.length-1;j>0;j--){
//将堆顶元素与末尾元素进行交换
arr[0] ^=arr[j];
arr[j] ^=arr[0];
arr[0] ^=arr[j];
adjustHeap(arr,0,j);//重新对堆进行调整
}
}
/**
* 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
*
*/
public static void adjustHeap(int []arr,int i,int length){
int temp = arr[i];//先取出当前元素i
for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
k++;
}
if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;//将temp值放到最终的位置
}
最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n+k)
