C++随机化快速排序

小灰灰 2022-05-15 12:57 200阅读 0赞

C++随机化快速排序

// 随机化快速排序.cpp : Defines the entry point for the console application.  
//

\#include "stdafx.h"  
\#include<iostream>  
\#include<ctime>  
using namespace std;  
double a\[100\];

int random(int m,int n)//产生一个随即下标，用其对应的数组元素作为比较标准  
\{  
srand((unsigned)time(NULL));  
return m + (rand()%(n-m+1));  
\}

int qartition(double \*a,int begin,int end) //一趟快速排序  
\{  
  
int i = begin-1,j=begin;  
double x = a\[end\];  
while(j<end)  
\{  
if(a\[j\]<=x)  
\{  
i++;  
double temp = a\[i\];  
a\[i\]=a\[j\];  
a\[j\]=temp;  
\}  
j++;  
\}  
double temp = a\[end\];  
a\[end\]=a\[i+1\];  
a\[i+1\]=temp;  
return i+1;  
\}  
  
int random\_qartition(double \*a,int begin,int end) //一趟随机化快速排序  
\{  
int q = random(begin,end);  
double temp = a\[end\];  
a\[end\]=a\[q\];  
a\[q\]=temp;  
return qartition(a,begin,end);  
\}

void random\_fast\_sort(double \*a,int begin,int end) //随机化快速排序  
\{  
if(begin<end)  
\{  
int p = random\_qartition(a,begin,end);  
random\_fast\_sort(a,begin,p-1);  
random\_fast\_sort(a,p+1,end);  
\}  
\}

int \_tmain(int argc, \_TCHAR\* argv\[\])  
\{  
int cases;  
cout<<"请输入需要排序的案例个数："<<endl;  
cin>>cases;  
while(cases--)  
\{  
memset(a,0.0,sizeof(a));  
int n;  
cout<<"请输入需要排序的元素的个数："<<endl;  
cin>>n;  
cout<<"请输入需要排序的元素："<<endl;  
int i = 0;  
for(i=0;i<n;i++)  
\{  
cin>>a\[i\];  
\}  
cout<<"排序前："<<endl;  
for(i=0;i<n;i++)  
\{  
cout<<a\[i\]<<" ";  
\}  
cout<<endl;  
random\_fast\_sort(a,0,n-1);  
cout<<"排序后："<<endl;  
for(i=0;i<n;i++)  
\{  
cout<<a\[i\]<<" ";  
\}  
cout<<endl;  
\}  
system("pause");  
return 0;  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，200人围观）

还没有评论，来说两句吧...

相关阅读

相关随机化快速排序

一、概念及其介绍快速排序由 C. A. R. Hoare 在 1960 年提出。随机化快速排序基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所

r囧r小猫/ 2024年03月16日 19:01/ 0 赞/ 46 阅读

相关随机化快速排序（Java 实例代码）

随机化快速排序一、概念及其介绍快速排序由 C. A. R. Hoare 在 1960 年提出。随机化快速排序基本思想：通过一趟排序将要排序的数据分割成独立的

谁践踏了优雅/ 2023年10月14日 14:57/ 0 赞/ 47 阅读

相关排序算法——随机快速排序

引言随机快排是一个非常有意思的排序排序算法，它的算法思想用到了如递归、荷兰国旗问题等诸多元素，还意外的引入了随机性的概念。以下将逐步总结三个版本的快速排序，由浅入深

た入场券/ 2023年01月16日 12:27/ 0 赞/ 119 阅读

相关排序算法c语言描述-快速排序随机化

今天在做数据结构排序实验的时候，使用的快速排序。按理，我印象中快排是很高效的，不过，这次400w的数据，排了2659秒，有点意想不到，让我一度怀疑了算法是否写错了。不过，认

墨蓝/ 2022年09月18日 12:46/ 0 赞/ 207 阅读

相关利用随机化快速排序求带权中位数C++实现

// 利用随机化快速排序求带权中位数.cpp : Defines the entry point for the console application. // //中

╰半橙微兮°/ 2022年06月18日 10:15/ 0 赞/ 132 阅读

相关 C++随机化快速排序

C++随机化快速排序 // 随机化快速排序.cpp : Defines the entry point for the console application. //

Love The Way You Lie/ 2022年06月18日 10:14/ 0 赞/ 184 阅读

相关快速排序C++实现（和随机快速排序）

快速排序思想：存在一乱序数组A\[n\](0~n-1)，第一步：变量le和变量ri,分别保存首数组A\[0\]的下标（即le= 0;）和尾数组A\[

约定不等于承诺〃/ 2022年05月24日 01:39/ 0 赞/ 188 阅读

相关利用随机化快速排序求带权中位数C++实现

// 利用随机化快速排序求带权中位数.cpp : Defines the entry point for the console application. // //中

今天药忘吃喽~/ 2022年05月15日 12:59/ 0 赞/ 172 阅读

相关 C++随机化快速排序

C++随机化快速排序 // 随机化快速排序.cpp : Defines the entry point for the console application. //

小灰灰/ 2022年05月15日 12:57/ 0 赞/ 201 阅读

相关 C++随机化快速排序

C++随机化快速排序 // 随机化快速排序.cpp : Defines the entry point for the console application. //

悠悠/ 2022年05月15日 12:57/ 0 赞/ 177 阅读