首页 > 试题广场 >

下面程序的输出结果是什么。

[单选题]

下面程序的输出结果是什么。

public class A2{ 
public static void main(String[] args){
    int[] a={2,4,6,8,3,6,9,12};
    doSomething(a,0,a.length-1);
    for(int i=0;i<=a.length-1;i++)
    System.out.print(a[i]+" ");
} 
private static void doSomething(int[] a,int start,int end){
    if(start<end){
        int p=core(a,start,end);
        doSomething(a,start,p-1);
        doSomething(a,p+1,end);
    }
}
private static int core(int[] a,int start,int end)
{
    int x=a[end];
    int i=start;
    for(int j=start;j<=end-1;j++){
        if(a[j]>=x){
            swap(a,i,j);
            i++;
        }
    }
    swap(a,i,end);
    return i;
} 
 
private static void swap(int[] a,int i,int j) 
{
    int tmp=a[i];
    a[i]=a[j];
    a[j]=tmp;
}
}

```
找到最大值
```
```
找到最小值
```
```
从大到小的排序
```
```
从小到大的排序
```

查看答案及解析

轩0o0

其实意思很简单，有几个比最尾大的索引 i 就加多少，最后交换，也就是最尾元素他处于第几大的位置，不就是从大到小排序吗

发表于 2015-10-13 15:22:48 回复(0)

菜鸟羊头

这个排序算法虽然能实现从大到小排序，但看得人眼晕。。。

每次排序，先拿前面的值依次和末尾值比较，比末尾值大的则交换，每次排序最大的值放到末尾；关键还没完，还要再和前面的值交换，将最大值放到前面。。。

发表于 2015-07-08 16:00:43 回复(7)

每天学一点

  开始被注释迷惑了半天。

  按快排的思想，遍历数组将比x大的按顺序存至a[0]a[1]a[2]..此时j负责遍历数组，i负责依次指向下一次

  遍历判断得到的大于x的数该存储的位置，每一次成功存储向后移动一格

  swap(a,i,end);//把最大的放到i的位置  

  应该是将x交换至分界点，（
  x并非最大
  ）至此一趟core完成，x左侧大于x，x右侧小于x,x左右任是无序数列

  然后依据分治的思想，对左序列，右序列迭代。当分至每个序列只有一个元素序列必然有序。

  最终达到排序目的。(灵魂手绘轻喷)

发表于 2017-04-06 20:30:18 回复(5)

yyshiningyear

是快排吧总是以最后一个数作为区分大的放前面小的放后面然后递归两个区间

发表于 2015-08-13 23:52:30 回复(3)

红茶知道

//看我的注释这种快排的思路就很清晰了,这是只从一个方向遍历的快排
public class A2 {
	public static void main(String[] args) {
		int[] a = { 2, 4, 6, 8, 3, 6, 9, 12 };
		quickSort(a, 0, a.length - 1);
		for (int i = 0; i <= a.length - 1; i++)
			System.out.print(a[i] + " ");
	}

	private static void quickSort(int[] a, int start, int end) {
		if (start < end) {
			int p = core(a, start, end);
			quickSort(a, start, p - 1);
			quickSort(a, p + 1, end);
		}
	}

	private static int core(int[] a, int start, int end) {
		int x = a[end];
		int i = start;  //记录遍历完后最后一个数应该放在的位置,初始就是start,因为如果前面没有数比最后一个数大,那么下面遍历完后最后一个数就应该放在start的位置
		for (int j = start; j <= end - 1; j++) { //遍历的目的是把参与排序的这轮数中比最后一个数大的数都放到最后一个数前面
			if (a[j] >= x) {
				swap(a, i, j);   
				i++;  //每遇到一个比最后一个数大的数,最后一个数应该放的位置就+1
			}
		}
		swap(a, i, end); //这里一交换后就把最后一个数放在了正确的位置,这样左边的数都比最后一个数大,右边的数都比最后一个数小
		return i;
	}

	private static void swap(int[] a, int i, int j) {
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
}

发表于 2017-08-15 10:21:36 回复(3)

剑枫

这道题目的核心思想是：根据交换的次数，决定存储的位置，交换0次，存在第一位，代表最大，交换1次，存在第二位，代表次大，以此类推.....结果可以拿一个有序的递增序列进行验证，这样比较直观，而且简单粗暴

发表于 2016-04-26 11:10:58 回复(3)

zackH

快速排序，比较经常使用的方式可以参照下面两个网址。

介绍：http://blog.csdn.net/morewindows/article/details/6684558

演示：http://www.tyut.edu.cn/kecheng1/site01/suanfayanshi/quick_sort.asp

发表于 2016-08-28 09:53:40 回复(0)

JessciaChow

是快速排序的另一种实现。严蔚敏的教材上是选择第一个元素作为中枢，从两侧向中间扫描逼近，最后确定枢轴应该在的位置；而上面这种解法则是算法导论上的，选择最后一个元素作为枢轴，然后单侧扫描逼近，最后确定枢轴应该在的位置（根据用变量i记录的交换的次数决定最后一个元素是第i大，然后把它放在第i个位置）。每次确定枢轴应该在的位置这一点是相同的，不同的是确定枢轴位置的过程。

上面算法还可以比较一下i和j的值，i、j相等的时候不进行交换，可以减少交换次数。

编辑于 2016-12-16 11:46:04 回复(0)

闲逛的蚂蚁

利用划分的思想，每次划分时选取这一组的最后一个值作为划分点，比划分点大的放到左边，比划分值小的就放到了右边，每一次划分就确定了划分点的最终位置，然后再递归的划分左边部分和右边部分。

发表于 2016-06-10 23:46:42 回复(0)

笨小孩ovo

有没有和我一样的，看见

 int x=a[end];
if(a[j]>=x){
 swap(a,i,j);
 i++;
}

直接选了D，太马虎了，还没看见

 swap(a,i,end);

这波草率了，掉坑里了

发表于 2022-03-31 19:07:59 回复(2)

LSur

看这个代码，看到循环syso就知道结果不可能只有一个故排除A.B。

接着我用了假设法，假设原数组中，a[end]即数组的最后一位即是最大值，相当于core方法题中的for循环可直接跳出，然后执行swap(a,i,end)，由于此时的i就是start值且没有任何变化，所以就是将最大值放在了最前面，再结合递归、快排的思想，可以很快知道这是一个从大到小的排序。

发表于 2018-06-08 15:29:27 回复(0)

有事启奏^O^无事退朝

注释误导，直接看core函数就会发现它是实现快速排序的一个阶段这里a[j]≥x对应从大到小排序；若改为a[j]＜＝x则对应从小到大排序

发表于 2018-03-29 14:42:59 回复(1)

666666666.qq.com

第一轮的话，找出了最大值，第二轮的话，找到了最小值，那个core循环的作用是找到比这一轮中数组a最后一个值大的数放在左边，比它小的不变位置，然后再将最后一个值放到它该放的位置【即i的值】，那么它现在比这个数大的值放在左边，比它小的值放在右边，类似分治的方法。

发表于 2021-02-03 15:49:51 回复(0)

马超安安

快速排序以最后一个数为划分区间值，大于放左边，小于放右边，每次划分2个区间，再每个区间继续递归排序

发表于 2017-04-07 22:12:50 回复(0)

纤尘

intx=a[end];

inti=start;

for(intj=start;j<=end-1;j++){

if(a[j]>=x){

swap(a,i,j);

i++;//交换了几次

}

}//把最大的放到最后

swap(a,i,end);//把最大的放到i的位置

这边的重点是i和j都是从start开始，i的作用：数组a[i]放大于等于x的值，j的作用：为遍历整个数组

而存在的，就是要数组每个元素都和x对比。只要出现大于等于x（即是a[j]的值），就让a[i]和a[j]交换，

这个遍历完成一个数组就自然把大于x和小于x的数组放置两端（高明之处在于只做值交换）。最后就是根据i++来得到x（下标是end）排在交换后数组的位置，然后和它交换，就完成一次以a[end]的“中点”的

排列活动。

发表于 2016-09-03 16:26:55 回复(0)

牛客2619936号

这快排是写错了么？一般来说快排的确是需要两个指针i和j 也需要递归但是这两个指针应该是一个从前往后扫一个从后往前扫这怎么都从start开始呢

发表于 2016-08-11 21:32:47 回复(2)

郑斌coder

doSomething(a,start,p-1);
doSomething(a,p+1,end);

以上说明使用的是快排

swap(a,i,end);//把最大的放到i的位置

又进行一次交换，将挑选出的最大的一个放到i处

发表于 2016-07-18 08:03:24 回复(0)

YQmQY

很简单的快排

1. start < end 就是来判断结束的当排序的长度为一的时候，自然也就排序成功了

2. 逻辑：

（1）先和最后一个比，将比最后一个大的放在p之前，将比最后一个小的放在p之后，将最后一个放在p这个位置

（2）然后拆分为两个数组, 0 -> p-1的和 p + 1 -> end的然后重复（1）

（3）start < end 即当最后判断的数组为1时则不再排序，顺序自然而然成立

3. 改变从大到小还是从小到大，改变a[j] >= x为a[j] <= x即可

4.分析时间复杂度：

（1）最好情况就是刚好都是二分，那就是O(n logn)

（2）最坏情况就是每次都是最后一个最小（最大）,那就是和冒泡排序一样，那就是O(n²)

（3）考虑到只有最坏的情况是O（n²）,所以平均时间复杂度为O(nlogn)

5.由于采用递归的方法，所以空间占用较大

发表于 2022-06-18 19:56:38 回复(0)

吾名_孤鸿寄语默苍离

你们慢慢看吧...

发表于 2022-05-28 16:11:25 回复(0)

求对象的小狐狸很emo

dosomething方法是左右迭代，core方法是确定左右分界点，同时令左边始终大于x,右边始终小于x,这是分治思想，去看一下快速排序就懂了

发表于 2022-04-23 23:38:38 回复(0)

提交观点

问题信息

Java 排序

上传者：小小

难度：

109条回答 6242收藏 12332浏览

下面程序的输出结果是什么。

问题信息

热门推荐

相关试题