快速排序（递归方式）

前言：

快速排序有两种实现：递归和非递归。本篇文章将以递归的方式实现快速排序，并对其进行优化。

排序思想：

解释为何最后key对应的值会放入正确位置：

，一组数据将指针从数组尾部开始，每有一个比key大的数句向前移动一次，R指针最后移动了比key值大的数的个数，到达key的正确排序位置。

 利用指针遍历对应的数组区间，每一次便利完成都会将key对应的值放入正确的位置。这样通过多次排序最终每一个值的位置都正确，就排序完成。

void Swap(int* a, int* b)//交换数据
{
	int i = *a;
	*a = *b;
	*b = i;
}

void myQsort(int* a, int n)//实现函数
{
	if (n <= 1)
	{
		return;
	}
	int begin = 0;
	int end = n - 1;
	int* k = a + begin;//将开始的数据作为初始的K值进行比较

	while (begin < end)//遍历数组将K放到对应的位置
	{
		while (end > 0 && *(a + end) >= *k)
		{
			end--;
		}
		while (begin < end && *(a + begin) <= *k)
		{
			begin++;
		}
		Swap(a + begin, a + end);
	}
	Swap(k, a + end);

	myQsort(a,end);//函数递归，实现前后分别排序

	myQsort(a + end + 1,n-end-1);
}

这里后面的思想也就是递归分治，是堆和队列问题中的简单思想。

优化：

当我们的数组有序时我们的快速排序的效率就会和冒泡排序一样对数组进行完全遍历，这时的时间复杂度为O(N^2)。那么这就需要我们对这种情况进行改进：

随机数取key法:

通过每一次随机取key值来避免有序的问题：

添加一个随机数生成，将k设置为符合一定范围内（在数组范围，不要越界）随机值

void Swap(int* a, int* b)//交换数据
{
	int i = *a;
	*a = *b;
	*b = i;
}

void myQsort(int* a, int n)//实现函数
{
	if (n <= 1)
	{
		return;
	}
	srand(time(NULL));
	int begin = rand() % n;//保证begin依旧在数组之间

	int end = n - 1;

	int* k = a + begin;//将开始的数据作为初始的K值进行比较

	while (begin < end)//遍历数组将K放到对应的位置
	{
		while (end > 0 && *(a + end) >= *k)
		{
			end--;
		}
		while (begin < end && *(a + begin) <= *k)
		{
			begin++;
		}
		Swap(a + begin, a + end);
	}
	Swap(k, a + end);

	myQsort(a,end);//函数递归，实现前后分别排序

	myQsort(a + end + 1,n-end-1);
}

另外优化方法：还有三数取中法，取三个数的中间大小的数，这里我们不再讲述