算法描述
快速排序
算法思路
快速排序算法的基本思路为从数组中选择一个数为基准数，之后，将比基准数小的数放在左边，比基准数大的数放在右边（分为了两个区），之后将左边（小于基准数）与右边（大于基准数）再次进行上述操作，一直重复直到无法再分为止
用户输入n，使用随机数产生n个数放入到数组a中
调用递归方法
sort()
PS：下面的数组a是全局变量
算法实现
System.out.println("输入数值个数n：");
Scanner scanner = new Scanner(System.in );
int n = scanner.nextInt();
scanner.close();
a = new int[n+1];
//随机赋值，留下a[0]存放基准数
for (int i = 1; i < n+1; i++) {
a[i]= (int) (Math.random()*100);
}
//输出数组a
for (int i = 1; i < n+1; i++) {
System.out.print(a[i]+" ");
}
sort(1,n);
//输出排序后的数值
System.out.println("");
for (int i = 1; i <n+1 ; i++) {
System.out.print(a[i]+" ");
}
}
public static void sort(int m1,int m2){
int i,j;
if(m1<m2){
i=m1;
j=m2;
a[0]=a[i];//每次的基准数都是传入分区的第一个数
//当i=j，即是完成了该分区的排序
while (i != j) {
//从右边开始扫描，直到不满足条件（也就是发现了一个数小于基准数，放入到左边的分区）
while(a[j]>=a[0] && j>i){
j--;
}
if(i<j){
a[i]=a[j];
i++;
}
//从左边开始扫描，直到不满足条件（也就是发现了一个数大于基准数，放入到右边的分区）
while(a[i]<=a[0] && j>i){
i++;
}
if(i<j){
a[j]=a[i];
j--;
}
}
a[i]=a[0];//将之前的基准数赋值给a[i]
//i已经存放了基准数，所以以i为分界线分为两个区，继续递归
sort(m1,i-1);
sort(i+1,m2);
}
return;
}结果
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
