排序在算法学习中占用很重要的地位，也很实用。就用这篇博客来总结一下常用的几种排序算法。
冒泡排序
在水中，大的泡泡会往上浮。
在冒泡排序中，通过不断交换两个相邻的数据，使大的（或小的）数字往数组头部移动。最终将数组全部排序。
如上图所示
数组 [4,6,7,5]。我们将这个数组降序排列。
首先从数组最后一个数开始，依次与他前一个数比较，如果大于前一个数，交换。这样经过一轮循环。我们将最大的数放到了数组index=0的位置。
然后继续上述操作，将数组中第二大的元素移至index=1的位置。
依次下去，直到完成数组的排序。
代码
public class BubbleSort {
public void sort(int[] src)throws Exception {
if(src==null||src.length==0)
throw new Exception("参数错误");
for(int i=1;i<src.length-1;i++) { //循环，将所有数字放到正确的位置
for(int j=src.length-1;j>=i;j--) { //将第i大的数字方法正确的位置
if(src[j]>src[j-1])
swap(src,j,j-1);
}
}
}
private void swap(int[] src,int index_a,int index_b) {
int temp=src[index_a];
src[index_a]=src[index_b];
src[index_b]=temp;
}
public static void main(String[] args) {
BubbleSort bubbleSort=new BubbleSort();
int[] src= {90,70,30,80,60,10,40,50,20};
try {
bubbleSort.sort(src);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
for(int i=0;i<src.length;i++) {
System.out.println(src[i]);
}
}
}
时间复杂度
最坏的情况，就是数组本来是升序的，要将其变为降序的。共需要进行1+2+3+。。。+n-1=n*（n-1）/2次比较和交换操作，时间复杂度是o(n^2)。没有额外使用空间来存储中间变量，空间复杂度是o(1)。最好的情况，数组已经是排序好的，只需要遍历一遍，时间复杂度是o(n)。
插入排序
如果你打扑克，并且喜欢将手里的牌按顺序排好，那么你一定会插入排序。
在插入排序中，我们维护一个有序数组，每来一个数字，我们将他插入到有序数组中，使该数组仍然有序。直到我们将所有的数字都插入到合适的位置。
如上图所示，我们在数组前部维护一个有序序列，然后依次将数字插入到有序序列的适合位置，直到所有数字都插入到有序数列中。
代码
public class InsertSort {
public void insertSort(int[] src)throws Exception {
if(src==null||src.length==0)
throw new Exception("参数错误");
int temp=0;
int i,j;
for(i=1;i<src.length;i++) {
if(src[i]>src[i-1]) {
temp=src[i];
for(j=i-1;src[j]<temp&&j>=0;j--) { //将第I个数组插入到合适的位置
src[j+1]=src[j];
}
src[j+1]=temp;
}
}
}
public static void main(String[] args) {
InsertSort insertSort=new InsertSort();
int[] src= {90,70,30,80,60,10,40,50,20};
try {
insertSort.insertSort(src);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
for(int i=0;i<src.length;i++) {
System.out.println(src[i]);
}
}
}
时间复杂度
在最坏的情况下，也就是数组本来是升序的，我们要把它变为降序的，共需要1+2+3+。。+n-1次比较和移动，时间复杂度是o(n^2)。最好情况下，数组本来就是排序好的，只需要遍历一遍就行，时间复杂度是o(n)
快速排序
快速排序的思想是从数组中取一个数，将这个数字放到适合的位置，使它前面的数字比它小（或者大），后面的数字比它大（或者小）。这样就将数组分为两个部分，然后依次对这两个子数组进行相同的操作，直到所有数组都在正确的位置。
如上图所示，我们使用两个指针，一个指向数组最左，一个指向数组最右。将最左的数作为基准值。先拿基准值和右边指针指向的数组进行比较，如果基准值较小，交换两个指针的值。移动左边指针，再比较基准值和左边的指针指向的数字，重复操作。直到将基准值放到合适的位置上。这就将数组分成了两部分，然后再分为对这两部分做同样的操作，直到所有数组都在正确的位置上。
代码
public class QuickSort {
public void quickSort(int[] src)throws Exception {
if(src==null||src.length==0)
throw new Exception("参数错误");
partition(src,0,src.length-1);
}
public void partition(int[] src,int start,int end) {
if(start>=end)
return;
int key=src[start];
int i=start;
int j=end;
while(i<j) {
while(i<j&&src[j]>=key)
j--;
if(i<j)
src[i]=src[j];
while(i<j&&src[i]<=key)
i++;
if(i<j)
src[j]=src[i];
}
src[i]=key;
partition(src,start,i-1);
partition(src,i+1,end);
}
public static void main(String[] args) {
QuickSort quickSort=new QuickSort();
int[] src= {90,70,30,80,60,10,40,50,20};
try {
quickSort.quickSort(src);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
for(int i=0;i<src.length;i++) {
System.out.println(src[i]);
}
}
}
时间复杂度
快速排序的递归中，数组形成了一个二叉树，快速排序的时间复杂度和二叉树的高度有关。在这个二叉树中，每一层的时间复杂度是n，树的高度与key值的选择有关。如果选择的key值恰好能将数组等分成两半，则树的高度是log(n)，如果key值只能将数组分成一份，则数的高度是n。所以，快速排序的时间复杂度最好是n*log(n)，最坏是n^2。
快速排序优化
如果key值取得不好，那快速排序的时间复杂度最坏可能是n^2。key值取恰好能将数组平分为最好。因此有对于key值得优化方法，如三数区中法（三个数中间值作为key值），和随机法（随机取key值）。
堆排序
堆排序是基于堆这种数据结构的一种排序算法。
堆是一颗完全二叉树，堆有最大堆和最小堆。最大堆中每个父节点都比它的子结点大，最小堆中每个父节点都比它的子结点小。
因此，堆有以下的性质：
1.堆中根结点是最大值或者最小值。
2.将堆层序遍历的结果放入数组中（数组index从0开始），index=a的两个子结点是2a+1和2a+2
在了解了堆以后，我们来说以下堆排序。堆排序中，首先将数组元素构建成堆（最大堆和最小堆），然后将堆中根结点和堆中最后一个结点交换，重新构建堆。直到将所有的元素排序成功。
代码
public class HeapSort {
public void headSort(int[] src)throws Exception {
if(src==null||src.length==0)
throw new Exception("参数错误");
for(int i=(src.length-2)/2;i>=0;i--) {
heapAdjust(src,i,src.length-1);
}
for(int i=src.length-1;i>0;i--) {
swap(src,0,i);
heapAdjust(src,0,i-1);
}
}
public void heapAdjust(int[] src,int start,int end) {
int temp=src[start];
int j=start*2+1;
for(j=start*2+1;j<=end;j=j*2+1) {
if(j<end&&src[j]<src[j+1])
j++;
if(temp>=src[j])
break;
src[start]=src[j];
start=j;
}
src[start]=temp;
}
public void swap(int[] src,int index_a,int index_b) {
int temp=src[index_a];
src[index_a]=src[index_b];
src[index_b]=temp;
}
public static void main(String[] args) {
HeapSort heapSort=new HeapSort();
int[] src= {90,70,30,80,60,10,40,50,20};
try {
heapSort.headSort(src);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
for(int i=0;i<src.length;i++) {
System.out.println(src[i]);
}
}
}
时间复杂度
构建堆的时间复杂度是o(n)，第a次交换堆顶元素并重建堆的时间复杂度是log(a)，共需要交换n-1次。因此，时间复杂度是log(1)+log(2)+...+log(n-1)=nlog(n)。堆排序的时间复杂度对原始数组的排列不敏感，最好最坏平均的时间复杂度都是nlog(n)。
归并排序
快速排序，堆排序都用到了二叉树的高度是log(n)。归并排序也是如此。
假设原始数据长度为n，归并排序先将数据一分为2，长度分别是n/2。然后对子数组继续二分，直到每个数组长度为1。然后对数组两两进行归并和排序，直到恢复原始数据长度。如下图所示。
上图中，首先对数据进行二分，直到子数组长度为1。然后对数组进行合并，排序，直到恢复原始数组长度。
代码
public class MergeSort {
public void mergeSort(int[] src)throws Exception {
if(src==null||src.length==0)
throw new Exception("参数错误");
sort(src,0,src.length-1);
}
public void sort(int[] src,int start,int end) {
if(start>=end)
return;
int mid=(start+end)/2;
sort(src,start,mid);
sort(src,mid+1,end);
merge(src,start,mid,end);
}
public void merge(int[] src,int start,int mid,int end) {
int[] temp=new int[end-start+1];
int index=0;
int i=start;
int j=mid+1;
while(i<=mid&&j<=end) {
if(src[i]<=src[j]) {
temp[index]=src[i];
i++;
index++;
}else {
temp[index]=src[j];
j++;
index++;
}
}
while(i<=mid) {
temp[index]=src[i];
i++;
index++;
}
while(j<=end) {
temp[index]=src[j];
j++;
index++;
}
for(index=0;index<temp.length;index++) {
src[start+index]=temp[index];
}
}
public static void main(String[] args) {
MergeSort mergeSort=new MergeSort();
int[] src= {50,10,90,30,70,40,80,60,20};
try {
mergeSort.mergeSort(src);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
for(int i=0;i<src.length;i++) {
System.out.println(src[i]);
}
}
}
时间复杂度
归并排序在分解数组的时候时间复杂度是1，在合并数组的时候，时间复杂度是n，并且合并的次数是log(n)，因此总的时间复杂度是nlog(n)。并且归并排事件复杂度序对原始数据不敏感，最好，最坏，平均事件复杂度都是nlog(n)。
几种排序算法分析
