数据结构排序——快排的递归与非递归

1.霍尔排序（递归方法） 

这个是将右边找到比key小的数字，之后让左边找到比key大的数字，让左右的交换，如果相遇就会停止，让key与他们停止的位置进行交换，这时，交换的位置一定比key小，完成这一次之后，key左边都是比他小的，右边都是比他大的。（这只是第一遍）

void kuaipai1(int* a, int left, int right)
{
	if (left >= right)
		return;
	int keyi = left;
	int begin = left;
	int end = right;
	while (begin < end)
	{
		while (begin < end && a[begin] < a[keyi])
		{
			begin++;
		}
		while (begin<end && a[end]>a[keyi])
		{
			end--;
		}
		int tem = a[end];
		a[end] = a[begin];
		a[begin] = tem;
	}
	int tem = a[keyi];
	a[keyi] = a[end];
	a[end] = tem;
	keyi = begin;
	kuaipai1(a, left, keyi - 1);
	kuaipai1(a, keyi + 1, right);
}

我们排完第一遍的时候，key的位置是已经确定的了，所以将左边与右边再次带入函数中，进行递归，直到left与right相同或大于。这就像二叉树一样，根，左子树，右子树。 

while循环的条件begin<end是因为防止他寻找小的数字时，越过了left，造成错误。 

这里我只是演示了key左边的快排，这里我们可以看见结束快排的right=left的情况。

（这里我们也可以让右边为key，但是你要让左边先动，让左边找到大的与右边交换，最后让left与key交换） 

2.双指针 （递归方法）

void kuaipai2(int* a, int left, int right)
{
	if (left >= right)
		return;
	int cur, prev;
	int keyi = left;
	cur = keyi;
	prev = keyi + 1;
	while (prev <= right)
	{
		if (a[prev] < a[keyi] && ++cur != prev)
		{
			int tem = a[prev];
			a[prev] = a[cur];
			a[cur] = tem;
		}
		prev++;
	}
	int tem = a[keyi];
	a[keyi] = a[cur];
	a[cur] = tem;
	keyi = cur;
	kuaipai2(a, left, keyi - 1);
	kuaipai2(a, keyi + 1, right);
}

这里当prev小于keyi的时候，就会让cur++，并且交换值，再让prev++，但是交换的时候有一个前提，就是cur++之后他不可以等于prev，当相等时不会发生交换，但是会让cur+1。完成后会再让 cur与keyi交换。在进行相同的递归。

3.非递归法（要用到栈的知识） 

数据结构----栈和队列-CSDN博客

void kuaipai3(int* a, int left, int right)
{
	ST ps;
	Init(&ps);
	Push(&ps, right);
	Push(&ps, left);
	while (ps.top>0)
	{
		int begin = Top(&ps);
		Pop(&ps);
		int end = Top(&ps);
		Pop(&ps);
		int keyi=fuzhu(a,begin,end);
		if (keyi < end)
		{
			Push(&ps, end);
			Push(&ps, keyi + 1);
		}
		if (begin < keyi)
		{
			Push(&ps, keyi - 1);
			Push(&ps, begin);
		}
	}
	Destory(&ps);
}

int fuzhu(int* a, int left, int right)
{
	int cur, prev;
	int keyi = left;
	cur = keyi;
	prev = keyi + 1;
	while (prev <= right)
	{
		if (a[prev] < a[keyi] && ++cur != prev)
		{
			int tem = a[prev];
			a[prev] = a[cur];
			a[cur] = tem;
		}
		prev++;
	}
	int tem = a[keyi];
	a[keyi] = a[cur];
	a[cur] = tem;
	keyi = cur;
	return keyi;
}

这里的Push是将你指定的数字输入到栈中，Top的意思是获得栈顶的数据，Pop的意思是去掉栈顶的数据，Destory是销毁栈。

这里我先将你要排序的最左边与最右边的下标传到栈中，再用begin为左边的下标，end为右边的下标 ，用fuzhu函数进行第一次排序，并返还keyi的位置，然后在进行类似左子树的区间与右子树的区间，就像霍尔方法的一样，将key的左边，右边的范围输入到栈中，最后再取左边的区间，再进行排序，但是这时会不停的对左边进行排序，直到左边排序完成，再进行右边的排序。（因为是先输入右边，再输入左边，根据栈的规则先进后出，所以会一直取左边的区间）