30.快速排序

算法思想时这样的：

1.每次选取第一个数为基准数；

2.然后使用“乾坤挪移大法”将大于和小于基准的元素分别放置于基准数两边；

3.继续分别对基准数两侧未排序的数据使用分治法进行细分处理，直至整个序列有序。对于下面待排序的数组:

第一步：先选择第一个数163 为基准数，以163 为基准将小于它的数排在它前面，大于等于它的数排在其后，结果如下:

具体排列数据的步骤如下：

1.确定163 为基准数后，先把163 从数组中取出来

2.然后从最右端开始，查找小于基准数163 的数，找到162，将其移至空出来的元素中

3.接下来，从最左边未处理的元素中从左至右扫描比基数163 大的数，将其移动至右侧空出来的元素中

4.接下来，继续从最右边未处理的元素中从右至左扫描比基数163 小的数，将其移动至左侧空出来的元素中

接下来再重复执行步骤3，171 执行右移

重复执行步骤4，此时右边的值已经均大于基数，左边的值均已小于基数

接下来我们将基数保存回黄色空格中

第二步：采用分治法分别对基数左边和右边的部分运用第一步中的方法进行递归操作，直到整个数组变得有序，以左边的数组为例:

选择162 为基数，运用“乾坤挪移大法”得到结果如下:

以162 为界，把数组分成两个部分，此时，基数右侧已经没有数据，所以，接下来只要继续对左侧的数组分治处理即可，选择159 为基数，再次运用“乾坤挪移大法”得到结果如下:

代码实现：

#include <stdio.h>
#include <stdlib.h>

int partition(int arr[], int low, int high)
{
	int i = low;
	int j = high;
	int base = arr[low];

	if(low < high)
	{
		while (i < j)
		{
			while (i < j && arr[j] >= base)
			{
				j--;
			}

			if (i < j)//右边已经找到小于基数的数
			{
				arr[i++] = arr[j];
			}

			while (i < j && arr[i] < base)
			{
				i++;
			}

			if (i < j)//左边已经找到大于基数的数
			{
				arr[j--] = arr[i];
			}
		}

		arr[i] = base;
	}

	return i;
}

void QuickSort(int* arr, int low, int high)//实现快速排序
{
	if (low < high)
	{
		int index = partition(arr, low, high);

		QuickSort(arr, low, index - 1);
		QuickSort(arr, index + 1, high);
	}
}

int main()
{
	int arr[] = { 163, 161, 170, 158, 165, 171, 170, 163, 159, 162 };
	int len = sizeof(arr) / sizeof(arr[0]);

	int index = partition(arr, 0, len - 1);
	printf("分区完毕， 基数下标: %d\n", index);

	QuickSort(arr, 0, len - 1);
	printf("执行快速排序后的结果：\n");
	for (int i = 0; i < len; i++)
	{
		printf(" %d", arr[i]);
	}

	system("pause");
	return 0;
}

参考资料来源：

奇牛学院