快速排序（快排）——C语言实现

时间复杂度： 快速排序（quicksort）的平均运行时间是O(N·logN)，最坏情形是O(N^2)。

算法思想： 是一种分治的递归算法。如果是升序排序，则首先选取一个元素key，将小于key的元素放在左边，小于key的元素放在右边。再对左右进行类似的操作，直到排序完成。

个人觉得快排涉及的还挺多，如key的选取，程序的递归与非递归实现等。

我的代码是简单的递归实现，后续学习再一点点补充吧。

①先动右指针，找到比key小的元素，此时右指针指向这个元素，然后用这个元素的值覆盖掉左指针指向的元素；

②再动左指针，找到比key大的元素，此时左指针指向这个元素，然后用这个元素的值覆盖掉右指针指向的元素；

③直到左右指针相遇（i==j），此时用key的值覆盖当前左或右指针指向的元素；

④左递归；

⑤右递归。

/*	快排1.0
*	作者：Talentq
*	日期：2020.8.15
*/
#include <stdio.h>

void quickSort(int array[], int left, int right);

int main(void)
{
	int i;
	int array[] = { 5,4,3,2,1,10,9,8,7,6 };	//待排序数组
	int len = sizeof(array) / sizeof(int);	//数组的长度

	quickSort(array, 0, len - 1);	//排序

	for (i = 0; i < 10; i++)	//打印排序后的数组
		printf("%d\n", array[i]);

	return 0;
}

void quickSort(int array[], int left, int right)
{
	int i, j, key;
	if (left >= right)
		return;
	i = left; j = right;
	key = array[i];	//取最左边的元素作为key
	while (i < j)
	{	//始终保持i < j
		while (i < j && array[j] > key)//右指针向左
			j--;
		if (i < j)	//小于key的放左边
			array[i++] = array[j];

		while (i < j && array[i] < key)//左指针向右
			i++;
		if (i < j)	//大于key的放右边
			array[j--] = array[i];
	}
	array[i] = key;	//最终将key放入i==j处

	quickSort(array, left, i - 1);	//左边递归
	quickSort(array, i + 1, right);	//右边递归
}