快速排序

假设有下面这样一排数据需要排序：

3 7 6 1 2 9 1 2 6

排开常用的冒泡和选择排序，今天我们来试一下一种新的方法：快速排序

快速排序的思路如下：

1. 首先我们要先从这组数据中选出一个任意值X，然后以X为分界，比X小的数据排到X的左半边，比X大的数据排到X的右半边。

2. 然后我们会得到两边数据，并且左边的比X小或等于X，右边的比X大或等于X，然后我们再将这两组数据进行与上面相同的操作，直至分到只有一个数据。因为都是相同的思路，这里我们可以采用递归操作，直至分为单个数据（此时是递归最开始的位置）。

我们来看看最重要的部分，就是如何分出数据左边和右边。这里我们采用设计两个指针，一个从数组左边开始向右走，一个从数组右边向左走。首先左边指针先走，走到它指向的数据大于X，这个指针停下，然后右边指针向左走。如果右边指针指向的数据小于X，则右边指针也停下，两个指针数据交换。然后重复上面过程，直至两指针相交。因为我们是选择先移动指针，再判断大小，所以这里为了方便操作，两个指针选择从两端外开始。下面为第一次互换中，指针的移动历程

多次互换后，我们可以得到一次成功分开数组过程中的每次交换后的数组状态：

下面是代码的实现：

//快速排序

#include<stdio.h>

void quick_sort(int arr[], int l, int r)
{
	if (l == r)
		return;
	int x = arr[l], i = l - 1, j = r + 1;
	//每一个数组划分交换过程
	while (i < j)
	{
	    //左指针右移
		while (arr[++i] < x)
			;
		//右指针左移
		while (arr[--j] > x)
			;
		//交换
		if (i < j)
		{
			int tmp = 0;
			tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
		}
	}
	//递归部分
	quick_sort(arr, l, j);
	quick_sort(arr, j+1, r);
}


int main()
{
	int arr[10] = { 9,8,5,1,2,3,2,1,4,6 };
	quick_sort(arr, 0, 9);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

值得注意的是，下一次递归时的边界问题，因为每一次分数组都会分成两个部分，所以每一次都会有两边递归排序，可以画图看出，最后一次右指针的位置是位于第一部分的最末尾元素，而左指针是位于第二部起始元素。

那么按照这个思想，边界的确定也可以用i来表示，也就可以写成：

	quick_sort(arr, l, i-1);
	quick_sort(arr, i, r);

注意： X的确定问题，如果递归传递的数组边界选择 j 表示，那么X不能取 r ，同理，如果递归传递的数组边界选择用 i 表示，那么X不能取 l 。

举个例子：

此时第一个递归无效，第二个递归传递的参数和原本传递过来的一样，就无限循环了！