黑马程序员技术交流社区

标题: 快速排序的代码，我的哪里错了 [打印本页]
作者: 孔德智    时间: 2012-9-13 09:13
标题: 快速排序的代码，我的哪里错了
本帖最后由 孔德智 于 2012-9-13 12:29 编辑

public class QuickSort
{
　　public static void main(String[] args)
　　{
　　 int [] arry={49,38, 65, 97, 76, 13, 27 };
　　  //程序还有问题.比如当数据为49,38, 65, 97, 76, 13, 27,12,11 的时候,第一次就把最小一位放到第一位,,而出现问题
  QuickSort.method2(arry);
  Arrays.sort(arry, 0, arry.length);
　　 for (int i = 0; i < arry.length; i++)
  {
　　   System.out.println("结果:"+arry);
　　 }
}
/**
　　* 快速排序
　　* @param arry
　　*/
　　public static void method2(int [] array)
{
　　 //1）设置两个变量I、J，排序开始的时候：I=0，J=N-1；
　　 int i=0;
　　 int j=array.length-1;//获取数组最后一位
　　 //2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；
　　 int k=array[0];//获取数组第一位
　　 int f=0;
　　 boolean check=false;
　　 int x=0;
　　 while(i != j)
  {
　　  //3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值A[J]，A[j]与A交换；
　　  while(array[j] > k)
   {
　　   j--;
　　  }
　　  int temp = k;
　　  k = array[j];
　　  array[j] = temp;
　　  //[49, 38, 65, 97, 76, 13, 27] //[27, 38, 65, 97, 76, 13, 49]//[27, 38, 49, 97, 76, 13, 65]
　　  //[27, 38, 49, 97, 76, 49, 65] //[27, 38, 13, 97, 76, 49, 65]//[27, 38, 13, 49, 76, 97, 65]
　　  //[27, 38, 13, 49, 76, 97, 65]
　　  //4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A[I]，A[j]与A交换；
   while (array < k)
   {
　　   i++;
　　  }
　　  int temp1= k;
　　  k = array;
　　  array = temp1;
　　  //[27, 38, 65, 97, 76, 13, 49] //[27, 38, 49, 97, 76, 13, 49] //[27, 38, 49, 97, 76, 13, 65]
　　  //[27, 38, 13, 97, 76, 49, 65] //[27, 38, 13, 49, 76, 49, 65] //[27, 38, 13, 49, 76, 97, 65]
　　  System.out.println(array+" "+array[j]);
　　  if(array==array[j])
   {
　　   x++;
　　   if(x>(array.length/2+1))
    {
　　    check=true;
　　   }
　　  }
　　  if(i==j||check)
   {
　　   k=array[0];//获取数组第一位
　　   if(i==j&&i==0)
    {
　　    k=array[1];
　　   }
　　   i=0;
　　   j=array.length-1;//获取数组最后一位
　　   check=false;
　　   x=0;
　　   if(f>(array.length/2+1))
    {
　　    k=array[j];
　　   }
　　   if(f==array.length)
    {
　　    break;
　　   }
　　   f++;
   }//[27, 38, 13, 49, 76, 97, 65] //[13, 27, 38, 49, 76, 97, 65]
  }
　　}
}

作者: 杨卫腾    时间: 2012-9-13 10:16
  1.         public static void superSelectSort(int[] arr)
  2.         {
  3.                 for(int x=0; x<arr.length-1; x++)
  4.                 {
  5.                         int value = arr[x]; //记录住一个元素
  6.                         int index = x;      //记录住元素角标
  7.                         for(int y=x+1; y<arr.length; y++)
  8.                         {
  9.                                 if(value>arr[y]) //在和遍历的元素进行比较
  10.                                 {       
  11.                                         //将较小的值赋给value
  12.                                         value = arr[y];
  13.                                        
  14.                                         //较小值的角标给index
  15.                                         index = y;      
  16.                                 }
  17.                         }
  18.                         //临时变量被覆盖后，说明被覆盖的元素才是最小的，交换元素。
  19.                         if(index!=x)         
  20.                                 swap(arr,x,index);
  21.                 }
  22.         }

  24.         public static void swap(int[] arr, int a,int b)
  25.         {
  26.                 int temp;
  27.                 temp = arr[a];
  28.                 arr[a] = arr[b];
  29.                 arr[b] = temp;
  30.         }
复制代码
看看这个排序方法。怎么样？
作者: 黑马-王言龙    时间: 2012-9-13 10:23
本帖最后由 黑马-王言龙 于 2012-9-13 10:25 编辑

建议：1、把格式排好  （论坛里有格式化代码的工具）
2、标识符起的有意义点

再写程序
作者: 马睿    时间: 2012-9-13 11:05
本帖最后由 马睿 于 2012-9-13 11:15 编辑

……LZ问的是快速排序，不是冒泡排序…这道应该是基础测试题经常会问到的之一…我不能贴给你源代码，不过可以告诉你，你哪里错了，以及思路

首先先讲一下什么是快速排序：

所谓快速排序，是分治算法的一种，而且使用到了递归！什么是分治算法呢?

简单的说，就是把一件事情划分为两个部分，比你要做个菜，番茄炒蛋，你可以分开操作把番茄先下锅炒，然后把蛋下去炒一下，最后把两个归并到一起炒（虽然实际做菜未必会这样做…这里只是个处理分治的例子）

所谓快速排序算法，其主要思路是：
1.对一组数字中，选取一个轴心数字，作为轴

2.从轴左边开始找比轴大的数字（索引 i 的到轴k的索引index到轴就结束），放到轴左边（也就是和轴交换位置，但是轴依然还是原来那个数字），只交换1次，然后执行步骤3

3.然后从轴的右边开始找(注意此时由于轴交换过了，轴在数组里的数组索引号也会变哦！索引 j 到key的新的index结束查找)，如果比轴小，则交换数据，只交换1次

4.重复步骤2,3，直到左边索引 i 和右边索引 j 交叉了（也就是 i >= j时结束运算）


举个例子
34 87 29 37，取轴为34
执行步骤2，找比34(轴k的index=0),大的，由于一开始是从左边找（i 的索引直接碰到了index，结束查找），直接进入步骤3（注意此时索引 i = 0）
执行步骤3，从右边找，找比34大的，29比34小，所以交换他们，于是数组变顺序成了29 89 （34） 37

判断while(i < j)成立则重复步骤2与3，注意此时轴 = 34，轴索引index = 1,索引 j = 1(因为刚才替换的位置是29的位置，索引为2，替换完后 j- -了)
步骤2，从i = 0开始从左向右边→ 找比34大的，发现89比 34大，交换       29  （34） 89 37   （注意交换完后 i = 2，因为是和索引1位置的89替换了，替换完后 i ++)
步骤3,从右边向左找←，找比34小的，此时 j =1 而34的index = 1 碰到了轴，直接结束查找

判断while(i < j)成立则重复步骤2与3,此时 i = 2 而 j =1 显然不成立
结束本次“小”排序

此时你发现序列为 29 (34) 89 37
而当你完全排完是 29 (34) 37 89
你是否发现了，轴34在最终结果的正确的位置了呢？
是的，所谓快速排序，就是每次选取一个轴，将轴经过小排序，把轴放到最终结果的正确位置（也就是将整个排序，分成若干次小排序，每次将一个数字直接放到最终位置）

（附送个选轴的方法）
选轴一般第一次从最左边那个选一个，然后小排序完成后，讲本次的 i j（左，右搜索）索引还原到搜索前的索引序号，然后判断当前轴的index是在 i与 j的哪边
如果 i < index则将 i 作为新的 左边索引 i 而将 index-1 作为新的右边索引 j （再次选择最左边的作为轴）
如果 j > index则将 index-1 作为新的 左边索引 i 而将  j作为新的右边索引 j （仍然再次选择最左边的作为轴）
  1.         
  2.         /*还原左右索引序号，left_hold和rigth_hold为排序前传入的索引(也就是上文说所的i与j)*/
  3.         left = left_hold;
  4.         right = right_hold;
  5.         if ( left < keyIndex )
  6.         {
  7.             for ( int i = 0; i <= index; i++)
  8.             {
  9.                 System.out.print(arrayList.get(i) + " ");
  10.             }
  11.             System.out.print("\n");
  12.             quickSort(left, keyIndex - 1);
  13.         }
  14.         if ( right > keyIndex )
  15.         {
  16.             for ( int i = 0; i <= index; i++)
  17.             {
  18.                 System.out.print(arrayList.get(i) + " ");
  19.             }
  20.             System.out.print("\n");
  21.             quickSort(keyIndex + 1, right);
  22.         }
复制代码
public class QuickSort
{
　　public static void main(String[] args)
　　{
　　 int [] arry={49,38, 65, 97, 76, 13, 27 };
　　  //程序还有问题.比如当数据为49,38, 65, 97, 76, 13, 27,12,11 的时候,第一次就把最小一位放到第一位,,而出现问题
  QuickSort.method2(arry);
  Arrays.sort(arry, 0, arry.length);
　　 for (int i = 0; i < arry.length; i++)
  {
　　   System.out.println("结果:"+arry);
　　 }
}
/**
　　* 快速排序
　　* @param arry
　　*/
　　public static void method2(int [] array)
{
　　 //1）设置两个变量I、J，排序开始的时候：I=0，J=N-1；
　　 int i=0;
　　 int j=array.length-1;//获取数组最后一位
　　 //2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；
　　 int k=array[0];//获取数组第一位
　　 int f=0;
　　 boolean check=false;
　　 int x=0;
　　 while(i != j)/*应该判 i 与 j是否交叉*/
  {
　　  //3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值A[J]，A[j]与A交换；
　　  while(array[j] > k) /* (应该判断加入判断索引j是否超过了k的index)*/
   {
　　   j--;
　　  }
　　  int temp = k;
　　  k = array[j];
　　  array[j] = temp;/*交换完后,k的index位置没变，并且把轴k数据给换了？，这个是错的，应该不是换数据，是换位置，轴的数据不变的*/
　　  //[49, 38, 65, 97, 76, 13, 27] //[27, 38, 65, 97, 76, 13, 49]//[27, 38, 49, 97, 76, 13, 65]
　　  //[27, 38, 49, 97, 76, 49, 65] //[27, 38, 13, 97, 76, 49, 65]//[27, 38, 13, 49, 76, 97, 65]
　　  //[27, 38, 13, 49, 76, 97, 65]
　　  //4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A[I]，A[j]与A交换；
   while (array < k)
   {
　　   i++;
　　  }
　　  int temp1= k;
　　  k = array;
　　  array = temp1;
　　  //[27, 38, 65, 97, 76, 13, 49] //[27, 38, 49, 97, 76, 13, 49] //[27, 38, 49, 97, 76, 13, 65]
　　  //[27, 38, 13, 97, 76, 49, 65] //[27, 38, 13, 49, 76, 49, 65] //[27, 38, 13, 49, 76, 97, 65]
　　  System.out.println(array+" "+array[j]);
　　  if(array==array[j])
   {
　　   x++;
　　   if(x>(array.length/2+1))
    {
　　    check=true;
　　   }
　　  }
　　  if(i==j||check)
   {
　　   k=array[0];//获取数组第一位
　　   if(i==j&&i==0)
    {
　　    k=array[1];
　　   }
　　   i=0;
　　   j=array.length-1;//获取数组最后一位
　　   check=false;
　　   x=0;
　　   if(f>(array.length/2+1))
    {
　　    k=array[j];
　　   }
　　   if(f==array.length)
    {
　　    break;
　　   }
　　   f++;
   }//[27, 38, 13, 49, 76, 97, 65] //[13, 27, 38, 49, 76, 97, 65]
  }
　　}
}


附送一个正常运算每次选轴和小排序结果
please input data split by space:
348 237 248 297 234 934 237 578 372 478 237
轴：348
237 237 248 297 234 237 348 578 372 478 934
轴：237
234 237 237 297 248 237 348 578 372 478 934
轴：234
234 237 237 297 248 237 348 578 372 478 934
轴：237
234 237 237 297 248 237 348 578 372 478 934
轴：297
234 237 237 237 248 297 348 578 372 478 934
轴：237
234 237 237 237 248 297 348 578 372 478 934
轴：248
234 237 237 237 248 297 348 578 372 478 934
轴：578
234 237 237 237 248 297 348 478 372 578 934
轴：478
234 237 237 237 248 297 348 372 478 578 934
轴：372
234 237 237 237 248 297 348 372 478 578 934
轴：934
234 237 237 237 248 297 348 372 478 578 934
作者: 王宝龙    时间: 2012-9-13 12:52
  1. public static void Sort(int[] a,int low,int high)
  2.         {
  3.                 int i = low;
  4.                 int j = high;
  5.                 int temp=a[low];//取第一个元素为标准数据元素
  6.                
  7.                 while(i<j)
  8.                 {
  9.                         while(i<j&&temp<=a[j])//在数组右端扫描
  10.                                 j--;
  11.                         if(i<j)
  12.                         {
  13.                                 a[i]=a[j];
  14.                                 i++;
  15.                         }
  16.                         while(i<j&&a[i]<temp)//在数组左端扫描
  17.                                 i++;
  18.                         if(i<j)
  19.                         {
  20.                                 a[j]=a[i];
  21.                                 j--;
  22.                         }
  23.                        
  24.                 }
  25.                 a[i]=temp;
  26.                
  27.                 if(low<i)Sort(a,low,i-1);
  28.                 if(i<high)Sort(a,j+1,high);
  29.         }
复制代码
看看这个怎么样！



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