c – 如何进行三个快速排序中位数的最坏情况排列
发布时间:2020-12-16 09:52:28 所属栏目:百科 来源:网络整理
导读:我知道快速排序的时间复杂性.但我想知道如何创建最坏情况的排列. 我想有一条规则要做到.我认为它真的很多,但对我来说太难了. 请告诉我如何创建三个快速排序的中位数的最坏情况,而不是正常的快速排序. (例如,如果pivot是列表中最左侧的项目,列表的最坏情况排
我知道快速排序的时间复杂性.但我想知道如何创建最坏情况的排列.
我想有一条规则要做到.我认为它真的很多,但对我来说太难了. 请告诉我如何创建三个快速排序的中位数的最坏情况,而不是正常的快速排序. here is my quick sort algorithm code 解决方法
实际上,创建一个项目排列并不会导致所有或甚至大多数Quicksort实现都出现最坏情况的行为.事实上,根据排序的实现方式,一次运行中的最坏情况数组在后续运行中可能会很好.如果实现使用中间随机三来选择枢轴,并且每次调用例程时使用不同的种子,则可能发生这种情况.
C qsort函数和许多其他库中的排序库函数很容易受到“Quicksort杀手”算法的影响,但它使用比较回调中提供的信息来动态创建最坏情况.令人惊讶的是,这并不困难.例如,参见A Killer Adversary for Quicksort. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |