八大排序
1.交换排序：
a.冒泡排序（相邻交换，最大在后）
外循环表示交换多少轮，内循环表示一轮交换多少次，两次循环
时间复杂度为O（n^2）
规律：
（1）外循环一共进行数组大小-1次循环（每循环一次排序一次）
（2）内循环每一次排序次数都在逐渐减小，（因为最大值已经在最后）
优化：如果发现某次排序一次交换都没有，那这个就是排序好的
// 优化
public static void sortwin(int a[]){
int zhuan=0;
// 标记后面一轮是否有过交换
boolean T=false;
// 所有论
for (int j = 0; j a[i+1]){
T=true;
zhuan=a[i];
a[i]=a[i+1];
a[i+1]=zhuan;
}
}
if (!T){
// 如果没有交换那证明已经排序完成
break;
}else{
// 重置
T=false;
}
}
// System.out.println(Arrays.toString(a));
}
b.快速排序（重点）
基础思想：
1.首先，会有一个基准值和一个左指针以及右指针（并且要有两个变量保存指针）
2.指针跟基准值比较，小的放在基准值左边，大的放右边（指针移动）
3.这样就会分成左边一个值小的分区和右边值大的分区
4.使用递归重复1，2的操作，直到每一个小分区只有1个数据
public static void quicksot(int nums[],int left,int right){
// 递归退出条件
if (left>right){
return;
}
// 因为后面交换中会更改两个指针，所以先保存
int l=left;
int r=right;
// 定义基准值
int pivot=nums[left];
while (l!=r){
// 45 ,30 , 61 , 82 , 74 , 12 , 26 , 49
// 45 ,30 , 26 , 82 , 74 , 12 , 61 , 49
// 45 ,30 , 26 , 12 , 74 , 82 , 61 , 49
// 12 ,30 , 26 , 45 , 74 , 82 , 61 , 49
// --------------------
// 12 ,30 , 26 , 45 , 74 , 82 , 61 , 49
// 从右边找到小于基准的值
while (nums[r]>=pivot && l2.插入排序
a.直接插入排序
内循环是移动左分区，外循环移动右分区，两次循环，时间复杂度为O（n^2）
规律：1.将整个数组分为两个分区，left有序区，和right无序区
2.左分区的数跟右分区一个一个比较，小于左分区，就左分区比较的那个值向后挪动
3.循环结束证明右分区的值大于左分区，此时leftindex+1才是插入的下标位置
注：下图中right保存了值，因为下面向后挪动会把值给挤掉
优化：当要插入的位置就是当前位置就不要插入
public void insert(int nums[]){
for (int j = 1; j =0 && nums[leftindex]>right){
// 向后挪动,为插入让出位置,之前理解有误,这里只是值往后挪,不是下标挪
nums[leftindex+1]=nums[leftindex];
// 有序列表向左移动,继续比较
leftindex--;
}
// 1,-1,2,4
// leftindex是要跟右分区比较值的下标,,但是由于要往左边移动,此时+1才是插入的下标
// 优化,如果=j证明插入的位置就是当前位置
if (leftindex+1!=j){
nums[leftindex+1]=right;
}
}
// System.out.println(Arrays.toString(nums));
}
b.希尔排序
希尔排序其实也是一种插入排序，是在插入排序的基础上优化的一种排序算法
有两种能够实现方式能够实现希尔排序：
原理：a.不断分组分到最后一组再进行其他排序
b.分组不断/2，直到为1
（1）交换实现希尔
（2）插入移动实现:在插入外面套一个循环分组
public void winxier(int num[]){
// 跟插入排序区别不大，外面加了个循环分组
// 分组
for (int fenzhu = num.length/2; fenzhu >0 ;fenzhu/=2) {
// 中层循环表示分成几个小组,且j=i指每个小组的后一个
for (int zhu = fenzhu; zhu=0 防止数组越界 num[leftindex]>right只有右边分区小于左边才会进去
while (leftindex>=0 && num[leftindex]>right){
// 左边分区值向后挪动
num[leftindex+fenzhu]=num[leftindex];
// 当前下标值比较完后，下标向左移动，又因为不属为i
leftindex-=fenzhu;
}
// 优化：当判断满足时证明leftindex移动了
if (leftindex-fenzhu!=zhu){
num[leftindex+fenzhu]=right;
}
}
}
// System.out.println(Arrays.toString(num));
}
3.归并排序
使用归并思想实现的排序方法，采用分治的策略，将问题分成多个小问题进行递归求解---分而治之
基本思路：合并次数等于数组长度-1
1.整体分为分 - 治
2.分，怎么分？通过递归向下分，到只有两个数比较为止
3.治，如何治？递归回溯向上合并，在分到最底部开始，
a.比较两个数大小，并使用一个临时数组temp临时储存
b.如果两个序列（最少有1个值）比较完，一方序列还有值，就将剩余的全部放到临时数组temp
c.将临时数组的值再copy到原数组
假如有此数组int nums[]={8,4,5,7,1,3,6,2};
会实现合并7次
//拆分在合并
public static void diguisort(int left,int right,int nums[],int temp[]){
if (left4.基数排序
基础思路：（用空间换时间）
1.首先有10个桶，因为用的是十进制数
2.每一趟呢就按位数存在桶里，取回原数组
3.会有多少趟？看最大数的位数，假如最大数为345此时最大位数n=3，有3趟
5.选择排序
a.简单选择排序
跟冒泡有丢相似的地方，冒泡大的往后冒，选择是小的往前选
外循环表示交换多少轮，内循环表示找到最小值，两次循环
时间复杂度为O（n^2）
规律：
（1）有数组大小-1轮排序
（2）每一轮排序又会通过循环找到一个最小值
（3）如第一轮找到最小值(1--length)与第一个值a[0]交换，第二轮排序就从
(2--length)里找最小值，找到后与a[1]交换
（4）初始化时定义一个最小值和最小值下标
优化：定义的下标值改变后才交换，没有改变就是当前就是最小值
注：如下图A步骤那里刚开始时一直想着感觉就是保存了最小值，可以拿到下面B步骤那里一起交换，后来发现一直不行，debug半天才发现，里面那个循环，如果不重置最小值的话就会找到最后一个比min小的值而不是最小值，因为最小值min一直没有重置
public static void jishu(int nums[]){
// 求最大数
int max=nums[0];
for (int i = 1; i < nums.length ; i++) {
if (maxb.堆排序