【算法设计-快速排序】随机快速排序算法
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;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
