如何优化快速排序

  • Z时代
  • 2024-01-10
  • 分类：问答

我正在尝试制定一种有效的quicksort算法。它可以正常工作，但是当元素数量巨大且数组的某些部分已预先排序时，运行时间会很长。我在上查找了Wikipedia文章quicksort，并发现以下内容：

为了确保最多使用O（log N）空间，请先递归到数组的较小部分，然后使用tail调用递归到另一个数组。

对于这样的小数组（即，其长度小于通过实验确定的阈值t），请使用具有较小常数因子并因此在小数组上更快的插入排序。这可以通过不对此类数组进行排序并在末尾运行单个插入排序遍历来实现，因为插入排序可有效处理几乎排序的数组。识别每个小片段时，单独的插入排序会增加启动和停止许多小排序的开销，但避免了浪费精力跨多个片段边界比较键，由于快速排序过程的工作，这些键是有序的。它还可以提高缓存的使用率。

我目前正在为这两个分区递归。任何想法如何实施第一个技巧？什么是

？其次，如何实现insertion-

sort快速排序？它会始终提高效率，还是仅在对数组的某些部分进行预排序时才提高效率？如果是第二种情况，那么我当然不知道何时会发生。那么我insertion-

sort什么时候应该包括？

回答：

在“快速排序”中，您选择了一个随机的轴心，该轴心将数组定界为两个半数，大多数情况下可能会更小一些，

例如数组大小100，枢轴将数组定界为40/60，其中40是较小的大小。

假设您确定阈值大小以使用插入排序为10，则需要继续通过数据透视表递归拆分数组，每当一半的其中之一变得小于或等于10时，就可以使用行为类似于小尺寸阵列上的O（n）。

请注意，如果将数组反向排序（最坏的情况），则插入排序将表现不佳。

关于递归方面，您只需要修改快速排序递归的终止条件->数组大小<= 10停止递归，并使用插入排序对所有数组（在此递归步骤中要小得多）进行排序。

通过尾递归，它们的意思是在前半部分完成您需要的所有操作，然后将较小的一半插入插入排序作为最后一个方法，该方法用于节省空间。

  Quick-sort()
      choose a pivot
      move the smaller elements from left
      move the bigger elements from right
      quick-sort on the bigger half of the array
      if half is less then X
         only then do an insertion sort on the other half <- this is a tail recursion insertion sort 
      else
         quick sort on this half also

据我所知，第二个优化建议不要对每个递归步骤都使用插入排序，但要记住对其进行约束的索引，然后在一批中调用插入排序以将所有切片中的项目连接在一起，这将确保提高缓存的使用率，但实施起来略有困难，

以上是 如何优化快速排序 的全部内容， 来源链接： utcz.com/qa/408311.html

回到顶部