黑马程序员技术交流社区

标题: 有关快速排序的问题 [打印本页]
作者: 十字路口    时间: 2013-6-1 00:32
标题: 有关快速排序的问题
本帖最后由 十字路口 于 2013-6-1 10:13 编辑

public class Quicksort{
public static int partion(int values[],int left,int right){
  int i=left;
  int j=right;
  int temp;
  int key=values[left];
  while(i<j){
   while(values<=key){
    i++;
   }
   while(values[j]>=key){
    j--;
   }
   if(i<=j){
    temp=values;
    values=values[j];
    values[j]=temp;
    i++;
    j--;
   }
  }
  return i;
}
public static  void qsort(int values[],int left,int right){
  int temp=0;
  if(left<right){
   temp=partion(values, left, right);
   qsort(values, left, temp-1);
   qsort(values, temp+1, right);
  }
}
public static void main(String[] args) {
  int a[]={34,43,6,12,78,37,92,14};
  qsort(a, 0, a.length-1);
  for(int i=0;i<a.length;i++){
   System.out.print(a+"  ");
  }
}
}
为什么这是个死循环。。。 while(values<=key){
i++;
}
while(values[j]>=key){
j--;
}
把段代码改成
while(values<key){
i++;
}
while(values[j]>key){
j--;
}
结果又不正确为什么呢？
作者: 神之梦    时间: 2013-6-1 01:58
首先这里while(values<=key)可以写等于，但是还缺少一个判断，就是i<j，因为如果不加这个判断，角标肯定会出界，所以运行时会出现错误。
这里可以写成while(i<j&&values<=key)
还有  if(i<=j){
     temp=values;
     values=values[j];
     values[j]=temp;
     i++;
     j--;
    }
   这里不能这么写，比如只有三个数，你去代入下就知道肯定会排出错误结果了

我之前写的一段代码，你可以看一下：
  1. /*
  2. 需求：使用快速排序的方法对数组进行升序排列
  3. 思路：1、快速排序是先利用数组的一个元素为参照，也叫枢轴。从左右两边分别与其比较，这是可以定义角标变量，左角标变量向右移，右的向左右，知道左大于等于右时，完成第一轮排序比较。
  4.                 第一轮比较后将大于这个元素的数放到右边，小于这个元素的数放到左边
  5.           2、再对左右两边根据第一步的思想进行排序。如：把左边的的部分当作一个数组，再从中选一个元素做参照。以此反复。
  6. */
  7. class QuickSort
  8. {       
  9.         public static void quickSort(int[] arr ,int left,int right)
  10.         {
  11.                 int l=left,r=right,pivot=arr[l];//pivot定义枢轴

  13.                 while(l<r)//判断一轮是否进行完了
  14.                 {
  15.                         while(l<r && arr[r]>=pivot)//判断右边的数是否都大于pivot
  16.                                 r--;

  18.                         //如果小于pivot，就将小于的元素放到左边去
  19.                         if(l<r)
  20.                         {
  21.                                 arr[l]=arr[r];
  22.                                 l++;//l++是为了避免重复判断
  23.                         }

  25.                         while(l<r && arr[l]<=pivot)//判断左边的数是否都小于pivot
  26.                                 l++;

  28.                         //如果大于privot，就将大于的元素放到右边去
  29.                         if(l<r)
  30.                         {
  31.                                 arr[r]=arr[l];
  32.                                 r--;
  33.                         }       
  34.                 }

  36.                 arr[l]=pivot;//将作为参照的元素放到分割位置
  37.                        
  38.                 //当一轮比较完，l！=left，说明左边还有大于1个元素，那么继续排序
  39.                 if(l>left)
  40.                 {
  41.                         quickSort(arr,left,l-1);
  42.                 }

  44.                 //当一轮比较完，r！=right，说明右边边还有大于1个元素，那么继续排序
  45.                 if(r<right)
  46.                 {
  47.                         quickSort(arr,l+1,right);
  48.                 }
  49.         }


  52.         //遍历数组
  53.         public static void printArray(int[] arr)
  54.         {
  55.                 System.out.print("[");
  56.                 for(int x=0;x<arr.length-1;x++)
  57.                         System.out.print(arr[x]+",");
  58.                 System.out.println(arr[arr.length-1]+"]");
  59.         }
  60. }


  63. class Test
  64. {
  65.         public static void main(String[] args)
  66.         {
  67.                 int[] arr1={1,2};
  68.                 int[] arr2={34,43,6,12,78,37,92,14};
  69.                 int[] arr3={2,2,2,10,2,3,3,3,3,2,2,2};

  71.                 QuickSort.printArray(arr1);
  72.                 QuickSort.quickSort(arr1,0,arr1.length-1);
  73.                 QuickSort.printArray(arr1);

  75.                 QuickSort.printArray(arr2);
  76.                 QuickSort.quickSort(arr2,0,arr2.length-1);
  77.                 QuickSort.printArray(arr2);

  79.                 QuickSort.printArray(arr3);
  80.                 QuickSort.quickSort(arr3,0,arr3.length-1);
  81.                 QuickSort.printArray(arr3);

  83.         }
  84. }
复制代码
作者: liujkh123    时间: 2013-6-1 08:55
首先，楼主的代码从头到尾没有对第一个数组元素的操作，仔细分析一下34的位置永远在首位
我跟着程序的思路理了一个程序运行流程给楼主，至于这个问题怎么解决，代码重构了
首先：34,43,6,12,78,37,92,14
第一次排序 i =1, j = 6;交换i，j的位置得到34,92,6,12,78,37,43,14,；i++后i=2，j--后j=5，返回2
第二次排序为前一截(values, 0, 1)就是给34,92排序，这里面不会执行交换，但是因为34<92，i会自加两下，所以最后返回的是i=2;
然后就无限重复第二步、、

这个问题出现的关键在于楼主代码没有对用作标杆的元素换位置，快速排序的核心思路就是在每一轮排序后，标杆元素在中间，左边全比它小，右边全比它大。然后再对左右分别进行排序。
下面是一个比较简洁的快速排序代码，希望能帮到你
  1. /**
  2.      * 交换指定数组a的两个变量的值
  3.      * @param a 数组应用
  4.      * @param i 数组下标
  5.      * @param j 数组下标
  6.      */
  7.     public void swap(int a[], int i, int j) {
  8.       
  9.         if(i == j) return;

  11.         int tmp = a[i];

  13.         a[i] = a[j];

  15.         a[j] = tmp;

  17.     }

  19.     /**
  20.      *
  21.      * @param array 待排序数组
  22.      * @param low 数组下标下界
  23.      * @param high 数组下标上界
  24.      * @return pivot
  25.      */
  26.     public int partition(int array[], int low, int high) {
  27.         //当前位置为第一个元素所在位置
  28.         int p_pos = low;
  29.         //采用第一个元素为轴
  30.         int pivot = array[p_pos];
  31.         
  32.         for (int i = low + 1; i <= high; i++) {

  34.             if (array[i] < pivot) {            
  35.                
  36.                 p_pos++;

  38.                 swap(array, p_pos, i);

  40.             }

  42.         }

  44.         swap(array, low, p_pos);

  46.         return p_pos;

  48.     }
  49.     /**
  50.      * 快速排序实现
  51.      * @param array
  52.      * @param low
  53.      * @param high
  54.      */
  55.     public void quickSort(int array[], int low, int high) {

  57.         if (low < high) {

  59.             int pivot = partition(array, low, high);

  61.             quickSort(array, low, pivot - 1);

  63.             quickSort(array, pivot + 1, high);

  65.         }

  67.     }
复制代码
作者: 十字路口    时间: 2013-6-1 09:27
灰常感谢各位大虾们，看了你们的提示，学到了很多。问题解决了。。。。。。



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