使用第一个元素作为支点快速排序

Question

我通过选择第一个元素作为支点，实现了快速排序。它适用于一般的测试用例，但考虑一个例子，当数组被反向排序时，例如5 4 3 2 1.我知道它在哪里抛出运行时错误。但我无法正确解决它。第一个元素的实现是否正确？请提出修改建议。

public static void quicksort(int low,int high) 
    { 

    if(low<high) 
    { 
    int temp=0; 
    int pivot=a[low];      
    int large_index=low+1; 
    int small_index=high; 

    while(large_index<=small_index) 
    { 
     while(a[small_index]>pivot) 
     small_index--; 

     while(a[large_index]<pivot) 
     large_index++; 

     if(large_index<=small_index) 
     { 
     temp = a[large_index]; 
     a[large_index]= a[small_index]; 
     a[small_index]= temp; 
     large_index++; 
     small_index--; 
     } 
    } 

    temp = a[small_index]; 
    a[small_index]= a[low]; 
    a[low]= temp; 


    quicksort(low,small_index-1); 
    quicksort(small_index+1,high); 
    } 

    } 

Answer 1

下循环继续上面high，当large_index已经开始在枢轴上方，它发生枢轴小于位于后它的每一个元素较大：

while(a[large_index]<pivot) 
large_index++; 

可能有其他错误，当然。

Answer 2

有多个缺陷：

a）所述环的外侧不必要的交换

温度= A [small_index]; a [small_index] = a [低]; a [低] =临时;

b）large_index的错误初始化。

c）在不检查 small_index和large_index的值的情况下调用递归函数。

我已经纠正他们，

现在的功能将类似于：

if (low < high) { 
      int temp = 0; 
      int pivot = a[low]; 
      int large_index = low; 
      int small_index = high; 

      while (large_index <= small_index) { 
       while (a[small_index] > pivot) 
        small_index--; 

       while (a[large_index] < pivot) 
        large_index++; 

       if (large_index <= small_index) { 
        temp = a[large_index]; 
        a[large_index] = a[small_index]; 
        a[small_index] = temp; 
        large_index++; 
        small_index--; 
       } 
      } 

      if(low < small_index) 
      { 
       quicksort(low, small_index); 
      } 
      if(large_index < high) 
      { 
       quicksort(large_index, high); 
      } 
     } 

现在，看在你的代码中的变量：（代码将在最后一次迭代失败任何给定的输入，除非输入不排序）

考虑输入2,1

1st iteration: 

pivot = 2 
large_index = 1; 
small_index = 1; 


while1: 
1<=1 -> true 
    while2: 1>2 false. 
    while3: 1<2 true. -> large_index++ 
       2nd time in while loop large_index =2 which is > the size of a. 

产生IndexArrayOutOfBounds。

这说明你的初始化large_index是错误的。

它应该是：large_index = low;而不是低+ 1;

希望这会有所帮助。

Answer 3

经过一番尝试后，我能够使Quicksort功能，现在它工作正常。 @BatScream我仍然在我的代码中使用small_index = low + 1。所以这不是我猜的错误。原始的快速排序算法遵循这种机制。请参考Princeton Professor Robert Sedgewick在QuickSort上的演讲。请注意，如果编辑过的快速排序算法存在缺陷。

public static void quicksort(int low,int high) 
{ 

    if(low<high) 
    { 
    int temp=0; 
    int pivot=a[low];      
    int large_index=low+1; 
    int small_index=high; 

    while(large_index<small_index) 
    { 

    while(a[large_index]<pivot) { 
    if(large_index==high) 
    break; 
    large_index++; 
    } 

    while(a[small_index]>pivot) 
    { 
    if(small_index==low) 
    break; 
    small_index--; 
    } 

    if(large_index<small_index) { 
    temp = a[large_index]; 
    a[large_index]= a[small_index]; 
    a[small_index]= temp; 
    large_index++; 
    small_index--; 
    } 
    } 

    if(a[small_index]<pivot) {        
     temp = a[small_index]; 
     a[small_index]= a[low]; 
     a[low]= temp; 
    } 

    if(low<small_index)         //Recursively sort the left half. 
    { 
    quicksort(low,small_index-1); 
    } 

    if(high>small_index)         //Recursively sort the right half. 
    { 
    quicksort(small_index+1,high); 
    } 
    } 

    }