随机化快排
2024-07-22 10:14:04 214人阅读
前一篇文章讲到了选择枢纽元的几种方法,其实第二种是随机选择元素作为枢纽元。那么在这篇文章里就实现一个随机化排序。
算法与前面《算法导论》里的例子差不多,只是在调用分割Partition时加入一个随机数,具体可以参看程序。PowerBet
C语言代码为:
07 | void swap( int *a, int *b) |
15 | void PrintArray( int arr[]) |
18 | for (i=0; i < num; ++i) |
20 | printf ( "%d " , arr[i]); |
24 | int Partition( int *arr, int beg, int end) |
27 | int sentinel = arr[end]; |
29 | for (j=beg; j <= end-1; ++j) |
31 | if (arr[j] <= sentinel) |
34 | swap(&arr[i], &arr[j]); |
37 | swap(&arr[i+1], &arr[end]); |
44 | int RandomPartition( int *arr, int beg, int end) |
46 | int i = beg + rand () % (end-beg+1); |
47 | swap(&arr[i], &arr[end]); |
48 | return Partition(arr, beg, end); |
51 | void RandomQuickSort( int *arr, int beg, int end) |
55 | int pivot = RandomPartition(arr, beg, end); |
56 | printf ( "\n随机选择 arr[%d](%d)" , pivot, arr[pivot]); |
57 | RandomQuickSort(arr, beg, pivot-1); |
58 | printf ( "\n随机选择 arr[%d](%d)" , pivot, arr[pivot]); |
59 | RandomQuickSort(arr, pivot+1, end); |
71 | arr[i] = rand ()%100+1; |
78 | RandomQuickSort(arr, 0, num-1); |
程序运行结果:
01 | 初始数组:79 36 68 39 10 96 59 60 84 21 |
02 | 排序过程:79 36 68 39 10 59 60 21 84 96 |
04 | 排序过程:21 10 36 39 79 59 60 68 [84] 96 |
06 | 排序过程:10 21 [36] 39 79 59 60 68 84 96 |
10 | 排序过程:10 21 [36] 39 79 59 60 68 84 96 |
13 | 排序过程:10 21 36 [39] 68 59 60 79 84 96 |
15 | 排序过程:10 21 36 39 60 59 68 [79] 84 96 |
17 | 排序过程:10 21 36 39 59 60 [68] 79 84 96 |
23 | 最后结果:10 21 36 39 59 60 68 79 [84] 96 |
24 | Process returned 0 (0x0) execution time : 0.582 s |
25 | Press any key to continue . |
一般来说随机选取枢纽元这种策略非常安全,除非随机数生成器有问题(这不像你所想象的那么罕见),因为随机的枢纽元不可能总在接连不断地产生劣质的分割。另一方面,随机数的生成一般是昂贵的,根本减少不了算法其余部分的平均运行时间。
比如上面程序的运行结果,可以看到,产生了不少随机数是对排序没有产生有效作用的,而产生这些随机数也耗费了不少时间。当然你也可以选择优化随机数生成器,这样又会引起更多的研究了。
随机化快排
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉:
投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。