快速排序的随机化版本_快速排序随机版本-CSDN博客

本文链接：https://blog.csdn.net/wenjiashun/article/details/38986071

该博客展示了随机化快速排序的代码实现。通过生成随机数，对数组进行随机划分，再进行快速排序。代码包含随机数生成、数组划分、随机划分及快速排序等函数，最后输出排序前后的数组。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

//就是从p到r之间产生一个随机数，i将A[i]和A[r]交换就行
#include <iostream>
#include <cstdlib>
#include <ctime>
#define NUMBER 20
using namespace std;

int random(int p,int r);//产生p到r之间的随机数
int partition(int *sPtr,int p,int r);//将数组进行划分
int randomizedPartition(int *sPtr,int p,int r);//将数组进行随机划分
void randomizedQuickSort(int *sPtr,int p,int r);//快速排序随机版
void print(int *sPtr,int number);
void exchange(int *a,int *b);

int main()
{
	srand(unsigned(time(NULL)));
	int A[NUMBER+1] = {0};
	for(int i=1;i<=NUMBER;i++)
		A[i] = rand()%101;//产生0到100之间的随机数
	cout << "before quickSort,the array is:" << endl;
	print(A,NUMBER);
	randomizedQuickSort(A,1,NUMBER);
	cout << "after quickSort,the array is:" << endl;
	print(A,NUMBER);
	system("pause >> cout");
	return 0;
}

int random(int p,int r)
{
	srand(unsigned(time(NULL)));
	if(r-p==0)
		return p;
	return p+rand()%(r-p+1);
}
int partition(int *sPtr,int p,int r)
{
	int i = p;
	for(int j=p;j<r;j++)
	{
		if(sPtr[j]<sPtr[r])
		{
			exchange(&sPtr[i],&sPtr[j]);
			i = i + 1;
		}
	}
	exchange(&sPtr[i],&sPtr[r]);
	return i;
}
int randomizedPartition(int *sPtr,int p,int r)
{
	int q = random(p,r);
	exchange(&sPtr[q],&sPtr[r]);
	return partition(sPtr,p,r);
}
void randomizedQuickSort(int *sPtr,int p,int r)
{
	if(p<r)
	{
		int q = randomizedPartition(sPtr,p,r);
		randomizedQuickSort(sPtr,p,q-1);
		randomizedQuickSort(sPtr,q+1,r);
	}
}
void print(int *sPtr,int number)
{
	for(int i=1;i<=number;i++)
		cout << " " << sPtr[i];
	cout << endl;
}
void exchange(int *a,int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}