使用快速排序仅以一种方法对整数向量进行排序（没有 medianof3 或分区方法，如经典实现）

Question

不确定我做错了什么。我收到一个空指针异常。我试过调整一些东西，我也有一个可以编译的版本，但似乎对向量的前半部分进行了排序，然后它将空值分配给一半的索引，因此我认为我的代码存在根本性的错误.

如标题所述，我尝试仅用一种方法来完成此操作。 Middle 简单定义为中值元素，(left+right)/2。我正在尝试通过 for 循环而不是单独的分区方法进行分区。

我参考了：Whosebug with Quicksort Java implementation

主要是 raymi 接受的响应（因此 //ei=right，在我的代码中）

我不确定我在做什么不同......是他的代码不正确，还是我？

这是我的代码：

 public static void quickSort(Vector v, int left, int right) {
     //ei = right
     //si == left

     if(left == right){
     return;} 
     //base case -- no more recursion!!
     else{
         Comparable pivot = (Comparable) v.elementAt((left+right)/2);
         int i;
         i = left + 1;  

         //partition the array
         for(int j = left +1; j<= right; j++){
             if(pivot.compareTo(v.elementAt(j)) > 0){ 
                 swap(v, left, j);
                 i++;
             }//end if
        }//close for loop
         //place pivot in the right position
         //may be incorrect(?)
         v.replace(left, v.elementAt(i-1));
         v.replace(i-1, v.elementAt((Integer) pivot));

         //recursive call on both sides -- may be wrong(?)
         quickSort(v, left, i-2);
         quickSort(v, i, right);
     }
}//end quicksort

和我的交换替换代码，它在其他方法中工作正常：

public void replace(int indexGiven, Object element){
    if(indexGiven<0 || indexGiven>= size)
        return false;

    data[indexGiven] = element;
    return true;
}

当我运行代码时，我得到一个空指针异常。我玩过交换“> 到 <”之类的东西，但充其量我得到了编译代码并将空值分配给向量的一半。我认为我的代码有一些明显的错误，但我就是看不到它。

Answer 1

问题之前包含与霍尔分区方案类似的代码，现在已删除。它应该开始

    for(i = low-1, j = high+1 ; ;)

因为第一个 while 预递增 i，第二个 while 预递减 j。枢轴值可以来自数组中的任何值（例如枢轴 = a[(low + high)/2]），但实际使用的枢轴索引将基于 j，递归调用将为

    quicksort(a, low, j);
    quicksort(a, j+1, high);

旁注 - 您可以使用中位数 3 对 a[low]、a[(low + high)/2]、a[high]（3 个 if / swap 语句）进行排序，然后使用 pivot = a [（低 + 高）/2].

由于示例 Hoare 分区代码已从问题中删除，我将在此处添加它：

void QuickSort(int a[], int lo, int hi)
{
    if (lo >= hi)
        return;
    int p = a[(lo + hi) / 2];   // set pivot, could use median of 3 here
    int i = lo-1;
    int j = hi+1;
    while (true)
    {
        while (a[++i] < p) ;    // increase i until a[i] >= pivot
        while (a[--j] > p) ;    // decrease j until a[j] <= pivot
        if (i >= j)             // break if indices meet or cross
            break;
        swap(a[i], a[j]);
    }
    QuickSort(a, lo, j);        // this part includes values <= pivot
    QuickSort(a, j + 1, hi);    // this part includes values  > pivot
}

Hoare type quicksort, p is pivot

          p              quicksort(a, 0, 7)
07 04 05 03 06 00 01 02
02                   07  swap
   01             04     swap
      00       05        swap
    p                    quicksort(a, 0, 3)
02 01 00 03
00    02                 swap
 p                       quicksort(a, 0, 1)
00 01   
       p                 quicksort(a, 2, 3)
      02 03
                p        quicksort(a, 4, 7)
            06 05 04 07
            04    06     swap
             p           quicksort(a, 4, 5)
            04 05
                   p     quicksort(a, 6, 7)
                  06 07

使用快速排序仅以一种方法对整数向量进行排序（没有 medianof3 或分区方法，如经典实现）

Using quickSort to sort an Integer Vector in only one method (without medianof3 or partition methods, like classical implementations)

java

sorting

vector

quicksort