数据结构实战

        快速排序的原理是通过一趟排序将待排记录分割成独立的两部分，一部分的关键字均比别一部分的关键字小，然后再分别对这两部分记录做快速排序，直到整个记录都有序为止。具体实现如下：

        任意选取一个记录做为中枢key，将所有关键字小于中枢的排在它的前面，将所有关键字大于它的排在它的后面。另外使用两个指针low和high来记录，它们的初始值分别为待排记录的头和尾。首先从high所指位置起向前搜索一个小于中枢key的值，并与key的位置做交换。再从low开始向后搜索找到一个大于key的值，并与key的位置做交换。直到low与higt相等为止。

#include <stdio.h>

#define SIZE	(10)

//快速排序
void quick_sort(int array[], int size)
{
	//低指针从头开始
	int low = 0;
	//高指针从尾开始
	int high = size - 1;
	//本趟比较枢纽
	int t = array[0];
	//本趟结束条件
	while (low < high)
	{
		//先从高指针向前找到小于枢纽的元素位置
		while (low < high && array[high] >= t)
		{
			high--;
		}
		//与枢纽位置交换
		array[low] = array[high];
		//再从低指针向后找到大于枢纽的元素位置
		while (low < high && array[low] <= t)
		{
			low++;
		}
		//与枢纽位置交换
		array[high] = array[low];
	}
	//当low和high相等时记录枢纽元素
	array[low] = t;
	//计算前半段数组大小
	int size_low = low;
	//计算后半段数组大小
	int size_high = size - low - 1;
	if (size_low > 1)
	{
		//前半段递归快速排序
		quick_sort(array, size_low);
	}
	if (size_high > 1)
	{
		//后半段递归快速排序
		quick_sort(&array[low + 1], size_high);
	}
}

//显示数组
void display(int *array, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
}

int main(int argc, char **args)
{
	int array[SIZE] =
	{ 5, 3, 7, 2, 9, 8, 1, 0, 6, 4 };
	display(array, SIZE);
	quick_sort(array, SIZE);
	display(array, SIZE);

	return 0;
}

        运行结果：

5 3 7 2 9 8 1 0 6 4 
0 1 2 3 4 5 6 7 8 9

        本例代码：

code path   chapter.08/e.g.8.4/

https       https://github.com/magicworldos/datastructure.git
git         git@github.com:magicworldos/datastructure.git
subverion   https://github.com/magicworldos/datastructure