我的 Quicksort 实现在降序数字情况下失败

Question

我正在编写快速排序代码。

代码如下，

function quickSort(inputArray){
  var pivotIndex = undefined;
  var low_Index = undefined;
  var high_Index = undefined;

  pivotIndex = inputArray.length - 1;
  low_Index = 0;
  high_Index = (inputArray.length > 2) ? (inputArray.length - 2) : 0;

  partition(pivotIndex,low_Index,high_Index);

  function partition(pivot_Index,low_Index,high_Index){
    var hasSwapped = false
    var temp = 0;

    for(var low = low_Index; low < pivot_Index; low++){

        if(inputArray[low] > inputArray[pivot_Index]){
            hasSwapped = true;
            temp = inputArray[low];
            inputArray[low] = inputArray[high_Index];
            inputArray[high_Index] = inputArray[pivot_Index];
            inputArray[pivot_Index] = temp;
            pivot_Index = high_Index;
            high_Index--;
            low--;              
        }
    }


    //console.log("PIVOT_INDEX "+inputArray[pivot_Index]);

    if(pivot_Index < inputArray.length - 1){

        if((pivot_Index + 1) < inputArray.length - 1){
            partition(inputArray.length - 1,(pivot_Index + 1),inputArray.length - 2);   
        }

        if((pivot_Index - 2) >= 1){
            partition((pivot_Index - 1),0,(pivot_Index - 2));   
        }


      }


  }



  return inputArray;

}

以上代码针对以下输入运行

console.log(quickSort([3,7,8,5,2,1,9,5,4]));
console.log(quickSort([4,7,3,15,2,1]));
console.log(quickSort([4,7,3]));
console.log(quickSort([7,3]));

输出是

rahul@rahul:~/myPractise/Algo$ node sorting.js 
[ 1, 2, 3, 4, 5, 5, 7, 8, 9 ]
[ 1, 2, 3, 4, 7, 15 ]
[ 3, 4, 7 ]
[ 3, 7 ]

但是对于以下所有数字均按降序排列的输入失败

console.log(quickSort([15,12,10,7,4,1]));

rahul@rahul:~/myPractise/Algo$ node sorting.js 
[ 1, 12, 10, 7, 4, 15 ]
rahul@rahul:~/myPractise/Algo$

我认为原因是我的枢轴索引指向 15 是最大数字，因此不会被替换。

我如何更改代码以使上述输入的算法有效？

注意：我从维基百科中的图表中得到了快速排序的解释

大家好，

我通过添加代码解决了上面的问题

    if(inputArray[low_Index] > inputArray[high_Index]){
        temp = inputArray[low_Index];
        inputArray[low_Index] = inputArray[high_Index];
        inputArray[high_Index] = temp;      
        pivot_Index = high_Index;           
    }

就在 for 循环之下和函数内部 if 条件之上 "partition"

所以现在我的代码看起来像这样

function quickSort(inputArray){
    var pivotIndex = undefined;
    var low_Index = undefined;
    var high_Index = undefined;

    pivotIndex = inputArray.length - 1;
    low_Index = 0;
    high_Index = (inputArray.length > 2) ? (inputArray.length - 2) : 0;

    partition(pivotIndex,low_Index,high_Index);

    function partition(pivot_Index,low_Index,high_Index){       
       var temp = 0;

       console.log("\nPivot Number : "+inputArray[pivot_Index]);
       console.log("input Array : "+inputArray);
       console.log("partitioned array : "+inputArray.slice(low_Index,pivot_Index+1));

       for(var low = low_Index; low < pivot_Index; low++){

        if(inputArray[low] > inputArray[pivot_Index]){

            temp = inputArray[low];
            inputArray[low] = inputArray[high_Index];
            inputArray[high_Index] = inputArray[pivot_Index];
            inputArray[pivot_Index] = temp;
            pivot_Index = high_Index;
            high_Index--;
            low--;              
        }
      }

      // added if condition, which solves my problem
      if(inputArray[low_Index] > inputArray[high_Index]){
        temp = inputArray[low_Index];
        inputArray[low_Index] = inputArray[high_Index];
        inputArray[high_Index] = temp;      
        pivot_Index = high_Index;           
      }




      if(pivot_Index < inputArray.length - 1){

        if((pivot_Index + 1) < inputArray.length - 1){
            partition(inputArray.length - 1,(pivot_Index + 1),inputArray.length - 2);   
        }

        if((pivot_Index - 2) >= 1){
            partition((pivot_Index - 1),0,(pivot_Index - 2));   
        }


      }


    }//partition



    return inputArray;

}

在运行之后输入上面的代码

console.log(quickSort([15,12,10,7,4,1]));

输出结果如下，

rahul@rahul:~/myPractise/Algo$ node sorting.js 

Pivot Number : 1

input Array : 15,12,10,7,4,1
partitioned array : 15,12,10,7,4,1

Pivot Number : 15
input Array : 1,12,10,7,4,15
partitioned array : 12,10,7,4,15

Pivot Number : 7
input Array : 1,4,10,7,12,15
partitioned array : 1,4,10,7

Pivot Number : 15
input Array : 1,4,7,10,12,15
partitioned array : 10,12,15
[ 1, 4, 7, 10, 12, 15 ]
rahul@rahul:~/myPractise/Algo$

代码运行正常。

Answer 1

当主元是数组的最大数时，您的 partition 函数不起作用（[2,1,3] 不会被排序...）。事实上，这种情况永远不会成立：

if(inputArray[low] > inputArray[pivot_Index]){

因此 pivot_Index 永远不会改变，所以最后一个条件永远为假：

if(pivot_Index < inputArray.length - 1){

除了你用错误的参数递归调用 partition 函数：

partition(inputArray.length - 1,(pivot_Index + 1),inputArray.length - 2);

事实上，你总是取整个数组的最后一个元素 (inputArray.length - 2) 而不是子数组。所以你最终可能会得到这样的结果：

                  [A,B,C,D,E,F]
        [A,B,C,D]              [E,F]
    [A,B]    **[C,D,E,F]** WRONG

您应该简化代码。从这样的事情开始：

function quicksort(array, lo, hi){
    if (lo < hi){ 
        indicePivot  := partition(array, lo, hi) // partition your array [values < pivot ... , pivot, values > pivot ...]
        // Divide and conquer: recursively call quicksort on sub arrays [values < pivot] and [values > pivot]
        quicksort(array, lo, indicePivot – 1) 
        quicksort(array, indicePivot + 1, hi)
    }
}

你的分区函数：

function partition(array, lo, hi){
   indicePivot = hi;
   // do the magic to have [values < pivot ..., pivot, values > pivot]
   // ...
   return indicePivot;
}

我的 Quicksort 实现在降序数字情况下失败

My Quicksort implementation fails for descending numbers case

javascript

sorting

algorithm

quicksort