快排算法比较

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;
};

我在排序时没有创建新数组和更改主元值，但是第二个示例在 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 进行正确测试。浏览器会进行各种优化，如果您一遍又一遍地对同一个数组进行排序，则很难知道您是否真的在测试您的排序算法。您可以考虑在每次循环测试中创建一个新的随机数组。

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

sort(pivotIndex + 1, end)

要让 in-place 快速排序工作，您需要一个分区方案来重置数据透视表的索引，然后在 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

在我的带节点的笔记本电脑上，这种排序 100,000 个随机整数大约需要 20 毫秒，non-inplace 函数需要大约 50 毫秒。

快排算法比较

Quicksort algorithm compare

javascript

quicksort