【算法设计-快速排序】随机快速排序算法

浏览数：14 / 时间：2015年06月08日

1.算法流程：

技术分享

但是为了减少算法因为初始数据可能已经部分按大小排序，导致算法复杂性会变成o(n2)进行了随机选择方法

在random_partition中随机产生(p,r)之间的一个数字，然后交换A[i]与A[r]这样会使得快速排序算法的复杂性得到降低。

代码实现：

#include<stdio.h>
#include<stdlib.h>
#define DataType int
void FastSort(DataType A[], int left, int right);//快速排序
int random_partition(DataType A[],int p,int r)
{

int i=rand()%(r-p+1)+p;
{
int temp=A[i];
A[i]=A[r];
A[r]=A[i];
}
int x=A[r];
int i=p-1;
for(int j=p;j<=r-1;j++)
{
if(A[j]<=x)
{
i=i+1;
{
int temp=A[i];
A[i]=A[j];
A[j]=temp;
}
}
}
{
int temp=A[i+1];
A[i+1]=A[r];
A[r]=temp;
}
return i+1;
}
void FastSort(DataType A[], int left, int right)
{
if(left<right)
{
int pivotloc=partition(A,left,right);
FastSort(A,left,pivotloc-1);
FastSort(A,pivotloc+1,right);
}
}

DataType main(void)
{
DataType *A = (DataType *)malloc(sizeof(DataType));
DataType key;
DataType i = 1;
A[0] = 0;
printf("请您随便输入数字，然后本程序对这些数字从小到大排序!按#结束\n");
while (scanf("%d", &key) == 1)
{
A[i] = key;
i++;
}
printf("排序后的结果是：\n");
FastSort(A, 1,i - 1);
DataType k;
for (k = 1; k <= i - 1; k++)
printf("%d ", A[k]);
return 0;
}