快速排序里的学问：霍尔快排的实现

专题的前一篇讲了快速排序的始祖——霍尔快排，那么这里就简单地实现一下霍尔快排。

补充说明下，快排的一个核心步骤是选取枢纽元，通常的做法是将第一个元素用作枢纽元，《算法导论》里的快排例子和Hoare快排都是这种枢纽元选择。先撇开效率不说，我们先看看Hoare快排的实现：

#include "stdio.h"
#include "math.h"
#include "stdlib.h"

int num = 10;

void PrintArray(int arr[])
{
    int i;
	for(i=0; i =枢纽
int Partition(int *arr, int beg, int end)
{
	int low = beg, high = end;
	//选定枢轴
	int sentinel = arr[beg];
	while(low =sentinel)
		{
            //printf("\n    arr[%d](%d) >= sentinel(%d)", high, arr[high], sentinel);
		    --high;
		    //printf(". high自减为%d, 此时 arr[high] 为 %d", high, arr[high]);
		}
		arr[low] = arr[high];
		//printf("\n    赋值-> arr[low](arr[%d]) = arr[high](arr[%d]) = %d", low, high, arr[low]);
		//printf("\n    比sentinel(%d)小的都丢到左边", sentinel);
		//比枢纽大的交换到高端
		while(low  arr[high](arr[%d]) = arr[low](arr[%d]) = %d", high, low, arr[high]);
	}
	arr[low] = sentinel;

	printf("\n排序过程:");
	PrintArray(arr);
	return low;
}

void QuickSort(int *arr, int beg, int end)
{
	if(beg 

程序运行结果为：

初始数组:80 16 97 6 12 92 31 52 54 89
排序过程: [ 54 16 52 6 12 31 ] 80 [ 92 97 89 ]
排序过程:[ 31 16 52 6 12 ] 54 [ 80 92 97 89 ]
排序过程:[ 12 16 6 ] 31 [ 52 54 80 92 97 89 ]
排序过程:[ 6 ] 12 [ 16 31 52 54 80 92 97 89 ])
排序过程:[ 6 12 16 31 52 54 80 89 ] 92 [ 97 ]
最后结果:6 12 16 31 52 54 80 89 92 97
Process returned 0 (0x0)   execution time : 0.384 s
Press any key to continue.


排序的思路是，选定一个枢纽元，比枢纽元大的全部丢到右边，比枢纽元小的全部丢到左边，可以看看下图：



对霍尔快排的思路清晰了吧？

前面提到了，《算法导论》里的快排例子和Hoare快排都是将第一个元素用作枢纽元的排序，当然也有其它选择法，后面会介绍到。
						
延伸阅读
此文章所在专题列表如下：
快速排序里的学问：从猜数字开始
快速排序里的学问：再看看称球问题
快速排序里的学问：信息熵
快速排序里的学问：快速排序的过程
快速排序里的学问：霍尔与快速排序
快速排序里的学问：霍尔快排的实现
快速排序里的学问：枢纽元选择与算法效率
快速排序里的学问：随机化快排
						
本文地址：http://www.nowamagic.net/librarys/veda/detail/2396，欢迎访问原出处。