快速排序里的学问：随机化快排

前一篇文章讲到了选择枢纽元的几种方法，其实第二种是随机选择元素作为枢纽元。那么在这篇文章里就实现一个随机化排序。

算法与前面《算法导论》里的例子差不多，只是在调用分割Partition时加入一个随机数，具体可以参看程序。

C语言代码为：

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

int num = 10;

void swap(int *a,int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void PrintArray(int arr[])
{
    int i;
	for(i=0; i 

程序运行结果：

初始数组:79 36 68 39 10 96 59 60 84 21
排序过程:79 36 68 39 10 59 60 21 84 96
随机选择 arr[8](84)
排序过程:21 10 36 39 79 59 60 68 [84] 96
随机选择 arr[2](36)
排序过程:10 21 [36] 39 79 59 60 68 84 96
随机选择 arr[1](21)
随机选择 arr[1](21)
随机选择 arr[2](36)
排序过程:10 21 [36] 39 79 59 60 68 84 96
随机选择 arr[3](39)
随机选择 arr[3](39)
排序过程:10 21 36 [39] 68 59 60 79 84 96
随机选择 arr[7](79)
排序过程:10 21 36 39 60 59 68 [79] 84 96
随机选择 arr[6](68)
排序过程:10 21 36 39 59 60 [68] 79 84 96
随机选择 arr[4](59)
随机选择 arr[4](59)
随机选择 arr[6](68)
随机选择 arr[7](79)
随机选择 arr[8](84)
最后结果:10 21 36 39 59 60 68 79 [84] 96
Process returned 0 (0x0)   execution time : 0.582 s
Press any key to continue.


一般来说随机选取枢纽元这种策略非常安全，除非随机数生成器有问题（这不像你所想象的那么罕见），因为随机的枢纽元不可能总在接连不断地产生劣质的分割。另一方面，随机数的生成一般是昂贵的，根本减少不了算法其余部分的平均运行时间。

比如上面程序的运行结果，可以看到，产生了不少随机数是对排序没有产生有效作用的，而产生这些随机数也耗费了不少时间。当然你也可以选择优化随机数生成器，这样又会引起更多的研究了。
						
延伸阅读
此文章所在专题列表如下：
快速排序里的学问：从猜数字开始
快速排序里的学问：再看看称球问题
快速排序里的学问：信息熵
快速排序里的学问：快速排序的过程
快速排序里的学问：霍尔与快速排序
快速排序里的学问：霍尔快排的实现
快速排序里的学问：枢纽元选择与算法效率
快速排序里的学问：随机化快排
						
本文地址：http://www.nowamagic.net/librarys/veda/detail/2398，欢迎访问原出处。