一、前言
? ? ? ? 最近在看算法公开课，听了很多老师讲了不少很有用的东西，但是只听不练很快就忘了，所以我还是选择以博客的方式巩固自己的学习。
二、排序算法概述
? ? ? ? 今天主要讲的是比较经典的六大排序算法：选择排序、冒泡排序、插入排序、归并排序、快速排序和堆排序，除此之外还有一个比较重点的基数排序，但是因为它是不基于比较的排序，所以用法不是很广泛，所以我也只讲解它的实现原理，不多做阐述，并且，在讲解之余，我也会穿插一些其他内容。
三、选择排序
? ? ? ? 选择排序是最基础的一种排序之一，它的实现方式是：对一个无序数组，先通过遍历查找整个数组的最大值放到最后一个，然后再对未排序部分继续查找最大值，直到查找完毕为止（当然也可选择最小值）。
? ? ? ? 举个例子就是：
? ? ? ? 有一个无序数组长度N=7，我所做的第一件事就是将数组从0到N-1遍历一遍，然后找到最大值7，?然后和第N-1，也就是最后一个数交换，之后变成了：
? ? ? ? 此时，最后一个数就已经排好了，所以在接下来的排序中，我们就可以不用管这个数了。现在我们再对前N-2也就是前6个数进行相同操作，将前六个数最大值5和最后第六个数交换，如下：
? ? ? ? 然后，第六个数也排好了，可以不用管了，再对前五个数进行操作：
? ? ? ? 重复操作直到对前0个数进行排序。
? ? ? ? 代码如下：
public static void selectsort(int[]arr){
if(arr==null||arr.length<2)
return;
for(int i=0;i<arr.length-1;i++){
int minindex=i;
for(int j=i+1;j<arr.length;j++){
minindex=arr[j]<arr[minindex]?j:minindex;
}
swap(arr,i,minindex);
}
}
public static void swap(int[]arr,int i,int j){
arr[i]=arr[i]^arr[j];
arr[j]=arr[i]^arr[j];
arr[i]=arr[i]^arr[j];
}? ? ? ? ?这里的交换操作，我用的是异或运算，异或运算的详细解析，见这份博客：异或运算
? ? ? ? 分析：我们最后看一下选择排序的时间复杂度：假设数组长度是N，那么我们外层for循环的复杂度就是O(N)，所以里面需要进行的循环次数从N到N-1，到N-2，是一个等差数组。所以一共循环的次数是N+N-1+N-2+...+1，复杂度是O(N^2)。
四、冒泡排序
? ? ? ? ·冒泡排序也是一种比较基础的排序，它的实现方法也是遍历数组，然后相邻元素一一进行比较，如果要升序排序的话，每次比较的时候都把大的那个放在后面，这样一轮循环下来，最后一个也就被排好了，然后和选择排序一样，固定排序好的那个数，对没有排序好的数继续进行操作，直到数组的每个数都被放到正确的位置。
? ? ? ? 流程如下：
?
?
?
?
?
? ? ? ? 一轮结束后，最大值已经放在最后一个，然后对前六个数继续操作。
代码：
public static void bubblesort(int[]arr){
if(arr==null||arr.length<2)
return;
for(int i=arr.length-1;i>=0;i--){
for(int j=0;j<i;j++){
if(arr[j]>arr[j+1])
swap(arr,j,j+1);
}
}
}
public static void swap(int[]arr,int i,int j){
arr[i]=arr[i]^arr[j];
arr[j]=arr[i]^arr[j];
arr[i]=arr[i]^arr[j];
}?分析：冒泡排序依然是要对数组进行遍历，依然是第一次遍历的长度是N，第二次是N-1,和选择一样，时间复杂度为O(N^2)。
五、插入排序
? ? ? ? 插入排序我认为和冒泡排序还是挺像的，它的实现方法是，给定一个无序数组arr，我们假设它最开始有序的长度是1，也就是arr的前1个数时有序的，这是肯定成立的。
? ? ? ? 之后从第二个数开始，我想要前2个数变的有序，我就需要将第二个数插入到前1个数都某个地方，使得前2 个数正好有序，如图：
????????
? ? ? ? 4要想和3构成的数组有序，就要选择合适的地方插入，4和3比较，4比较大，所以原地不动就可以。然后又来了个1：?
?
? ? ? ? 现在已知前2个数时有序的，那么1插入之后要想有序，必须插入到合适的位置上，1和4比较，4更大，所以1应该插入到4之前，于是1再和3比较，比3小，应该插入到3之前，但是3之前没有了，所以就把1放在第一个。
? ? ? ? ?那么前三个数也有序了，与此同理：下面的操作如下：
?
?
代码：
public static void insertsort(int[]arr){
if(arr==null||arr.length<2)
return;
for(int i=1;i<arr.length;i++){
for(int j=i-1;j>=0;j--){
if(arr[j]>arr[j+1])
swap(arr,j,j+1);
}
}
}
public static void swap(int[]arr,int i,int j){
arr[i]=arr[i]^arr[j];
arr[j]=arr[i]^arr[j];
arr[i]=arr[i]^arr[j];
}? ? ? ? ?分析：插入排序与前面两个排序的不同之处在于，它排序的好坏取决于数据的整齐程度，而冒泡排序和选择排序，不管原本的数组是什么样的，都要老老实实的遍历，最终结果也总是O(N^2)。但是插入排序的不同之处在于，在最优情况下，给定的数组的排好序的，也就是说每次只需要查看一下当前数是否比前一个数要大即可，复杂度是O（N)，而最差情况下给定的数组的逆序给定的，那么它需要执行的次数就和选择和冒泡一样了，是N+N-1+N-1+...1,为O(N^2)的复杂度。所以插入排序平均来说还是优于前两个排序的，但是由于我们说时间复杂度都是按照最坏的情况下计算的，所以我们依然将插入排序归类为O(N^2)的排序。
六、归并排序
? ? ? ? 从这个排序开始，都是比O(N^2)快的排序的，当然也相对前面三种排序更难理解一些。
? ? ? ? 归并排序的方法是：我想要排序一个数组，那我就先将数组等分成两部分，分别排序两个部分，然后再对排序好的两个部分再进行个排序不就好了？那么就递归调用，直到被划分的小数组只有两个的时候，我们开始排序。这样一来，很容易就得到两个排好序的子数组，现在对他们进行合并：怎么合并呢？我们需要一个长度为两个数组之和的辅助数组，通过双指针解决：
????????
? ? ? ? 首先两个指针分别指向两个数组的开头，比较大小，将小的那个放入数组，然后指针右移：
?
重复操作直到有一边越界为止：
? ? ? ? 然后有一边越界之后，退出循环，对没有将没有越界的一边的剩余的数加到辅助数组里去。
?
? ? ? ? 这样两个小数组就排好序了，接下来我们只需要将辅助数组一一对应的赋值给我们真实数组即可。然后把排好序的数组和另外一个等大的数组继续进行归并，直到整个数组都有序为止。
?????????代码：
public static void mergesort(int[]arr){
if(arr==null||arr.length<2)
return;
process(arr,0,arr.length-1);
}
public static void process(int []arr,int l,int r){
if(l==r)
return;
int mid=l+((r-l)>>1);
process(arr,l,mid);
process(arr,mid+1,r);
merge(arr,l,mid,r);
}
public static void merge(int[]arr,int l,int m,int r){
int[]help=new int[r-l+1];
int p1=l,p2=m+1;
int i=0;
while(p1<=m&&p2<=r){
help[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
}
while(p1<=m){
help[i++]=arr[p1++];
}
while(p2<=m){
help[i++]=arr[p2++];
}
for(i=0;i<help.length;i++){
arr[l+i]=help[i];
}
}? ? ? ? 分析：它的时间复杂度怎么计算呢?前面说了，我们将数组依次对半分开，然后对分开的子数组计算，那么分开之后看起来其实是一个二叉树，计算的次数就是二叉树的高logN，然后进行的merge又要遍历一整个长度的数组，所以算法时间复杂度应该是O(NlogN)，额外空间复杂度是辅助数组的长度O(N)。
七、快速排序
? ? ? ? 快速排序也是一个很经典的排序，它有几个不一样的版本，其实区别并不大。我们直接所3,0版本吧。3.0版本的快排就是在无序数组中任意选择一个数和最后一个数交换，然后将小于这个数的数放在数组的左边，大于这个数的数放在数组的右边，等于这个数的数放在数组的中间，递归着实现即可。所谓1.0版本就是选择最后一个值作为划分值，将小于等于它的放在左边，大于它的放在右边；所谓2.0版本就是依然选择最后一个数进行划分，小于它的放左边，大于它的放右边，等于它的放中间。
? ? ? ? 我们为了简便计算，通过2.0版本演示一下：
????????
?代码：
????????
public static void quicksort1(int []arr){
if(arr==null||arr.length<2)
return;
quicksort(arr,0,arr.length-1);
}
public static void quicksort(int[]arr,int l,int r){
if(l<r){
swap(arr,l+(int)(Math.random())*(r-l+1),r);
int[]p=partition(arr,l,r);
quicksort(arr,l,p[0]-1);
quicksort(arr,p[1]+1,r);
}
}
public static int[] partition(int[]arr,int l,int r){
int less=l-1;
int more=r;
while(l<more){
if(arr[l]<arr[r]){
swap(arr,++less,l++);
}else if(arr[l]>arr[r]){
swap(arr,--more,l);
}else {
l++;
}
}
swap(arr,more,r);
return new int[]{less+1,more};
}
public static void swap(int[]arr,int l,int r){
arr[l]=arr[l]^arr[r];
arr[r]=arr[l]^arr[r];
arr[l]=arr[l]^arr[r];
}? ? ? ? 复杂度依然和树结构相似，是O(NlogN）。
?八、堆排序
? ? ? ? 在介绍堆排序之前，我们先了解一下堆，堆其实就是一个二叉树，堆分为大根堆和小根堆，所谓大根堆就是指任何一颗树头结点都是最大的，小根堆同理，如下就是一个大根堆：
????????
? ? ? ? ?任何一棵树都比它子节点的值大，这就是大根堆，那么堆有哪些操作呢？
? ? ? ? 堆主要操作有两个，一个是插入一个元素后重新把大根堆转化为大根堆，一个是将堆中任何一个元素变化后，重新构建大根堆，具体方式在这就不多说了，直接上代码吧。
????????
public static void main(String[] args) {
int []arr={2,5,1,6,1,6,3,61,6,1,2,3};
heapsort(arr);
for(int a:arr){
System.out.println(a);
}
}
public static int[] heapsort(int[]arr){
//安排成大根堆
// for(int i=0;i< arr.length;i++){
// heapInsert(arr,i);
// }
//下面过程和上面一样，稍微快了一点
//变大根堆应该从下开始
for(int i=arr.length-1;i>=0;i--){
heapify(arr,i, arr.length);
}
int heapsize= arr.length;
swap(arr,0, --heapsize);
while(heapsize>0){
heapify(arr,0,heapsize);
swap(arr,0,--heapsize);
}
return arr;
}
public static void heapInsert(int[]arr, int index){
//循环停止的条件是两个，一个是当前节点并不比父亲节点要打，循环停止
//或者是到达头结点的时候，index和（index-1）/2都是0，那么依然不满足循环，退出循环
while(arr[index]>arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index=(index-1)/2;
}
}
public static void heapify(int []arr,int index,int heapsize){
int leftson = index*2+1;
while(leftson<heapsize){
int max=leftson+1<heapsize&&arr[leftson+1]>arr[leftson]?leftson+1 : leftson;
max = arr[max]>arr[index]?max:index;
if(max==index)
break;
swap(arr,index,max);
index=max;
leftson=index*2+1;
}
}
public static void swap(int[]arr,int i,int j){
arr[i]=arr[i]^arr[j];
arr[j]=arr[i]^arr[j];
arr[i]=arr[i]^arr[j];
}?
?
?