专题的前一篇讲了快速排序的始祖——霍尔快排，那么这里就简单地实现一下霍尔快排。
补充说明下，快排的一个核心步骤是选取枢纽元，通常的做法是将第一个元素用作枢纽元，《算法导论》里的快排例子和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，欢迎访问原出处。
