[C++知识库]单循环完成快速排序（C语言）

注：这个代码是一位强者教我的，我以一个初学者的思维加了点注来帮助更多像我一样刚刚入门想学习算法又不会C++的编程者们理一理思路（我是屑大学生，加的注可能会有逻辑不严谨的地方），希望对你们有些帮助

下面以一个内含0~9十个数字的简单数组来展示单循环完成的快速排序

#include<stdio.h>
void quicksort(int a[], int left, int right) //这个加不加void都行，加了更严谨
{
	int p;
	if (left < right) 
	{
		p = left;
		int index = p + 1;
		/*单循环完成分区，用index“锁住”在左区第一个出现的比基准值大的值，并把它当做“搬运工”，以
		交换的形式把该点右边所有比基准值小的数放到左边，最后把基准值的位置放在搬运完成后第一个比基准
		值大的值后面，就完成了一次分区*/
		for (int i = index; i <= right; i++)
			if (a[i] < a[p]) 
			{
				int t = a[i];
				a[i] = a[index];
				a[index] = t;
				index++;
		/*每有一个比基准值小的数，基准值要确定的位置就往前走一步，当有比基准值大的数出现时，让i
		去找该数后面比基准值小的数，然后交换a[index]内存的数和a[i]内存的数。注意，只是交换数，
		index实际上表示的是位置，他只是一个基准值的备用参考容器，每出现一个比基准值大的值，index
		就会被拖慢一步，这样最终index和i的差值就是比基准值大的值的个数，也即右区的长度，以此来完成分区*/
			}
		int t = a[p];//把基准值放到它该到的位置上
		a[p] = a[index - 1];
		a[index - 1] = t;
		p = index - 1;
		quicksort(a, left, p - 1);//先分左边
		quicksort(a, p + 1, right);//再分右边
		/*注意，对于部分“找第几”的问题，以那个“第几”为left或right，然后只排一边即可*/
	}
}
int main() 
{
	int a[10] = { 6, 1, 2, 4, 9, 3,7, 10, 8, 5 };//目标数组
	quicksort(a, 0, 9);
	for (int i = 0; i < 10; i++) 
		printf("%d ", a[i]);
	return 0;
}