以中间要素为枢轴的QuickSort [英] QuickSort with middle elemenet as pivot
本文介绍了以中间要素为枢轴的QuickSort的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我正在尝试搜索有关快速排序如何以中间元素为枢轴的任何解释,但我找不到任何解释.我要寻找的是关于如何逐步对数字进行排序的任何演示,因为它真的很难理解算法.谢谢.
I am trying to search for any explanation on how Quick sort works with middle element as pivot but I couldn't find any. What I am trying to look for is there any demo on how the numbers are sorted step by step because its really hard understanding the algorithms. Thanks.
推荐答案
竖线围绕枢轴:
61 11 93 74 75 21 12|55|81 19 14 86 19 79 23 44
44 11 23|19|14 21 12 19
19|11|12 14
11
19|12|14
12
|19|14
14
19
19|21|23 44
|19|21
19
21
|23|44
23
44
81 55 75|86|74 79 93 61
81 55|75|61 74 79
74|55|61
55
|74|61
61
74
75|81|79
|75|79
75
79
81
|93|86
86
93
11 12 14 19 19 21 23 44 55 61 74 75 79 81 86 93
基于Hoare分区方案的这种变化:
Based on this variation of Hoare partition scheme:
void QuickSort(int a[], int lo, int hi) {
int i, j, p;
if (lo >= hi)
return;
i = lo - 1;
j = hi + 1;
p = a[(lo + hi)/2];
while (1)
{
while (a[++i] < p) ;
while (a[--j] > p) ;
if (i >= j)
break;
swap(a+i, a+j);
}
QuickSort(a, lo, j);
QuickSort(a, j + 1, hi);
}
请注意,枢轴可以在分区步骤结束时出现在左侧或右侧.
Note that the pivot can end up in either the left or right part after partition step.
这篇关于以中间要素为枢轴的QuickSort的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文