写了一个快速排序，但是有bug，困扰了很久 - 黑马程序员技术交流社区

黑马程序员技术交流社区

标题:

作者:

时间:

标题:

本帖最后由、zhi 于 2013-5-27 12:44 编辑

package com.itheima;
import java.util.Random;
import org.junit.Test;
public class Test1 {
int i = 0; //定义一个整型的i记录排序的次数
public static void main(String[] args) {
Test1 T = new Test1();
// int[] arr = {49,38,65,97,78,13,27};
int[] arr = { 49, 38, 65, 97, 78, 13, 27, 12, 11 }; //实例化一个数组
System.out.println("初始化数组为：");
printArray(arr); //把数组打印出来
T.Run(arr, 0, arr.length - 1); //开始排序
}
public void Run(int[] arr, int begin, int end) { //一个递归，不断的对数组进行排序
if (begin < end) { //只有开始索引比结束索引小的时候才进行排序
int key = getMiddle(arr, begin, end); //进行排序并返回中间值的位置
Run(arr, begin, key - 1); //对中间的左边进行递归
Run(arr, key + 1, end); //对中间的右边进行递归
}
}
public int getMiddle(int[] arr, int frist, int last) {
int begin = frist; //开始索引等于数组第一个下标
int end = last; //结束索引等于数组长度减一
int key = frist; //基准数的索引等于数组的第一个索引
while (begin < end) { //每当开始索引小于结束索引的时候都不断的排序
while (begin < end && arr[end] > arr[key]) { //从数组的结束索引开始不断向前找，直到找到一个比基准数小的数位置，然后进行交换
end--; //找不到就向前走
if (end == key) { //如果结束索引等于开始索引了，那就要结束循环
break;
}
}
key = swap(arr, key, end); //找到了，就交换数据，并返回基准数交换后的索引
i++; //每次交换都统计次数
System.out.println("第" + i + "次结果为");
printArray(arr); //输出这次交换后的数组
while (begin < end && arr[begin] < arr[key]) {//从数组开始不断向后找，直到找到一个比基准数大的数，交换位置
begin++; //找不到就向后走
if (begin == key) { //如果前后两个索引相等，就要结束循环
break;
}
}
key = swap(arr, key, begin); //找到了，就交换数据，并返回基准数交换后的索引
i++;
System.out.println("第" + i + "次结果为");
printArray(arr);
if (begin == end || begin > end) { //如果前后索引相等或者前面的比后面的大，都要结束循环
break;
}
}
return begin; //返回中间数的索引
}
private int swap(int[] arr, int key, int x) {
int temp = arr[x];
arr[x] = arr[key];
arr[key] = temp;
return x; //比较后，要返回基准数新的索引
}
private static void printArray(int[] arr) {
for (int j : arr) { // 遍历输出数组的值
System.out.print(j + " ");
}
System.out.println(); // 换行
}
}

复制代码

int[] arr = new int[20];
for(int i = 0;i<arr.length;i++){
Random rand = new Random();
arr[i] = rand.nextInt(100); //生成0-100的之间的整型随机数并赋值给arr[i]
}

复制代码

= rand.nextInt(100); //生成0-100的之间的整型随机数并赋值给arr
 }
如果数组的生成是上面的代码，就会很容易死循环。。

下面有个哥们解决了这个问题。

作者: clp 时间: 2013-5-26 20:20
楼主可否给出一个排不了的数组，我试了几个都是正确的，一时还真找不出来bug

初始化数组为：
1 3 5 7 9 2 4 6 897 78 13 27 12 11
第1次结果为
1 3 5 7 9 2 4 6 897 78 13 27 12 11
第2次结果为
1 3 5 7 9 2 4 6 897 78 13 27 12 11
第3次结果为
1 2 5 7 9 3 4 6 897 78 13 27 12 11
第4次结果为
1 2 3 7 9 5 4 6 897 78 13 27 12 11
第5次结果为
1 2 3 7 9 5 4 6 897 78 13 27 12 11
第6次结果为
1 2 3 7 9 5 4 6 897 78 13 27 12 11
第7次结果为
1 2 3 6 9 5 4 7 897 78 13 27 12 11
第8次结果为
1 2 3 6 7 5 4 9 897 78 13 27 12 11
第9次结果为
1 2 3 6 4 5 7 9 897 78 13 27 12 11
第10次结果为
1 2 3 6 4 5 7 9 897 78 13 27 12 11
第11次结果为
1 2 3 5 4 6 7 9 897 78 13 27 12 11
第12次结果为
1 2 3 5 4 6 7 9 897 78 13 27 12 11
第13次结果为
1 2 3 4 5 6 7 9 897 78 13 27 12 11
第14次结果为
1 2 3 4 5 6 7 9 897 78 13 27 12 11
第15次结果为
1 2 3 4 5 6 7 9 897 78 13 27 12 11
第16次结果为
1 2 3 4 5 6 7 9 897 78 13 27 12 11
第17次结果为
1 2 3 4 5 6 7 9 11 78 13 27 12 897
第18次结果为
1 2 3 4 5 6 7 9 11 78 13 27 12 897
第19次结果为
1 2 3 4 5 6 7 9 11 78 13 27 12 897
第20次结果为
1 2 3 4 5 6 7 9 11 78 13 27 12 897
第21次结果为
1 2 3 4 5 6 7 9 11 12 13 27 78 897
第22次结果为
1 2 3 4 5 6 7 9 11 12 13 27 78 897
第23次结果为
1 2 3 4 5 6 7 9 11 12 13 27 78 897
第24次结果为
1 2 3 4 5 6 7 9 11 12 13 27 78 897
第25次结果为
1 2 3 4 5 6 7 9 11 12 13 27 78 897
第26次结果为
1 2 3 4 5 6 7 9 11 12 13 27 78 897
作者: 韩明海 时间: 2013-5-26 20:43
太复杂了，一点都不快，能设计出来这个复杂算法不得不赞一个{:soso_e179:}
作者: 尖卡斌引 时间: 2013-5-27 00:12
public class Test4 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = {23,4,56,12,567,34,21,9,56,3,12};
sop(arr);
kuaiPai(arr);
sop(arr);

}
public static void kuaiPai(int[] arr){
 qSort(arr,0,arr.length-1);

}
public static void qSort(int[] arr,int low,int high){
if(low<high){
int pin =part(arr,low,high);
qSort(arr,low,pin-1);
qSort(arr,pin+1,high);

}

}
public static int part(int[] arr,int low,int high){
int key = arr[low];
int pin =low ;
while(low<high){
while(low<high&&key<=arr[high])
high--;
arr[pin]=arr[high];
pin=high;
while(low<high&&key>=arr[low])
low++;
arr[pin]=arr[low];
pin=low;

}
arr[pin]=key;
return pin;
}
public static void sop(int[] arr){
System.out.print("[");
for(int i=0;i<arr.length;i++){
if(i==arr.length-1)
System.out.println(arr[i]+"]");
else
System.out.print(arr[i]+",");
}
}

}
直接上代码
作者: 神之梦 时间: 2013-5-27 00:55
一些特定的数组楼主给出look下先
作者: 张俊迪 时间: 2013-5-27 01:46
该你改的你看看不行我再给你改应该没问题
import java.util.Random;
public class Test1 {
 int i = 0; //定义一个整型的i记录排序的次数

 public static void main(String[] args) {
 Test1 T = new Test1();
//int[] arr={3,4,5,6,1,1,7};//下面getMiddle中的arr[end]>key会出现死循环，你的是arr[end]>arr[key]
 int[] arr = {49,38,65,97,78,13,27,1,2};
 // int[] arr = { 49, 38, 65, 97, 78, 13, 27, 12, 11 }; //实例化一个数组
 System.out.println("初始化数组为：");
 printArray(arr); //把数组打印出来
 T.Run(arr, 0, arr.length - 1); //开始排序
 }

 public void Run(int[] arr, int begin, int end) { //一个递归，不断的对数组进行排序
 if (begin < end) { //只有开始索引比结束索引小的时候才进行排序
/*你这中间值也用KEY太蒙人，是不是应该换个*/
 int key = getMiddle(arr, begin, end); //进行排序并返回中间值的位置
 Run(arr, begin, key - 1); //对中间的左边进行递归
 Run(arr, key + 1, end); //对中间的右边进行递归
 }
 }

 public int getMiddle(int[] arr, int frist, int last) {
 int begin = frist; //开始索引等于数组第一个下标
 int end = last; //结束索引等于数组长度减一
 //int key = frist; //基准数的索引等于数组的第一个索引
int key = arr[frist];
 while (begin < end) { //每当开始索引小于结束索引的时候都不断的排序

 //while (begin < end && arr[end]>arr[key]) { //从数组的结束索引开始不断向前找，直到找到一个比基准数小的数位置，然后进行交换
while (begin < end && arr[end]>=key) {//不加等号会出现死循环，例如一个数组中有相等的值
 end--; //找不到就向前走
//没必要出现这句
 /*if (end == key) { //如果结束索引等于开始索引了，那就要结束循环
 break;
 }*/
 }
 //swap(arr, key, end); //找到了，就交换数据，并返回基准数交换后的索引
 swap(arr,begin,end);//你上面的传值是啥意思，为什么要和标志位换呢，是不是应该像我这样，感觉你的快排的原理和我的不大一样

 /*
 i++; //每次交换都统计次数
 System.out.println("第" + i + "次结果为");
 printArray(arr); //输出这次交换后的数组*///到这不是本次的最终结果，也许你的结果和我的不是一个意思，判断一次结果是标志的值发生变化才算一次结果

 while (begin < end && arr[begin]<=key) {//从数组开始不断向后找，直到找到一个比基准数大的数，交换位置
 begin++; //找不到就向后走
 /* if (begin == key) { //如果前后两个索引相等，就要结束循环
 break;
 }*/
 }

 //swap(arr, key, begin); //找到了，就交换数据，并返回基准数交换后的索引
swap(arr, end, begin);
/*
 i++;
 System.out.println("第" + i + "次结果为");
 printArray(arr);*/

/*if (begin == end || begin > end) { //如果前后索引相等或者前面的比后面的大，都要结束循环
 break;
 }没必要*/

 }
i++;
 System.out.println("第" + i + "次结果为");
 printArray(arr);//输出一次结果

 return begin; //返回中间数的索引

 }

 private void swap(int[] arr, int key, int x) {
 int temp = arr[x];
 arr[x] = arr[key];
 arr[key] = temp;
 // return x; //比较后，要返回基准数新的索引
 }

 private static void printArray(int[] arr) {
 for (int j : arr) { // 遍历输出数组的值
 System.out.print(j + " ");
 }
 System.out.println(); // 换行
 }

}
撑不住了，看得有点晚睡了，不行你再给我huitie明天接着给你搞，不出意外应该没问题
作者: 殇_心。 时间: 2013-5-27 10:09
如果问题已解决，请及时修改分类，否则继续提问，谢谢合作！
作者: 、zhi 时间: 2013-5-27 12:41

张俊迪发表于 2013-5-27 01:46
该你改的你看看不行我再给你改应该没问题
import java.util.Random;
public class Test1 {

这组代码的话，我用的是随机生成20个数字，排了好久都没有排完，和我原来代码一样，特定的数组可以排，随机生成的数组很容易死循环：
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963568次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963569次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963570次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963571次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963572次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963573次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963574次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963575次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963576次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963577次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963578次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963579次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963580次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963581次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963582次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963583次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963584次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963585次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963586次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963587次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963588次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963589次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963590次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963591次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963592次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963593次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963594次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963595次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963596次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963597次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963598次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963599次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963600次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963601次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963602次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963603次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963604次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963605次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963606次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963607次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963608次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963609次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963610次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963611次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963612次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963613次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963614次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963615次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963616次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963617次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963618次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963619次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963620次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963621次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963622次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963623次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963624次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963625次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963626次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963627次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963628次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963629次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963630次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963631次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963632次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963633次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963634次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963635次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963636次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963637次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963638次结果为
作者: 张俊迪 时间: 2013-5-27 13:20

、zhi 发表于 2013-5-27 12:41
这组代码的话，我用的是随机生成20个数字，排了好久都没有排完，和我原来代码一样，特定的数组可以排，随 ...

我写的代码你好好看了吗，你把我的代码复制上，运行一下，是不是没问题，反正我的电脑上没问题，你知道发生死循环是为什么吗，因为你的数组中有相同的数，而你的排序中没有判断等号的时候，所以会出现死循环，你发生死循环是不是都会有相同的值，麻烦你好好看看我写的代码，还有，你的好好看看快排的原理
作者: ozt6719393 时间: 2013-5-27 13:33
我自己写过的快速排序的，试过了，没问题：
/**
 *
 * 快速排序的基本思想是：通过一趟排序将要排序的数据分成两部分，左边的所有数据都比右边所有数据都要小，
 * 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 */
public class Test2 {

public static void main(String[] args) {

int[] arr = {85,3,12,48,96,137,52};
// 打印排序前的数组
System.out.print("排序前：");
printArr(arr);
// 调用方法对数组进行排序
qickSort(arr,0,arr.length-1);
// 打印排序后的数组
System.out.print("排序后：");
printArr(arr);
}

//用于遍历数组并打印数组
public static void printArr(int[] arr) {
for(int a: arr){
System.out.print(a+" ");
}
System.out.println();
}

// 快速排序
public static void qickSort(int[] arr ,int left,int right){
int temp;
int i = left,j = right;
if(left<right){
temp = arr[left];
//下边这个循环完成了一趟排序，即将数组中小于temp的元素放在左边，大于temp的元素反正右边
while(i!=j){
// 从左往右扫描找到一个小于temp的元素
while(i<j && arr[j]>temp)
--j;
if(i<j){
// 找到后放在temp左边
arr[i] = arr[j];
// 把下次找的起点推后一位
++i;
}
// 从右往左扫描找到一个大于temp的元素
while(i<j && arr[i]<temp)
++i;
if(i<j){
// 找到后放在temp右边
arr[j] = arr[i];
// 把下次找的起点前移一位
--j;
}
}
// 将temp放在最终位置
arr[i] = temp;
//递归地对temp左边的元素进行排序
qickSort(arr,left,i-1);
//递归地对temp右边的元素进行排序
qickSort(arr,i+1,right);
}
}

}

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2