Java快速排序算法不能正常工作
Java快速排序算法不能正常工作
提问于 2013-06-10 10:55:32
我有两个Arraylist，由于第二个Arraylist(类型为double)中的值，排序应该是降序的。基本上，不考虑第一个数组列表的值，但是第一个数组列表中的元素映射到第二个数组中的元素，因此由于Arraylist2中的值，这两个数组都应该得到排序。(我希望这或多或少是清楚的)
问题：
不知何故，当我在排序后打印出Arraylist2的值(带有双值)时，它们完全没有排序，而是有一个与排序前不同的顺序。我还编写了一些调试system.outs，它显示了algoritm正在运行，但我不知道为什么它不能正确排序，我希望有人能看到问题所在。
代码：
Call + Outputcode：
String str = "";
// DEBUG //
for(int k = 0; k < test.size(); k++) {
str += " " + test.get(k);
}
System.out.println(str);
System.out.println("------------------------------------------------------------------/r/n");
sort(items, test, 0 ,(test.size() -1));
String str2 = "";
for(int k = 0; k < test.size(); k++) {
str2 += " " + test.get(k);
}
System.out.println(str2);
// DEBUG //快速排序algoritm：
public void sort(ArrayList<Item> items, ArrayList<Double> nutzen, int l, int r) {
if(l < r) {
double pivot = nutzen.get(r);
int p = partition(items, nutzen, l, r, pivot);
sort(items, nutzen, l, p-1);
sort(items, nutzen, p+1, r);
}
}
private int partition(ArrayList<Item> items, ArrayList<Double> nutzen, int l, int r, double pivot) {
int i = l;
int j = r-1;
do {
do {
i = i + 1;
} while(i < r && nutzen.get(i) > pivot);
do {
j = j - 1;
} while(j > l && nutzen.get(i) < l);
if(i < j) {
// Tausche Daten
double tmp = nutzen.get(i);
Item tmp2 = items.get(i);
nutzen.set(i, nutzen.get(j));
nutzen.set(j, tmp);
items.set(i, items.get(j));
items.set(j, tmp2);
}
} while(i < j);
if (nutzen.get(i) > pivot) {
double tmp = nutzen.get(i);
Item tmp2 = items.get(i);
nutzen.set(i, nutzen.get(r));
nutzen.set(r, tmp);
items.set(i, items.get(r));
items.set(r, tmp2);
}
return i;
}示例输出：(第一个是未排序的Arraylist，第二个是排序的)
0.22540250447227192 0.5289855072463768 0.3245742092457421 0.35105028644175684 0.3773755656108597 0.2041172365666434 0.4091826437941473 0.33037437282902354 0.4383735705209657 0.28473648186173856 0.3422330097087379 0.25703446095478977 0.3373493975903614 0.2701873935264055 0.3221397891448653 0.34912891986062716 0.3018603018603019 0.31361550229474755 0.35785288270377735 0.27435456110154904 0.22781065088757396 0.27684563758389263 0.21881770349736923 0.4226451927769644 0.24628854206318995 0.3256219991270188 0.3844096293465801 0.3178254051228437 0.398093508851566 0.3544702638834187 0.20851528384279475 0.4041025641025641 0.21713772992373262 0.26014028667276606 0.3591307662981319 0.23153252480705622 0.27023319615912206 0.24333719582850522 0.29892573563755254 0.31568998109640833 0.27108784176847006 0.34125412541254124 0.279090113735783 0.3737704918032787 0.3326703132769766 0.22776967930029154 0.22143195827406353 0.27614293221229635 0.22866611433305717 0.533879374534624 0.28534031413612565 0.20782003213711836 0.21262837580829214 0.2137904468412943 0.2898398529797847 0.24622641509433962 0.3927108927108927 0.26053042121684866 0.3005334914048607 0.23183297180043383 0.24539571926331508 0.3479899497487437 0.4193054136874362 0.31155589123867067 0.31771595900439237 0.3897529734675206 0.3561643835616438 0.31221719457013575 0.477299880525687 0.2683881064162754 0.30484160191273163 0.20526154787396758 0.2362366474938373 0.3485633537447009 0.24390243902439024 0.2618308766485648 0.382782475019216 0.23864915572232645 0.466403162055336 0.31514030218933087 0.3074433656957929 0.3438485804416404 0.28774928774928776 0.29548816568047337 0.34277286135693213 0.5334967320261438 0.32756539235412474 0.2945334590009425 0.20973389355742297 0.25292242295430395 0.2336989640463132 0.328060522696011 0.4326647564469914 0.30530226274907124 0.3326499231163506 0.3077194219245682 0.2322235922729141 0.25569544364508395 0.3788049605411499 0.2476489028213166
------------------------------------------------------------------
0.22540250447227192 0.5289855072463768 0.466403162055336 0.4383735705209657 0.3897529734675206 0.4193054136874362 0.4226451927769644 0.29548816568047337 0.3479899497487437 0.3438485804416404 0.477299880525687 0.3561643835616438 0.4041025641025641 0.3326703132769766 0.3844096293465801 0.4091826437941473 0.34277286135693213 0.398093508851566 0.3485633537447009 0.3927108927108927 0.4326647564469914 0.3005334914048607 0.28534031413612565 0.31155589123867067 0.31771595900439237 0.31221719457013575 0.30484160191273163 0.3074433656957929 0.31514030218933087 0.5334967320261438 0.32756539235412474 0.2898398529797847 0.25292242295430395 0.28774928774928776 0.533879374534624 0.2945334590009425 0.20973389355742297 0.27614293221229635 0.26053042121684866 0.2683881064162754 0.3737704918032787 0.279090113735783 0.34125412541254124 0.27108784176847006 0.31568998109640833 0.29892573563755254 0.2336989640463132 0.27023319615912206 0.328060522696011 0.3591307662981319 0.26014028667276606 0.30530226274907124 0.3544702638834187 0.3178254051228437 0.3256219991270188 0.3326499231163506 0.3077194219245682 0.27684563758389263 0.2322235922729141 0.27435456110154904 0.35785288270377735 0.31361550229474755 0.3018603018603019 0.34912891986062716 0.3221397891448653 0.2701873935264055 0.3373493975903614 0.25703446095478977 0.3422330097087379 0.28473648186173856 0.33037437282902354 0.25569544364508395 0.3773755656108597 0.35105028644175684 0.3245742092457421 0.2618308766485648 0.382782475019216 0.23864915572232645 0.24390243902439024 0.2362366474938373 0.20526154787396758 0.24539571926331508 0.23183297180043383 0.24622641509433962 0.2137904468412943 0.21262837580829214 0.20782003213711836 0.22866611433305717 0.22143195827406353 0.22776967930029154 0.24333719582850522 0.23153252480705622 0.21713772992373262 0.20851528384279475 0.24628854206318995 0.21881770349736923 0.22781065088757396 0.2041172365666434 0.3788049605411499 0.2476489028213166回答 2
Stack Overflow用户
回答已采纳
发布于 2013-06-10 18:11:31
我已经很久没有整理排序算法了(哦，完全APIs的乐趣)，但这让我觉得很奇怪。
} while(j > l && nutzen.get(i) < l);最好是
} while(j > l && nutzen.get(i) < pivot);总之，一个建议。不要试图对10个数字排序，只报告退出，使用3或4进行尝试，更认真地调试代码的内部工作(在每一步，选择哪个枢轴，结果的子列表是什么，等等)。
Stack Overflow用户
发布于 2013-06-10 20:24:06
我才刚开始，所以我以前还没看过“快车”，但我想我已经成功了。只需要修改我评论的4行。另外，我将l改为左，r改为右，我改为a，j改为z，使我更容易跟踪。就像我说的，我还是个菜鸟，在我读comp专业的第一年，所以我不能评论这个实现有多好。对我来说，这似乎是一个很好的问题，我可以继续努力学习。希望它能帮助你走出一些而不是太“这是答案”-ish。
这些变化：
- 将左、右计数器进一步“外部”偏移1，以说明它们在比较之前会增加和减少。似乎并没有像以前那样解析整个范围。为了同样的效果，可以将内部do..while循环更改为while循环。
l改为pivot。你在比较一个值和一个索引。i是对的，所以我想那只是一个糟糕的结果。if (nutzen.get(a) > pivot)改为if (nutzen.get(a) < pivot)。在这一点上，我需要花更多的时间找出原因，而且我还有其他的事情需要去做。我只知道它没有用，呵呵。
我没有疯狂的测试它，但它似乎是有效的。我抄袭了你的6个样本值，并试用了它们，结果成功了。祝好运!
private static int partition(ArrayList<Double> items, ArrayList<Double> nutzen, int left, int right, double pivot) {
int a = left-1; //offset to account for do..while incrementing prior to comparison
int z = right; //offset to account for do..while decrementing prior to comparison
do {
do {
a++;
} while(a < right && nutzen.get(a) > pivot);
do {
z--;
} while(z > left && nutzen.get(z) < pivot); //compare to pivot, not index
if(a < z) {
double tmp = nutzen.get(a);
Double tmp2 = items.get(a);
nutzen.set(a, nutzen.get(z));
nutzen.set(z, tmp);
items.set(a, items.get(z));
items.set(z, tmp2);
}
} while(a < z);
if (nutzen.get(a) < pivot) { //changed > to <
double tmp = nutzen.get(a);
Double tmp2 = items.get(a);
nutzen.set(a, nutzen.get(right));
nutzen.set(right, tmp);
items.set(a, items.get(right));
items.set(right, tmp2);
}
return a;
}
.22540250447227192 0.5289855072463768 0.3245742092457421 0.35105028644175684 0.3773755656108597 0.2041172365666434
------------------------------------------------------------------
0.5289855072463768 0.3773755656108597 0.35105028644175684 0.3245742092457421 0.22540250447227192 0.2041172365666434页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/17022243
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号