Mic*_*ael 1 sorting algorithm partitioning quicksort
Lomuto分区是quicksort中使用的简单分区算法.Lomuto算法对子阵列进行分区,A[left] ... A[right]并假定A[left]它是一个枢轴.如何A[left] ... A[right]使用给定pivot P(与之不同A[left])将此算法修改为分区？
Lomuto的分区算法取决于枢轴是被分区的子阵列的最左边元素.它也可以修改为使用枢轴最右边的元素; 例如,请参阅CLRS的第7章.
使用枢轴的任意值(比如不在子阵列中的某些东西)会在快速排序实现中搞砸,因为无法保证您的分区使问题变得更小.假设你有一个零作为你旋转的值,但所有N个数组条目都是正数.然后你的分区将给出零长度的元素数组<= 0和一个长度为N的数组,其中包含元素> = 0(这些都是它们).在这种情况下,你会尝试使用quicksort进行无限循环.如果您尝试使用Lomuto分区的修改形式查找数组的中位数,则相同.分区主要取决于从数组中选择要转动的元素.你基本上失去了一个后置条件,一个元素(枢轴)将在分区之后固定到位,Lomuto'
Lomuto的算法也主要取决于在被分区的数组的第一个或最后一个位置的元素上的旋转.如果你转动一个不在数组前端或最后端的元素,那么Lomuto分区工作原理的循环不变量将是一场噩梦.
您可以通过将第一个(或最后一个,如果以此方式实现)元素作为第一步进行交换来转动数组的不同元素.查看麻省理工学院关于Quicksort的6.046J课程的视频讲座,他们深入讨论了Lomuto的分区算法(虽然他们只称它为Partition)和基于它的快速分类的vanilla实现,更不用说讨论预期运行时的一些很大概率了.随机形式的快速排序:
http://www.youtube.com/watch?v=vK_q-C-kXhs
CLRS和编程珍珠在快速排序方面都有很好的部分,如果你可能因使用劣质书籍而无法使用算法类或类似东西.
| 归档时间： |
|
| 查看次数： |
2294 次 |
| 最近记录： |