//快速排序
#include<iostream>
usingnamespace std;
void Quicksort(intarray[],inta,intb)
{
if (a > b)
return;
int start =a;
int end =b;
int key =array[start];//用字表的第一个记录作为枢轴
while (start < end)
{
while (start < end&&array[end] >= key)
--end;
array[start] =array[end];//将比第一个小的移到低端
while (start < end&&array[start] <= key)
++start;
array[end] =array[start];//将比第一个大的移到高端
}
array[start] = key;//枢轴记录到位
Quicksort(array,a,start-1);
Quicksort(array,start+1,b);
}
int main()
{
int a[8] = { 10, 85, 15, 61, 47, 92, 45, 20 };
Quicksort(a,0,sizeof(a)/sizeof(a[0])-1);
for (int i = 0; i<sizeof(a) /sizeof(a[0]); i++)
{
cout << a[i] <<" ";
}
cin.get();
return 0;
}
//随机化快速排序
#include<iostream>
#include<ctime>
usingnamespace std;
void swap(int &a,int &b);
int partition(int A[],int start,int end);
intrandomized_partition(int A[],int start,int end);
voidrandomized_quick_sort(int A[],int start,int end);
int random(int start,int end);
int main()
{
int test[] = { -1, 2, 7, 6, 3, 5 };
randomized_quick_sort(test, 0,sizeof(test)/sizeof(test[0])-1);
for (int i = 0; i<(sizeof(test) /sizeof(test[0])); i++)
printf("%d ", test[i]);
cin.get();
return 0;
}
//划分区域
int partition(intA[],intstart,intend)
{
int base =A[end];//以最后一个数作为划分的基点
int i =start -1;
for (int j = start; j <end; j++)
{
if (A[j] <= base)
{
i++;
swap(A[i],A[j]);
}
}
swap(A[i+1],A[end]);
return i + 1;
}
//随机得到基数值
intrandomized_partition(intA[],intstart,intend)
{
int t = random(start,end);
swap(A[t],A[end]);
return partition(A,start,end);
}
//快排的随机化版本
voidrandomized_quick_sort(intA[],intstart,intend)
{
if (start<end)
{
int t =randomized_partition(A,start,end);
randomized_quick_sort(A,start, t - 1);
randomized_quick_sort(A, t + 1,end);
}
}
//交换
void swap(int &a,int &b)
{
int temp =a;
a =b;
b = temp;
}
//得到start到end之间的随机整数
int random(intstart,intend)
{
int t;
srand(time(NULL));
while (true)
{
t = rand() % (end + 1);
if (t >=start)
return t;
}
}