Java中的快速排序
程序员文章站
2022-03-16 19:14:28
...
import java.lang.reflect.Array;
import java.util.Arrays;
public class KSpx {
public static int getIndex(int []arr,int low,int high){
//基准数据
int temp=arr[low];
while (low<high){
//当队尾的元素大于等于基准数据时,向前挪动high指针
while (low<high && arr[high]>=temp){
high--;
}
//如果队尾元素小于temp了,需要将其赋值给low
arr[low]=arr[high];
//当队首元素小于等于temp时,向前挪动low指针
while (low<high && arr[low]<=temp){
low++;
}
//当队首元素大于temp时,需要将其赋值给high
arr[high]=arr[low];
}
//跳出循环时low和high相等,此时的low或high就是temp的正确索引位置
//由原理部分可以很清楚的知道low的位置的值并不是temp,所以需要将temp赋值给arr[low]
arr[low]=temp;
return low;//返回temp正确位置
}
public static void quickSort(int []arr,int low,int high){
if(low<high){
//找寻基准数据的正确索引
int index=getIndex(arr,low,high);
//进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
quickSort(arr,low,index-1);
quickSort(arr,index+1,high);
}
}
public static void main(String[] args) {
int []arr={3,5,1,6,8,7};
quickSort(arr,0,arr.length-1);
System.out.print(Arrays.toString(arr));
}
}
下一篇: 范围For 语句