快速排序算法比较

Question

我不明白为什么我的排序算法在有50000个数字的数组上失败了

const myquicksort2 = (sortedArray) => {

    const sort = (start, end) => {
        if (end - start <= 1) return;
        let pivot = sortedArray[end - 1];
        let pivotIndex = end - 1;

        for (let i = start; i < end; i++) {
            if (sortedArray[i] > pivot && i < pivotIndex) {
                let temp = sortedArray[i];
                sortedArray[i] = pivot;
                sortedArray[pivotIndex] = temp;
                pivot = temp;
            }
        }
        sort(start, pivotIndex);
        sort(pivotIndex + 1, end);
    };

    sort(0, sortedArray.length);

    return sortedArray;
};

我不会在排序时创建新数组和更改Pivot值，但第二个示例在50000上不会失败，并且在https://jsperf.com/sorting12389上的性能要好得多

function sort(arr) {
   if (arr.length > 1) {
     const medium = arr[0];
     const leftPart = [];
     const centerPart = [];
     const rightPart = [];

     arr.forEach((item) => {
       if (item < medium) leftPart.push(item);
       if (item > medium) rightPart.push(item);
       if (item === medium) centerPart.push(item);
     })

     return sort(leftPart).concat(centerPart).concat(sort(rightPart));
   } else {
     return arr;
   }
 }

Answer 1

这里有几个问题。

首先，您需要注意使用jsperf进行正确的测试。浏览器会做各种优化，如果你一遍又一遍地对相同的数组进行排序，很难知道你是否真的在测试排序算法。您可以考虑在每次循环测试中创建一个新的随机数组。

其次，你的就地排序没有一个好的分区方案。快速排序的美妙之处在于，它将数组分成对数缩小的块。你在这里不是真的在做快速排序。它更像是冒泡排序，因为您的end变量只是从数组长度计数到0，并且每次调用时都会遍历列表的0 - end。这构成了O(n^2)时间。另外，因为pivotIndex总是被定义为end - 1，所以这是一个完全浪费的递归：

sort(pivotIndex + 1, end)

要使就地快速排序起作用，您需要一个重置透视索引的分区方案，然后在start - pivot和pivot+1 - end上重新排序。

一种常见的分区方案是Hoare分区，您可以从数组的相反两端移动两个变量，当您在轴心的任一侧找到值时交换。这并不复杂，但很容易搞砸索引。

分区通常是作为一个单独的函数编写的，但为了使其与您的函数保持一致，我只对其进行了内联：

​

const myquicksort2 = (sortedArray) => {
  const sort = (start, end) => {    
      if (end <= start) return;
      let pivot = sortedArray[end];
      let left = start, right = end
     
      // Partion 
      while(left <= right){
        while (sortedArray[left] < pivot){ 
          left++ 
        }     
        while (sortedArray[right] > pivot){ 
          right-- 
        }
        if (left <= right) {
          [sortedArray[left], sortedArray[right]] = [sortedArray[right], sortedArray[left]]
          left++
          right--
        }
      }

      sort(start, right);
      sort(right + 1, end);
  };

  sort(0, sortedArray.length-1);

  return sortedArray;
};

console.log(myquicksort2([5, 7, 2, 1, 11, 10]))

​

当我在Node中运行时间测试时，它比生成数组的函数快得多。在你的jsperf中，它不是。然而，如果我在每个循环中创建一个新的数组，速度会更快，这表明我们在jsperf的工作方式中没有看到一些东西。这是一个edit of the jsperf

在我的笔记本电脑上，这个节点在大约20毫秒内对100,000个随机整数进行排序，它需要大约50毫秒的非就地函数。