基本思想

       通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。快速排序使用分治法来把一个串（list）分为两个子串行（sub-lists）。

注意分组的时候先从右边开始比较，因为之前记录的基数是开始的位置，所以循环之前开始部分是空的，因此从右边开始。分组时需要记住左右震荡的技巧。

主要代码及示例

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

void QuickSort(int a[], int left, int right);

int main()
{
	const int nLen = 20;
	int a[nLen] = {0};

	srand((unsigned int)time(NULL));
	for (int i=0; i<nLen; i++)
	{
		a[i] = rand()%100;
	}

	/** 排序前 */
	for (int i=0; i<nLen; i++)
	{
		printf("%2d ", a[i]);
	}
	printf("\n");

	QuickSort(a, 0, nLen-1);
	/** 排序后 */
	for (int i=0; i<nLen; i++)
	{
		printf("%2d ", a[i]);
	}
	printf("\n");
}
/** 快速排序的思想
 *  快速排序先选定基数（一般选择第一个），然后把大于该数的元素放到右侧，
 *  小于该数的元素放到左侧，在比较的时候从右往左到从左往右式震荡式排序，
 *  如此实现基数位置的排序，根据基数的正确位置，分别使用递归快排左右两
 *  端，即可实现整个序列的排序
 */


int QuickPart(int a[], int left, int right)
{
	int base = a[left];

	while(left < right)
	{
		// 因为a[left]为空，所以从右边开始
		while(right>left && a[right]>base)
		{
			right--;
		}
		a[left] = a[right];

		while(left<right && a[left]<=base)
		{
			left++;
		}
		a[right] = a[left];
	}

	a[left] = base;

	return left;
}

void QuickSort(int a[], int left, int right)
{
	if(left < right)
	{
		int n = QuickPart(a, left, right);

		QuickSort(a, left, n-1);
		QuickSort(a, n+1, right);
	}
}

结果展示

47  8 13 33 22 78 11 31 53  3  1 86 37 91 62 68 25 82 61 76
 1  3  8 11 13 22 25 31 33 37 47 53 61 62 68 76 78 82 86 91

快速排序