时间戳

首页 > 解决方案 > 快速排序算法比较

javascript - 快速排序算法比较

问题描述

不明白为什么我的排序算法落在了 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;
   }
 }

标签： javascriptquicksort

解决方案

这里有几个问题。

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

其次，您的就地排序没有良好的分区方案。快速排序的美妙之处在于它将数组拆分成对数收缩的块。您在这里并没有真正进行快速排序。它更像是冒泡排序，因为您的end变量只是从数组长度计数到零，并且每次调用都循环遍历0 - end列表。这需要 O(n^2) 时间。此外，由于pivotIndex总是定义为end - 1，这是一个完全浪费的递归：

sort(pivotIndex + 1, end)

要使就地快速排序起作用，您需要一个分区方案来重置枢轴的索引，然后再使用start - pivotand 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 的工作方式中我们没有看到某些东西。这是jsperf 的编辑

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

推荐阅读