排序算法
一、插入排序
1、代码如下：
public static void insertSort1(int[]ints){
//i循环：从索引1开始一直到最后
for(int i=1;i
if(ints[i]< ints[i-1]){//i位置的值需要插入到前面位置
//j循环：从0开始到i前面
for(int j=0;j
if(ints[i]< ints[j]){//找到插入位置(j位置)
int temp = ints[i];
//k循环：将数据向后移动
for(int k=i-1;k >= j;k--){
ints[k+1]= ints[k];
}
ints[j]= temp;
break;
}
}
}
}
}
2、其实2个for循环也可以解决，代码如下：
public static void insertSort2(int[]ints){
for(int i = 1;i < ints.length;i++){
if(ints[i]< ints[i-1]){
for(int j = 0;j< i;j++){
if(ints[i]< ints[j]){
int temp = ints[i];
ints[i]= ints[j];
ints[j]= temp;
}
}
}
}
}
二、快速排序
/**
*快速排序
* @param ints需要排序的数组
* @param start开始位置
* @param end结束位置
*/
public static void fastSort(int[]ints,int start,int end){
if(start < end){
int index = sortUnit(ints,start,end);//获取标杆值所在的位置
fastSort(ints,start,index-1);//左边
fastSort(ints,index+1,end);//右边
}
}
/**
*返回标杆值在数组中的位置
* @param ints需要排序的数组
* @param start开始位置
* @param end结束位置
* @return
*/
public static int sortUnit(int[]ints,int start,int end){
int temp = ints[start];
int j = end;
int i = start;
while(i
while(i
if(ints[j]< temp){//j负责找到比标杆小的数，扔给i
ints[i]= ints[j];
break;
}
j--;
}
while(i
if(ints[i]>= temp){//j负责找到比标杆大的数，扔给j
ints[j]= ints[i];
break;
}
i++;
}
}
ints[i]= temp;//将标杆值放入到数组中
return i;
}
三、堆排序
public static void stackSort(int[]ints){
int size = ints.length;
while(size>2){
//建最大堆
//循环次数：父节点的个数，父节点索引
for(int i =(size-1)/2;i>=1;i--){
int maxIndex = i*2;//假设做儿子最大
//左儿子=父节点索引*2，右儿子=左儿子+1
if((maxIndex+1)< size && ints[maxIndex+1]> ints[maxIndex]){//假设有右儿子且右儿子比左儿子大
maxIndex++;//右儿子大
}
//最大的儿子与父亲比
if(ints[maxIndex]> ints[i]){
int temp = ints[maxIndex];
ints[maxIndex]= ints[i];
ints[i]= temp;
}
}
//根节点与最后一个节点交换
int data = ints[1];
ints[1]= ints[size-1];
ints[size-1]= data;
size--;
}
}
注：堆排序对数组的第一个元素不进行处理
四、冒泡排序
public static void bubbleSort(int[]ints){
for(int i=0;i
for(int j=0;j
if(ints[j+1]< ints[j]){
int temp = ints[j+1];
ints[j+1]= ints[j];
ints[j]= temp;
}
}
}
}
