（一）常见的排序算法
常见的排序算法分为四大种：插入排序，选择排序，交换排序，归并排序
插入排序：直接插入排序，希尔排序
选择排序：选择排序，堆排序
交换排序：冒泡排序，快速排序
归并排序：归并排序
这里我们先讲几个，剩下比较复杂的，我们单独讲
（二）插入排序
1.直接插入排序
直接插入排序就是我们默认第一个元素是有序的，然后我们把待排序的元素与有序元素中从右向左来找这个待排序的元素的位置，知道所有的记录插入完为止，得到一个新的有序序列
用代码层面来讲就是，当我们插入第i（i>=1）个元素时，我们前面的array[0]~array[i-1]已经排好序了，此时我们把array[i]与array[i-1]以及之前有序的元素比较，通过这种比较找到应该插入的位置，原来位置的元素顺序后移
代码实现
public static void insertSort(int[] array){
for (int i = 1; i < array.length; i++) {
int tmp=array[i];
int j=i-1;
for (; j > 0 ; j--) {
if (array[j]>tmp){
array[j+1]=array[j];
}else {
break;
}
}
array[j+1]=tmp;
}
}时间复杂度O（N^2）
空间复杂度O(1)
稳定性：稳定（稳定性就是如{1，4，3（1），3（2），5}排完序后为{1，3（1），3（2），4}3（1）是在3（2）后面的这样是稳定的）
但是这里如果将array[j]>tmp变为array[j]>=tmp就是不稳定的（本身是一个稳定排序可以实现为不稳定排序的，不稳定排序是不可以变成稳定排序的）
直接插入排序的数据越有序，排的越快 所以直接插入排序适用于待排序序列基本有序了
2.希尔排序（缩小增量排序）
希尔排序的基本思想是：先把待排序文件中分为多个组如（分组的个数由多到少），每组之内进行直接插入排序，然后重复上述分组和排序，当到达分组个数为1的时候，就完成了排序
注：当排序分组个数!=1的时候，我们叫做预排序，当分组个数为1的时候才是真正的排序
代码实现如下
我们分多少组有不同的分发，我这里是用每次分组缩减一半的方式
然后这里我们说每组都是一次直接插入排序，但是因为每组都不是连续的，所以改变一点
public static void shellSort(int[] array){
int gap= array.length;
while(gap>1){
gap/=2;
shell(array,gap);
}
}
//对每组进行直接插入排序
private static void shell(int[] array, int gap) {
//i=gap 是找到分组后第一组的第二个元素(因为直接插入排序默认第一个数是有序的)
for (int i = gap; i < array.length; i++) { //这里不用+gap，i++正好是下一组的下一个元素
int tmp=array[i];
int j=i-gap;
for (; j > 0 ; j-=gap) {
if (array[j]>tmp){
array[j+gap]=array[j];
}else {
break;
}
}
array[j+gap]=tmp;
}
}时间复杂度为O（N^1.25）~O（1.6*N^1.25）因为gap的取值方式很多，分组方式不固定，所以希尔排序的时间复杂度不固定
空间复杂度O（1）
稳定性：不稳定
希尔排序是对直接插入排序的优化，因为直接插入排序的数据越有序才排的越快，所以分组＞1的时候都是预排序，目的是让数组更有序徐，当分组=1的时候，数组就已经接近有序了，这样就会达到优化的效果
（三）选择排序
1.直接选择排序
每一次循环从待排序的元素中选出最小（最大）的一个元素（默认循环起始位置元素最小（最大）），存放在这一次循环的起始位置，知道全部待排序的元素排完
因为这个比较简单，所以我们直接看代码实现
public static void selectSort(int[] array){
for (int i = 0; i < array.length; i++) {
int tmp=i;
for (int j = i+1; j < array.length; j++) {
if (array[j]<array[tmp]){
tmp=j;
}
}
swap(array,i,tmp);
}
}直接选择排序的效率不是很好，实际中用的很少
时间复杂度O(N^2)
空间复杂度O（1）
稳定性：不稳定
（四）交换排序
基本思想：根据序列中的值，来交换两个记录序列中的位置
特点：将值大的记录向序列尾部移动，值小的记录序列前部移动
1.冒泡排序
冒泡排序是每一次循环，从前到后两两比较把大的交换放到后面，然后把数组中的最大值放到最后一位，然后每次循环都把未排序的值中最大值放到未排序中的最后面
代码实现如下
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length-1; i++) {
boolean flg=false;
for (int j = 0; j < array.length-1-i; j++) {
if (array[j]>array[j+1]){
swap(array,j,j+1);
flg=true;
}
}
if (flg==false){
break;
}
}
}时间复杂度O(N^2)
空间复杂度O(1)
稳定性：稳定排序
我们这里进行了优化。也就是每一趟判断这一次是否交换了，没交换就说明已经有序了，如果已经有序就不需要之后的排序了
2.快速排序
快速排序是一种二叉树结构的交换排序算法
基本思想为：取一个待排序元素序列中的元素作为基准值（通常取最左边的元素），按照该排序码将待排序集合分割成两个子序列，左子序列的值都小于基准值，右子序列都大于基准值，然后左右子序列都重复这个过程，直到所有元素都排列完成
代码实现（跟二叉树遍历的结构是很像的，就是内部代码有一些变化）
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
public static void quick(int[] array,int start,int end){
if(start>=end)return ;
int pivot=partitionHoare(array,start,end);
quick(array,start,pivot-1);
quick(array,pivot+1,end);
}
private static int partitionHoare(int[] array, int left, int right) {
int tmp=array[left];
int i=left;
while(left<right){
while(left<right&&array[right]>=tmp)right--;//这里注意一定要写>=||<=否则可能会死循环
while(left<right&&array[left]<=tmp)left++;
swap(array,left,right);
}
swap(array,i,left);
return left;
}按基准值划分为左右两半的方式有很多
上述我们用的是Hoare版：默认左边为基准值，先从右边找到一个比基准值大的元素，再从左边找一个比基准值小的元素，两者交换，如此往复，等到left=right的时候，我们就把基准值放到这里即可。
还有挖坑法：先把最左边的数据（left下标）存放到临时变量中，然后先从最右边（right下标）找到一个比临时变量小的数据放到left下标中，然后再从左向右找一个比临时变量大数据放到刚刚那个right下标中，如此往复，等left=right的时候，我们就把基准值放到这里即可
代码如下:
private static int partitionDig(int[] array, int left, int right) {
int tmp=array[left];
while(left<right){
while(left<right&&array[right]>=tmp)right--;
array[left]=array[right];
while(left<right&&array[left]<=tmp)left++;
array[right]=array[left];
}
array[left]=tmp;
return left;
}还有一个前后指针法：有两个指针，prev指针指向序列开头，cur指针指向prev的后一个位置，我们还是把第一个元素作为基准值，然后两个指针向后走，cur指针指向的元素大于基准值就继续向前走，此时prev不动，直到cur找到小于基准值的值，只有当cur找到小于基准值的时候，prev才向后走此时要判断prev下标是否等于cur，如果等于就继续走，不等于就要交换
代码实现如下
private static int partition(int[] array,int left,int right){
int prev=left;
int cur=left+1;
while(cur<=right){
if(array[cur]<array[left]&&array[++prev]!=array[cur]){
swap(array, cur, prev);
}
cur++;
}
swap(array, left,prev);
return prev;
}因为我们使用的是递归，类似二叉树的思想，所以我们的时间复杂度就是O(N*递归层数)
所以时间复杂度在最好情况下为O(N*logN)（二叉树），最坏情况下为O(N^2)（偏树）
空间复杂度就是递归层数，最好为O(logN),最坏为O(N)
3.快排的优化
因为快排可能会出现偏树，导致递归层数过高，所以我们的思路就是降低树的高度，来防止栈溢出，我们这里的方法叫三数取中法
那什么是三数取中法，这里简单来说一下，也就是取三个数（left下标值，right下标值和mid值），我们选取三个数中的中间数来作为这个基准值（与left下标值做交换），这样就能够一定程度上降低树的高度（如果是1，2，3，4，5这样顺序的，能够很好的降低）
private static int middleNum(int[] array,int left,int right){
int mid=(left+right)/2;
if(array[left]>array[right]){
if (array[mid]>array[left]){
return left;
} else if (array[mid]<array[right]) {
return right;
}else {
return mid;
}
}else {
//array[left]<array[right]
if (array[mid]<array[left]){
return left;
} else if (array[mid]>array[right]) {
return right;
}else {
return mid;
}
}
}
public static void quick(int[] array,int start,int end){
if(start>=end)return ;
int index=middleNum(array, start, end);
swap(array, start, index);
int pivot=partitionHoare(array,start,end);
quick(array,start,pivot-1);
quick(array,pivot+1,end);
}我们知道递归是十分消耗我们的栈空间的，有没有办法节省一下？我们之前学二叉树的时候发现，二叉树的结点大部分都分布在最后几层，也就是说对栈消耗最大的部分在后几层，那我们快排中，后几层的数据是很少的，而且趋于有序，这时我们就可以使用直接插入排序来直接处理后几层的数据，这样我们就可以减少对栈的使用了
public static void insertSort(int[] array,int left,int right){
for (int i = left+1; i <= right; i++) {
int tmp=array[i];
int j=i-1;
for (; j > 0 ; j--) {
if (array[j]>tmp){
array[j+1]=array[j];
}else {
break;
}
}
array[j+1]=tmp;
}
}
public static void quick(int[] array,int start,int end){
if(start>=end)return ;
//最后几层有更多的节点，使用更多的栈，但是最后层数节点中的数据很少且趋于有序，我们可以使用直接插入排序
if(end-start+1<=15){
insertSort(array, start, end);
}
int index=middleNum(array, start, end);
swap(array, start, index);
int pivot=partitionHoare(array,start,end);
quick(array,start,pivot-1);
quick(array,pivot+1,end);
}4.快排的非递归实现
我们这里使用栈来辅助我们实现，思路就是我们先把start，end下标放进去，然后我们调用partition方法来求pivot，然后我们看pivot的左边有没有两个元素，如果有下标放到栈中（因为只有一个元素的话，就说明这个元素也是有序的不需要放到栈里）右边一样处理，然后判断栈空不空，不空取出两个
public static void quickSortNor(int[] array){
int start=0;
int end= array.length-1;
Stack<Integer> stack=new Stack<>();
int pivot=partitionHoare(array,start,end);
if(pivot-1>start){
stack.push(start);
stack.push(pivot-1);
}
if(pivot+1<end){
stack.push(pivot+1);
stack.push(end);
}
while(!stack.isEmpty()){
end=stack.pop();
start=stack.pop();
pivot=partitionHoare(array,start,end);
if(pivot-1>start){
stack.push(start);
stack.push(pivot-1);
}
if(pivot+1<end){
stack.push(pivot+1);
stack.push(end);
}
}
}