首页 > 代码库 > 霍尔快排的C语言实现
霍尔快排的C语言实现
专题的前一篇讲了快速排序的始祖——霍尔快排，那么这里就简单地实现一下霍尔快排。
补充说明下，快排的一个核心步骤是选取枢纽元，通常的做法是将第一个元素用作枢纽元，《算法导论》里的快排例子和Hoare快排都是这种枢纽元选择。先撇开效率不说，我们先看看Hoare快排的实现：香格里拉娱乐城
01 | #include "stdio.h" |
02 | #include "math.h" |
03 | #include "stdlib.h" |
04 |
05 | int num = 10; |
06 |
07 | void PrintArray(int arr[]) |
08 | { |
09 | int i; |
10 | for(i=0; i < num; ++i) |
11 | { |
12 | printf("%d ", arr[i]); |
13 | } |
14 | } |
15 |
16 | //一趟快排之后，以枢纽为分隔，左边的<=枢纽, 右边的>=枢纽 |
17 | int Partition(int *arr, int beg, int end) |
18 | { |
19 | int low = beg, high = end; |
20 | //选定枢轴 |
21 | int sentinel = arr[beg]; |
22 | while(low < high) |
23 | { |
24 | //printf("\n 定点取arr[%d]的值，设为 sentinel(%d)", low, sentinel ); |
25 | //printf("\n 比sentinel(%d)大的都丢到右边", sentinel); |
26 | //比枢纽小的交换到低端 |
27 | while(low < high && arr[high]>=sentinel) |
28 | { |
29 | //printf("\n arr[%d](%d) >= sentinel(%d)", high, arr[high], sentinel); |
30 | --high; |
31 | //printf(". high自减为%d, 此时 arr[high] 为 %d", high, arr[high]); |
32 | } |
33 | arr[low] = arr[high]; |
34 | //printf("\n 赋值-> arr[low](arr[%d]) = arr[high](arr[%d]) = %d", low, high, arr[low]); |
35 | //printf("\n 比sentinel(%d)小的都丢到左边", sentinel); |
36 | //比枢纽大的交换到高端 |
37 | while(low < high && arr[low]<=sentinel) |
38 | { |
39 |
40 | //printf("\n arr[%d](%d) <= sentinel(%d)", low, arr[low], sentinel); |
41 | ++low; |
42 | //printf(". low自增为%d, 此时 arr[low] 为 %d", low, arr[low]); |
43 | } |
44 | arr[high] = arr[low]; |
45 | //printf("\n 赋值-> arr[high](arr[%d]) = arr[low](arr[%d]) = %d", high, low, arr[high]); |
46 | } |
47 | arr[low] = sentinel; |
48 |
49 | printf("\n排序过程:"); |
50 | PrintArray(arr); |
51 | return low; |
52 | } |
53 |
54 | void QuickSort(int *arr, int beg, int end) |
55 | { |
56 | if(beg < end) |
57 | { |
58 | int pivot = Partition(arr, beg, end); |
59 | //分治思想，递归排序 |
60 | QuickSort(arr, beg, pivot-1); |
61 | QuickSort(arr, pivot+1, end); |
62 | } |
63 | } |
64 |
65 | int main() |
66 | { |
67 | int i; |
68 | int arr[10]; |
69 |
70 | srand(time(0)); |
71 | for(i=0; i < 10; i++) |
72 | { |
73 | arr[i] = rand()%100+1; |
74 | //printf("%d ", rand()%100+1); |
75 | } |
76 | printf("初始数组:"); |
77 | PrintArray(arr); |
78 |
79 | QuickSort(arr, 0, num-1); |
80 |
81 | printf("\n最后结果:"); |
82 | PrintArray(arr); |
83 |
84 | return 0; |
85 | } |
程序运行结果为：
1 | 初始数组:80 16 97 6 12 92 31 52 54 89 |
2 | 排序过程: [ 54 16 52 6 12 31 ] 80 [ 92 97 89 ] |
3 | 排序过程:[ 31 16 52 6 12 ] 54 [ 80 92 97 89 ] |
4 | 排序过程:[ 12 16 6 ] 31 [ 52 54 80 92 97 89 ] |
5 | 排序过程:[ 6 ] 12 [ 16 31 52 54 80 92 97 89 ]) |
6 | 排序过程:[ 6 12 16 31 52 54 80 89 ] 92 [ 97 ] |
7 | 最后结果:6 12 16 31 52 54 80 89 92 97 |
8 | Process returned 0 (0x0) execution time : 0.384 s |
9 | Press any key to continue. |
排序的思路是，选定一个枢纽元，比枢纽元大的全部丢到右边，比枢纽元小的全部丢到左边，可以看看下图：
对霍尔快排的思路清晰了吧？
前面提到了，《算法导论》里的快排例子和Hoare快排都是将第一个元素用作枢纽元的排序，当然也有其它选择法，后面会介绍到。
霍尔快排的C语言实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。