【C语言】快排(霍尔法)的底层逻辑——二叉树分治

霍尔快排代码：

void Swap(int* a, int* b)
{
	int tmp = 0;
	tmp = *a;
	*a = *b;
	*b = tmp;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int left = begin,right = end;
	int keyi = left;
	while (left < right)
	{
		while(left<right&&a[right] >= a[keyi])
			right--;
		while (left < right && a[left] <= a[keyi])
			left++;
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	keyi = left;
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

逻辑：

left和right往中间走，right先走，找数值比a[keyi]小的
left后走，找数值比a[keyi]大的
最后当left和right相遇时，把a[left]和a[keyi]的值交换，并把下标left和keyi也交换
这时候，以keyi为根节点，左边看成左子树，右边看成右子树，只要左右都各自排成有序，整个数组就有序了
所以接下来进行左子树和右子树的递归

易错点：

这个条件就控制了当递归到只剩一个节点和没有节点时，就返回

两个子循环的条件也要加上left<right
否则如果没有比a[keyi]小的数，right就会一直减减，导致越界；没有比a[keyi]大的数left就会一直加，导致越界