QuickSortByRange, QuickSelectByRange, PartitionByRange

• 下载 qsbr.zip - 1.8 KB

引言

经典的 快速排序 (QuickSort) 和 快速选择 (QuickSelect) 算法的 worst-case 性能较差。如果一直选择不好的枢轴，例如每次只减少一个元素，那么最坏情况下的性能是二次方的：O(n²)。数组中的重复值对于快速排序来说是有问题的。

本文介绍了 QuickSortByRange, QuickSelectByRange 和 PartitionByRange 算法，它们通过从 PartitionByRange 算法返回一个枢轴范围来解决重复值的问题。当数组包含多个重复值时，这种方法很有效。

例如，如果数组的每个元素都包含相同的值，则 QuickSort 的时间复杂度为 O(n²)，而 QuickSortByRange 的时间复杂度为 O(n)。考虑到快速排序的平均情况性能为 O(n log n)，对于 QuickSortByRange 来说，全重复值的场景成为比平均情况更好的场景，相比之下，快速排序则面临比平均情况更差的场景。

背景

QuickSort 和 QuickSelect 都依赖于分区算法。分区算法查看数组范围内的一个初始（枢轴）值，然后重新组织该范围内的值，以便将所有小于或等于枢轴值的值放在枢轴的左侧，而将大于枢轴值的值移动到枢轴的右侧。该算法将根据需要移动枢轴元素，以满足这种准排序，然后它将返回枢轴元素的最终位置。

例如，让我们考虑一下在更大的数组中的以下范围

[ < , > , == , x , < , > , < , == ]

在这个例子中，'x' 标记枢轴值，'<' 表示小于枢轴值的值，'>' 表示大于枢轴值的值，'==' 表示等于枢轴值的值。

在通过 quickSort 分区算法进行单次传递后，这些元素将被重新组织为

[ < , == , < , < , == , x , > , > ]

PartitionByRange 算法更进一步。它进一步重新组织数组，以便将等于枢轴元素的元素放置在枢轴元素的紧左侧。小于枢轴值的值被放置在这个等值元素范围的左侧。

在通过 PartitionByRange 算法进行单次传递后，这些元素将被重新组织为

[ < , < , < , == , == , x , > , > ]

PartitionByRange 算法不是返回一个指示枢轴值最终位置的单一值，而是返回两个指示包含与枢轴值相同值的范围的位置值。这使得 QuickSortByRange 和 QuickSelectByRange 算法能够分别将下一次通过 PartitionByRange 的边界移动到比 QuickSort 和 QuickSelect 更右或更左的位置。

Using the Code

代码用 C# 编写，用于整数数组。将代码移植到另一种语言或值类型相当简单。

附带的文件是一个 HttpHandler，设计用于在具有 IIS 的机器的 localhost 上运行。它包括基准测试代码，用于复制本文结尾发布的结果。

PartitionByRange 代码的一个重要部分是用于存储等于枢轴值的值的存储位置的 Stack。将代码移植到另一种语言时，请确保使用 LIFO 结构来存储这些索引。可以使用数组代替堆栈，只要使用 LIFO 顺序即可。

PartitionByRange

public Tuple<int, int> partitionByRange(int[] a,int left,int right,int pivot) {

  int pivotValue = a[pivot];
  Stack<int> equalValuePositions = null;
  swap(a,pivot,right);
  for(int i=left;i<right;i++)
    if(a[i] <= pivotValue) {
      swap(a,left++,i);
      if(a[i] == pivotValue) {
        if(equalValuePositions == null) equalValuePositions = new Stack<int>();
        equalValuePositions.Push(i);
      }
    }
  swap(a,left,right);
  var rightPivotIndex = left;
  if(equalValuePositions != null) foreach(int i in equalValuePositions) swap(a,--left,i);
  return new Tuple<int, int>(left,rightPivotIndex);

}

public void swap(int[] a,int i,int j){ if(i!=j){ int k=a[i]; a[i]=a[j]; a[j]=k; } }

QuickSortByRange

public void quickSortByRange(int[] a) {

  qSortByRange(a,0,a.Length - 1,new Random());

}

public void qSortByRange(int[] a,int left,int right,Random r) {

  if(left < right) {
    int pivot = left + r.Next(right - left + 1);
    Tuple<int, int> pivotRange = partitionByRange(a,left,right,pivot);
    qSortByRange(a,left,pivotRange.Item1 - 1,r);
    qSortByRange(a,pivotRange.Item2 + 1,right,r);
  }

}

QuickSelectByRange

public int quickSelectByRange(int[] a,int n) {

  return qSelectByRange(a,0,a.Length - 1,n,new Random());

}

public int qSelectByRange(int[] a,int left,int right,int n,Random r) {

  if(left == right) return a[left];

  int pivot = n;

  while(true) {

    Tuple<int, int> pivotRange = partitionByRange(a,left,right,pivot);
    if(n >= pivotRange.Item1 && n <= pivotRange.Item2) return a[n];
    if(n < pivotRange.Item1)
      right = pivotRange.Item1 - 1;
    else
      left = pivotRange.Item2 + 1;
    pivot = left + r.Next(right - left + 1);

  }

}

开销

PartitionByRange 算法需要一个 Stack（或类似的 LIFO 结构），额外的比较，并且它返回一个包含两个整数的元组而不是一个整数。

这些开销需求导致性能下降，直到数组至少包含几个重复项后才会被克服。

性能

• 在没有重复条目的数组中，QuickSort 算法比 QuickSortByRange 算法快约 8%。
• 在只有几个重复条目的数组中，QuickSort 算法比 QuickSortByRange 算法快约 9%。
• 在有几个重复项的数组中，QuickSortByRange 算法比 QuickSort 算法快约 14%。
• 在有相当多重复项的数组中，QuickSortByRange 算法比 QuickSort 算法快约 76%。
• 在有很多重复项的数组中，QuickSortByRange 算法比 QuickSort 算法快约 98%。
• 在所有重复项的数组中，QuickSortByRange 算法比 QuickSort 算法快约 99.9%。

历史

在本文的原始版本中，我错误地声明 QuickSortByRange 在每个元素都包含相同值的数组上提供 O(1) 的性能。