java---8种排序
2020-12-13 16:16
标签：覆盖 相同 思想 length 递归 new 冒泡排序 mil 最大的 1：冒泡排序 （可改进） 定义一个flag=false；如果有交换就将flag=true；在每一轮排序后判断 for(int i=0;j java---8种排序 标签：覆盖 相同 思想 length 递归 new 冒泡排序 mil 最大的 原文地址：https://www.cnblogs.com/ytfantey/p/11613747.html for(int j=0;j
temp=arr[j]; //如果后一个比前一个大
arr[j]=arr[j+1]; //就交换
arr[j+1]=temp; //然后将标记置为true
flag=true;
}
} //每一轮之后判断是否交换过
if(flag==false){ //如果没有交换 就这一轮跳过
break;
}else{ //如果交换了，
flag=false; //就重置标记
}
}
2：选择排序 每一次选择最小的，使用记号min，和这一次找到的最小的索引minIndex，
for(int i=0;i
int min=arr[i]; //其对应的索引位minIndex
for(int j=1;j
min=arr[j]; //最小的min换做这个arr[j]
minIndex=j; //然后将标记，改为j
}
}
if(minIndex!=i){ //如果第一次找到的最小的不是第一个
arr[minIndex]=arr[i]; //就将第一次找到的那个最小的编号值用第一个覆盖
arr[i]=min; //第一个arr[0]就用min覆盖，实际上是交换
}
}
3：插入排序，每一次从后面找一个数字，插入到前面有序数列之中。
for(int i=1;i
for(int j=i;j>0;j--){
if(arr[j]>arr[j-1]){
temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=arr[j];
}
}
}
注解：第一次循环i=1时候，j=1,调整arr[j]与arr[j-1]也就是第一个数，与第二个数的位置关系，
第二次循环i=2时候，j=2,调整arr[j]与arr[j-1]也就是第三个数，与第二个数的位置关系
j=1,
4：希尔排序，思想：将一个数组的个数逐渐二分成两个数组，
for(int gap=arr.length/2;gap>0;gap=gap/2){ //gap为将数组逐渐二分
for(int i=gap;i
if(arr[j]>arr[j+gap]){ //如果满足，则交换
temp=arr[j];
arr[j]=arr[j+gap];
arr[j+gap]=temp;
}
}
}
8，7，6，5，4，3，2，1 =>> 长度arr.length=7
第一轮：gap=4,i=4--7,j=0--3,判断条件之后交换结果为。 4，3，2，1，8，7，6，5
第二轮：gap=2,i=2--7,
i=2时：j=0,交换4与2，交换之后为： 2，3，4，1，8，7，6，5
i=3时：j=1,0
j=1,交换3与1，交换之后为： 2，1，4，3，8，7，6，5
j=0,不满足条件，无法交换2与4
i=4时：j=2,1,0
j=2,交换arr[j]与arr[j+gap]发现不满足条件，无法交换
j=1,交换arr[1]与arr[3],发现也不满足
j=0,交换arr[0]与arr[2],发现也不满足
i=5:j=3,2,1,0
j=3,交换arr[3]与arr[5],发现不满足条件无法交换
j=2,交换arr[2]与arr[4]，发现不满足条件，无法交换
。。。。。。。。
i=6时：j=4,3,2,1,0
j=4,交换arr[4]与arr[6],8比6大，交换后为：2，1，4，3，6，7，8，5
j=3,2,1,0 都不满足两个一组的前者比后者大
i=7时：j=5,4,3,2,1,0
j=5 2,1,4,3,6,5,8,7
j=4,3,2,1,0 波不满足两个一组的前者比后者大
第三轮：gap=1,i=1--7
这一轮交换的原理变为每相邻的两个，前者比后者大就交换
i=1时：j=0, arr[0]与arr[1] 1,2,4,3,6,5,8,7
i=2时：j=1,0 arr[1]与arr[2] 2比4小，无法交换 5：快速排序，
将数组按照sratrnum，分为比startnum大，比startnum小的两个前后数组
然后将startnum置换为前一个数组的最后一个（或者后一个数组的第一个），再按照新置换的
进行递归快速排序
public static void quicksort(int [] arr,int left,int right){ //传入数组，和起始索引
int i= left; //记下起始索引，
int j=right;
int temp; //定义temp，用于交换
int startnum=arr[left] //定义startnum
if(left>right){return ;} //如果
while(i
while(i
while(i
temp=arr[i];arr[i]=arr[j];arr[j]=temp;//交换
}
arr[left]=arr[i];arr[i]=startnum; //将startnum重改
quicksort(arr,i+1,right);
quicksort(arr,left,j-1);
}
6：归并排序
7：基数排序（桶排序)
public static void TongSort(int []arr){
int max=arr[0];
for(int i=1;i
int maxLength=(max+"").length; //最大的数为几位数
int [][] bukcet=new int[10][arr.length];//十个存放尾数相同的桶
int []bukcetcounts=new int[10]; //上一步每一个桶里面放的数量
bucketcounts[0]=1 表示末尾为0的桶放了1个数
for(int i=0,n=1;i
bucket[digitOfElement][bucketcounts[digitOfElement]]=arr[j];
//上一步，首先我们有bucket[10][arr.length]的十个桶,如果得到123尾数为3，
//bucket[digitOfElement][bucketcounts[digitOfElement]]
//bucket[digitOfElement][]这一个表示尾号全部为3的一列arr.lengt的桶，
//bucketcounts[digitOfElement]表示arr.length这一列桶的上下位置
//bucketcounts[digitOfElement]++ 表示元素的个数
bucketcounts[digitOfElements]++;
}
int index=0;
for(int k=0;k
for(int l=0;l
}
}
bucketcount[k]=0;
}