【算法导论】C++实现的随机化的快速排序

C++实现的随机化的快速排序：

#include <iostream>
#include <set>
#include <string>
void swap（int * a,int * b）;
int partition（int * array_list,int left,int right）;
void Print（）;
int random_partition（int * array_list,int left,int right）;
void random_quick_sort（int * array_list,int left,int right）;
const int size = 100;
//int array_list [] ={2,8,7,1,3,5,6,4};
int * array_list;
int main（）
{
//const int size = 10;
array_list = new int [sizeof（int）*size];
srand（0）;
for（int i=0;i<size;i++）
{/*随即的填充数组元素*/
int ran_num=rand（）% size;
array_list[i] = ran_num;
}
random_quick_sort（array_list,0,size - 1）;
Print（）;
return 0;
}
void random_quick_sort（int * array_list,int left,int right）
{
if（left >= right）
{
return ;
}
int index = random_partition（array_list,left,right）;
random_quick_sort（array_list,left,index - 1）;
random_quick_sort（array_list,index + 1,right）;
}
/*随机化的快速排序对于输入的元素加入随机化的成分，使之获得较好的平均性能*/
int random_partition（int * array_list,int left,int right）
{
srand（left）;
int ran_num=（ rand（））% right;
if（（ran_num < left ））
{/*防止出现因为取模后随机数为0的情况*/
ran_num = left;
}
/*如果，不交换排序区间内的数据，则成为普通的快速排序*/
swap（&array_list[right],&array_list[ran_num]）;
return partition（array_list,left,right）;
}
int partition（int * array_list,int left,int right）
{
int index = left;
int pivot = array_list[right];
for（int i= left ; i< right; i++）
{
if（array_list[i] < pivot）
{
swap（&array_list[index],&array_list[i]）;
index ++;
}
}
swap（&array_list[right],&array_list[index]）;
//Print（）;
return index;
}
void swap（int * a,int * b）
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void Print（）
{
for（int i=0;i< size;i++）
{
std::cout<<array_list[i]<<" ";
}
std::cout<<std::endl;
}