关于快速排序的问题

Question

我按照快速排序的原理编了一个函数，可有错误，我自己检查不出来，请高手帮帮忙
static void QSort(int[] pDate,int left,int right)
{
int i,j;
int middle,temp;
i = left;
j =  right;
middle = pDate[left];
while(true)
{
while((i++)<right&&pDate[i]>middle);
while((j--)>left&&pDate[j]<middle);
if(i>=j)
break;
temp = pDate[i];
pDate[i] = pDate[j];
pDate[j] = temp;
}
pDate[left] = pDate[j];
pDate[j] = middle;
if(left<j)
QSort(pDate,left,j);
if(right>j)
QSort(pDate,i,right);
}

Answer 1

写一个main测试程序，逐步发现问题。可以的话，再接着考虑内存和效率的问题。

Answer 2

package arithmetic;public class QuickSort2 {private static int[] theArray = null;public static void main(String[] args) {
   //要排序的数组
   theArray = new int[]{5, 4, 3, 8, 1, 6, 9};
  
   //显示未排序时的数组
   for (int i : theArray)
    System.out.print(i + " ");
   System.out.println();
  
   //快速排序
   quickSort();   //快速排序后的顺序
   for (int i : theArray)
    System.out.print(i + " ");
   System.out.println();
}/**
* 快速排序法
* 通过调用recQuickSort实现
*
*/
public static void quickSort() {
   recQuickSort(0, theArray.length - 1);
}/**
* 快速排序
* 每次循环选出一个数组元素作为枢轴,然后划分,划分后的两个数组,在选出枢轴,如此进行循环
* 当子数组中的元素小于3的时候(这里的3可以自己设置,并且这里是选的3,使用的原始的排序算法.这里是可以换成另外一个数,比如说10,然后
*    用插入排序算法排序),用原始的"手动"排序
* 递归
* @param left
* @param right
*/
private static void recQuickSort(int left, int right) {
  
   //数组大小
   int size = right - left + 1;
  
   //当数组长度小于3的时候,调用这个方法排序
   //也可换做插入排序
   if (size < 3) {
    manualSort(left, right, size);
   } else {
    //求枢轴
    //简单的快速排序会选择数组最右端的元素作为枢轴,但那样会在某些数组中排序时效率低下,如逆序
    int median = medianOf3(left, right);
    int partition = partitionIt(left, right, median);//划分
    recQuickSort(left, partition - 1);
    recQuickSort(partition + 1, right);
   }
}/**
* 划分算法
* 即选出一个枢轴,然后有两个指针(一左一右)相对遍历,将所有比枢轴大的数复制到右边,比枢轴小的元素复制到左边
* @param left
* @param right
* @param median
* @return leftPtr,此时它等于rightPtr + 1,是枢轴位置,这个位置左边的值都比它小,右边的值都比它大
*/
private static int partitionIt(int left, int right, int median) {
  
   int leftPtr = left - 1;
   int rightPtr = right;
  
   while (true) {
    //注意:因为这里选择枢轴是数组元素并在在数组中间,所以下面两个while循环没有越界检查
    //否则应该在两个while循环中加入适当的越界检查,如leftPtr < rightPtr
   
    //当定位到一个比枢轴大的元素时停下
    while (theArray[++leftPtr] < median)
     ;
    //当定位到一个比枢轴小的元素时停下
    while (theArray[--rightPtr] > median)
     ;
    //如果两个指针相遇或者交叉,则证明划分完毕
    if (leftPtr >= rightPtr)
     break;
    else//交换"位置不合适"的元素
     swap(leftPtr, rightPtr);
   }
   return leftPtr;
}/**
* 根据数组最左边,最右边和中间的三个数,求出中间值,作为枢轴
* @param left
* @param right
* @return
*/
private static int medianOf3(int left, int right) {
   int center = (left + right) / 2;
  
   //这样比较,对换位置后,这三个元素可形成一个有序的排列
   //返回中间的元素做枢轴,其余两个数组也不用再进行划分了
   if (theArray[left] > theArray[center])
    swap(left, center);
   if (theArray[left] > theArray[right])
    swap(left, right);
   if (theArray[center ] > theArray[right])
    swap(center, right);
   return theArray[center];
}/**
* 当数组的长度小于3的时候,用这个方法排序
* 这就类似于"手动"排序了,因为至多有3个数
* @param left
* @param right
* @param size
*/
private static void manualSort(int left, int right, int size) {
  
   if (size == 1)//1个数不用排也是有序的
    return;
   if (size == 2) {//两个数的排序
    if (theArray[left] > theArray[right])
     swap(left, right);
    return;
   } else {
    //第一个数和第二个数比
    if (theArray[left] > theArray[right - 1])
     swap(left, right - 1);
    //第一个和第三个数比
    if (theArray[left] > theArray[right])
     swap(left, right);
    //第二个和第三个数比,这样就能对3个数进行排序
    if (theArray[right - 1] > theArray[right])
     swap(right -1, right);
   }
}/**
* 交换两个数组元素的位置
* @param left
* @param right
*/
private static void swap(int left, int right) {
   int temp = theArray[left];
   theArray[left] = theArray[right];
   theArray[right] = temp;
}
}

Answer 3

public class QuickSort
{ /**
 *  JAVA排序算法实现代码-快速(Quick Sort)排序。
 */
public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 }; // 预设数据数组   public static void main(String args[]) {     System.out.print("排序前: ");
    for (int i = 0; i < a.length; i++)
      System.out.printf("%3s", a[i]);     System.out.println("");     int Index = a.length;     Quicksort(0, Index - 1, Index); // 快速排序     // 排序后结果
    System.out.print("排序后: ");
    for (int i = 0; i < a.length; i++)
      System.out.printf("%3s", a[i]);     System.out.println("");
  }   public static void Quicksort(int Left, int Right, int Index) {
    int i, j, k; // 循环计数变量
    int Pivot; // 枢纽变量
    int Temp; // 暂存变量     i = Left; // 设定左指针
    j = Right; // 设定右指针     Pivot = a[Left]; // 取最左边的元素     if (i < j) {
      do {
        while (a[i] <Pivot && i < Right) // 从左往右找比Pivot大的值
        {
          i++;
        }
        while (a[j] > Pivot && j > Left) // 从右往左找比Pivot小的值
        {
          j--;
        }         if (i < j) // 交换a[i]和a[j]
        {
          Temp = a[i];
          a[i] = a[j];
          a[j] = Temp;
        }
      } while (i < j);
      if (i > j) {
        Temp = a[Left]; // 交换a[Left]和a[j]
        a[Left] = a[j];
        a[j] = Temp;         // 打印目前排序结果         System.out.print("排序中: ");
        for (k = 0; k <= Index; k++) {
          System.out.printf("%3s", a[k]);
        }
        System.out.println("");
      }
      Quicksort(Left, j - 1, Index); // 排序左半边
      Quicksort(j + 1, Right, Index); // 排序右半边
    }
  }
}