一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 665|回复: 12
收起左侧

[学Java/C#] 求一个算法的解答

[复制链接] |试试Instant~ |关注本帖
donnice 发表于 2014-6-25 06:52:01 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
public class SYX_Quicksort{
public static void quicksort(int[] a){
quicksort(a,0,a.length-1);
}
public static int median3(int[] a, int left, int right){
int center = (left + right)/2;
if(a[center]<a[left])
SwapReferences(a,left,center);
if(a[right]<a[left])
SwapReferences(a,left,right);
if(a[right]<a[center])
SwapReferences(a,center,right);
SwapReferences(a,center,right-1);
return a[right-1];
}
public static void quicksort(int[] a, int left, int right){
int pivot = median3(a,left,right);
int i = left;
int j = right - 1;
for(;;){
while(a[++i] < pivot){}
while(a[--j] > pivot){}
if(i<j)
SwapReferences(a,i,j);
else
break;
}
SwapReferences(a,i,right-1);
quicksort(a,left,i-1);
quicksort(a,i+1,right);
}
public static void SwapReferences(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args){
int[] arr = {12,67,32,76,87,54,32,87,34,18,12};
quicksort(arr);
for(int i = 0; i<arr.length-1; i++)
System.out.print(arr[i]);
}

}
很不好意思的来求解答,上面是我所编写的快速排序的程序
已经通过编译器了,但不知为何一直显示下标溢出,我查了半天没发现什么错误……求解答

评分

1

查看全部评分

ytsr 发表于 2014-6-26 04:31:39 | 显示全部楼层
donnice 发表于 2014-6-26 00:04
我想面试官更在意我的思路以及能否实现一种算法,而不是拘泥于我如何完成这个算法

对于这么简单的排序问题,你是没有办法体现你的思路多牛逼的,但是可以体现你的编程风格是professional的。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| donnice 发表于 2014-6-25 07:20:26 | 显示全部楼层
我后来改了一下可以用了,此贴无需再回答
public static void quicksort(int[] a, int left, int right){
                int pivot = median3(a,left,right);
                int i = left;
                int j = right - 1;
                for(;;){
                        while(i<=a.length-2 && a[++i] < pivot){}
                        while(j<=a.length-2 && a[--j] > pivot){}
                        if(i<j)
                                SwapReferences(a,i,j);
                        else
                                break;
                }
                SwapReferences(a,i,right-1);
                if(left<i-1)
                quicksort(a,left,i-1);
                if(i+1<right)
                quicksort(a,i+1,right);
        }
这是我改进过的代码,主要是在下标游移的部分以及最后的quicksort这边做了改动,供大家参考
回复 支持 反对

使用道具 举报

 楼主| donnice 发表于 2014-6-25 07:51:09 | 显示全部楼层
顺便说一句:合并排序塞高!!!!
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-25 08:08:56 | 显示全部楼层
quicksort 我建议写3个部分
1. 主干部分, 调用递归.
2. 递归部分, divided
3. 分割部分,  partition
回复 支持 反对

使用道具 举报

ytsr 发表于 2014-6-25 08:18:37 | 显示全部楼层
donnice 发表于 2014-6-25 07:20
我后来改了一下可以用了,此贴无需再回答
public static void quicksort(int[] a, int left, int right){
...

for(;;)

看了好别扭
回复 支持 反对

使用道具 举报

 楼主| donnice 发表于 2014-6-25 08:23:46 | 显示全部楼层
readman 发表于 2014-6-25 08:08
quicksort 我建议写3个部分
1. 主干部分, 调用递归.
2. 递归部分, divided

主要算法差不多就好了,而且主干,递归,分割。。。。你确定你说的不是合并排序?
不过刚刚发现如果数组再加个元素的话这个算法还是有问题,而合并很好用
回复 支持 反对

使用道具 举报

 楼主| donnice 发表于 2014-6-25 08:24:18 | 显示全部楼层
ytsr 发表于 2014-6-25 08:18
for(;;)

看了好别扭

我的逻辑比较喜欢这种。。。当然你也可以用while
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-25 08:49:47 | 显示全部楼层
donnice 发表于 2014-6-25 08:23
主要算法差不多就好了,而且主干,递归,分割。。。。你确定你说的不是合并排序?
不过刚刚发现如果数组 ...

不是, 是为了防止错误.
回复 支持 反对

使用道具 举报

 楼主| donnice 发表于 2014-6-25 08:54:44 | 显示全部楼层
readman 发表于 2014-6-25 08:49
不是, 是为了防止错误.

有道理,下次试试多谢指教
回复 支持 反对

使用道具 举报

ytsr 发表于 2014-6-25 20:37:34 | 显示全部楼层
donnice 发表于 2014-6-25 08:24
我的逻辑比较喜欢这种。。。当然你也可以用while

跟你一个口味的面试官估计没有
回复 支持 反对

使用道具 举报

 楼主| donnice 发表于 2014-6-26 00:04:01 | 显示全部楼层
ytsr 发表于 2014-6-25 20:37
跟你一个口味的面试官估计没有

我想面试官更在意我的思路以及能否实现一种算法,而不是拘泥于我如何完成这个算法
回复 支持 反对

使用道具 举报

 楼主| donnice 发表于 2014-6-26 04:42:41 | 显示全部楼层
ytsr 发表于 2014-6-26 04:31
对于这么简单的排序问题,你是没有办法体现你的思路多牛逼的,但是可以体现你的编程风格是professional的 ...

好吧……
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 04:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表