1. 插入排序
思想： 假设左边的已经排好序，要加入的数值需要从右边开始逐个比较。如果小于下一个要比较的值
arr[j-1]，那么交换arr[j-1]到后面一个位置。如果大于或等于（即不小于）下一个要比较的值arr[j-1]，那么要插入的值位置应该在arr[j]。java实现
package Sort;
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
int[] arr= {5,3,8,6,4};
ToInsertSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void ToInsertSort(int[] arr) {
if(arr==null || arr.length==0)
return;
for(int i=1;i<arr.length;i++) { //假设最左边的已经排序好
int temp=arr[i]; //这个位置可能被占用
int j=i;
while(j>0&&arr[j-1]>temp) {
arr[j]=arr[j-1];
j--;
}
arr[j]=temp;
}
}
}
- 复杂度
- 时间上，最坏，1+2+ ... +(n-1)=n*(n-1)/2；最好，n
- 空间上，n
2. 选择排序
- 思想：插入排序的改进。考虑到插入排序在序列基本有序的条件下，效率更高。选择增量序列，进行k趟排序。
package Sort;
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int[] arr= {5,3,8,6,4,9,10,5,6};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void shellSort(int[] arr) {
if(arr==null || arr.length==0)
return;
int d=arr.length/2;
for(;d>=1;d=d/2) {
shellInsert(arr,d);
}
}
private static void shellInsert(int[] arr,int d) {
//进行插入排序
for(int i=d;i<arr.length;i++) { //假设d位置之前的已经排好序
int temp=arr[i];
int j=i;
while(j>d-1&&arr[j-d]>temp) {
arr[j]=arr[j-d];
j-=d; //竞争j-d -->j-d位置
}
arr[j]=temp;
}
}
}
- 复杂度
- 时间上，最坏，不好算，是o(n^2 )；最好，log(n)*n；平均，n^1.3
- 空间上，n
3. 选择排序
- 思想：选择出最小值的下标，进行交换。
package Sort;
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args) {
int[] arr= {5,3,8,6,4,9,10,5,6};
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void selectSort(int[] arr) {
if(arr==null || arr.length==0)
return;
for(int i=0;i<arr.length-1;i++) {
int minindex=i;
for(int j=i+1;j<arr.length;j++) {
if(arr[minindex]>arr[j])
minindex=j;
}
if(minindex!=i)
swap(arr,minindex,i);
}
}
private static void swap(int[] arr,int i,int j) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
- 复杂度
- 时间上，最坏和最好都是1+2+3+ ... +n-1=n(n-1)/2
- 空间上，n。辅助空间o(1)
4. 冒泡排序
- 思想：比较相邻的两个元素，仍后根据结果决定是否交换位置。比选择排序要差，交换次数太多。不过有一点优于选择排序：可以根据某个指标判断是否提前完成排序。
package Sort;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arr= {5,3,8,6,4,9,10,5,6};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bubbleSort(int[] arr) {
if(arr==null || arr.length==0)
return;
int flag=0;
for(int i=0;i<arr.length-1;i++) {
if(flag==1)
break;
flag=1;
for(int j=arr.length-1;j>i;j--) {
if(arr[j]<arr[j-1]) {
swap(arr,j,j-1);
flag=0;
}
}
}
}
private static void swap(int[] arr,int i,int j) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
- 复杂度
- 时间上，最坏o(n^2) ，最好o(n)。
- 空间上，n。辅助空间o(1)
5. 归并排序
- 思想：分而治之，后合并。分到只有一个数为止，然后合并。
package Sort;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] arr= {5,3,8,6,4,9,10,5,6};
mergeSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void mergeSort(int[] arr,int left,int right) {
if(arr==null || arr.length==0)
return;
if(left>=right)
return;
int mid=(left+right)/2;
mergeSort(arr,left,mid);
mergeSort(arr,mid+1,right);
merge(arr,left,mid,right);
}
private static void merge(int[] arr,int left,int mid,int right) {
int[] temp=new int[right-left+1];
int i=left;
int j=mid+1;
int k=0;
while(i<=mid&&j<=right) {
if(arr[i]<arr[j])
temp[k++]=arr[i++];
else
temp[k++]=arr[j++];
}
while(i<=mid)
temp[k++]=arr[i++];
while(j<=right)
temp[k++]=arr[j++];
for(int p=0;p<temp.length;p++)
arr[left+p]=temp[p];
}
}
- 复杂度
- 时间上，nlog(n)。
- 空间上，n+n。辅助空间o(n)
6. 快速排序
- 思想：分而治之。每次确定出来一个pivot（基准）。它左边的数都比pivot小，右边都大。这样pivot的位置就确定了。递归下去。有归并的味道。不过，归并是后期发力。快速一开始就会确定一个位置。
package Sort;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr= {5,3,8,6,4,9,10,5,6};
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr,int left,int right) {
if(arr==null || arr.length==0)
return;
if(left>=right)
return;
int pivot=partition(arr,left,right);
quickSort(arr,left,pivot-1);
quickSort(arr,pivot+1,right);
}
private static int partition(int[] arr,int left,int right) {
int pivot=left;
int pivotKey=arr[left];
while(left<right) {
while(left<right&&arr[right]>=pivotKey)
right--;
while(left<right&&arr[left]<=pivotKey)
left++;
swap(arr,left,right);
}
if(left!=pivot)
swap(arr,left,pivot);
return left;
}
private static void swap(int[] arr,int i,int j) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
- 复杂度
- 时间上，平均nlog(n)。
- 空间上，n。辅助空间o(1)
7. 堆排序
- 思想：首先，调整数组到满足堆性质。大顶堆，即数组第1个数最大。然后交换首末数。这样最后面的数最大。调整堆。
package Sort;
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int[] arr= {5,3,8,6,4,9,10,5,6};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
for(int i=arr.length/2-1;i>=0;i--) { //下标为arr.length/2-1，才开始有子叶
heapAdjust(arr,i,arr.length-1);
}
for(int i=arr.length-1;i>0;i--) {
int temp=arr[0];
arr[0]=arr[i];
arr[i]=temp;
heapAdjust(arr,0,i-1);
}
}
private static void heapAdjust(int[] arr,int start,int end) {
int temp=arr[start];
int i=2*start+1;
while(i<=end) { //子节点是2*i+1 2*i+1
if(i<end&&arr[i]<arr[i+1])
i++;
if(temp>=arr[i]) //满足堆性质
break;
arr[start]=arr[i];
start=i; //开启下一轮,确定下标i位置是否满足性质
i=2*start+1;
}
arr[start]=temp;
}
}
- 复杂度
- 时间上，o(nlog(n))。
- 空间上，n。辅助空间o(1)
8. 基数排序
- 思想：借助多关键字排序思想对单逻辑关键字进行排序的方法。如果对数字进行排序，那么个位、十位、百位就是不同优先级的关键字，如果要进行升序排序，那么个位、十位、百位优先级一次增加。基数排序是通过多次的收分配和收集来实现的，关键字优先级低的先进行分配和收集。
package Sort;
import java.util.*;
public class RadixSort {
public static void main(String[] args) {
int max=100;
int min=1;
int[] arr = new int[10];
Random random = new Random(47);
for (int i=0; i<10; i++) {
int s = random.nextInt(max)%(max-min+1) + min;
arr[i]=s;
//System.out.println(s);
}
//int[] arr= {5,3,8,6,4,9,10,5,6,12,123};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void radixSort(int[] arr) {
if(arr==null || arr.length==0)
return;
int arrMax=getMax(arr);
int maxBit = (arrMax+"").length();
for(int i=1;i<=maxBit;i++) {
List<List<Integer>> buf=distribute(arr,i,maxBit);
collect(arr,buf);
}
}
public static void collect(int[] arr,List<List<Integer>> buf) {
int k=0;
for(List<Integer> bucket:buf) {
for(int ele:bucket) {
arr[k++]=ele;
}
}
}
public static List<List<Integer>> distribute(int[] arr,int bit,int maxBit){
List<List<Integer>> buf = new ArrayList<List<Integer>>();
for(int i=1;i<=10;i++)
buf.add(new LinkedList<Integer>());
for(int i=0; i<arr.length; i++) {
buf.get(getNBit(arr[i], bit)).add(arr[i]);
}
return buf;
}
public static int getNBit(int x, int n) {
String sx = x + "";
if(sx.length() < n)
return 0;
else{
return sx.charAt(sx.length()-n)-'0';
}
}
public static int getMax(int[] arr) {
int max=arr[0];
for(int i=1;i<arr.length;i++){
if(arr[i]>max){
max=arr[i];
}
}
return max;
}
}
- 复杂度
- 时间上，o(d(n+rd))
- 空间上，n+rd。辅助空间o(rd)
总结（来源“算法爱好者”）
在前面的介绍和分析中我们提到了冒泡排序、选择排序、插入排序三种简单的排序及其变种快速排序、堆排序、希尔排序三种比较高效的排序。后面我们又分析了基于分治递归思想的归并排序还有计数排序、桶排序、基数排序三种线性排序。我们可以知道排序算法要么简单有效，要么是利用简单排序的特点加以改进，要么是以空间换取时间在特定情况下的高效排序。但是这些排序方法都不是固定不变的，需要结合具体的需求和场景来选择甚至组合使用。才能达到高效稳定的目的。没有最好的排序，只有最适合的排序。
下面就总结一下排序算法的各自的使用场景和适用场合。
从平均时间来看，快速排序是效率最高的，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是，在n较大时归并排序使用时间较少，但使用辅助空间较多。
上面说的简单排序包括除希尔排序之外的所有冒泡排序、插入排序、简单选择排序。其中直接插入排序最简单，但序列基本有序或者n较小时，直接插入排序是好的方法，因此常将它和其他的排序方法，如快速排序、归并排序等结合在一起使用。
基数排序的时间复杂度也可以写成O(d*n)。因此它最使用于n值很大而关键字较小的的序列。若关键字也很大，而序列中大多数记录的最高关键字均不同，则亦可先按最高关键字不同，将序列分成若干小的子序列，而后进行直接插入排序。
从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为O(n^2)的简单排序也是稳定的。但是快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。稳定性需要根据具体需求选择。
上面的算法实现大多数是使用线性存储结构，像插入排序这种算法用链表实现更好，省去了移动元素的时间。具体的存储结构在具体的实现版本中也是不同的。
