+

c++快速排序法

 


///  E-mail:[e-mail]

//快速排序法

//基本的思想:通过一趟排序将待排的记录分割成独立的两部分，
//其中前一部分的 记录的关键字均比另一部分记录的关键字小，
//再分别对两组记录进行递归分割，达到排序的目的

//平均时间复杂度为  O(log2(n))

#include "iostream.h"
#include "stdlib.h"

//交换两变量值
void swap(int &a,int &b)
{
 int c;
 c=a;a=b;b=c;
}

//将数组分成两部分，前一部分的值均比后一部分值小
//返回分界点
int Partition(int data[],int low,int high)
{
 int pivokey;
 pivokey=data[low];
 while(low<high)
 {
  while(low<high&&data[high]>=pivokey)
   high--;
  swap(data[low],data[high]);

  while(low<high&&data[low]<=pivokey)
   low++;
  swap(data[low],data[high]);
 }
 return low;
}

//进行的递归的调用，达到排序的目的
void QSort(int data[],int low,int high)
{
 if(low<high)
 {
  int pivokey=Partition(data,low,high);
  QSort(data,low,pivokey-1);
  QSort(data,pivokey+1,high);
 }
}

void main()
{
 int i;
 int mydata[50];
 for(i=0;i<50;i++)
 {
  //每行显示 10 个数据
  if(i%10==0)
   cout<<endl;
  mydata[i]=rand()%100;
  cout<<mydata[i]<<"  ";  
 }

 QSort(mydata,0,49);

 cout<<endl<<endl;
 for(i=0;i<50;i++)
 {
  //每行显示 10 个数据
  if(i%10==0)
   cout<<endl;
  cout<<mydata[i]<<"  ";  
 }
}

 

 

 
 
 
        发表评论  

--------------------------------------------------------------------------------
 
 
相关专题:  

--------------------------------------------------------------------------------
 
 
相关信息: 
 
 

--------------------------------------------------------------------------------
 
 
相关评论: 
 
 
发表人：cycheng   发表人邮件：[e-mail]   发表时间：2004-6-23 17:20:15 
 
 
_________________________________________________________________

求质数如下：

#include<stdio.h>
void main()
{
int a,c,e,f=0;
 &nbs ....详细内容  

--------------------------------------------------------------------------------
 
发表人：zoukun   发表人邮件：[e-mail]   发表时间：2004-9-30 22:43:10 
 
 
p87#4里面的空格好象没有考虑进去哎,而且回车都在一列啊,没有达到效果啊?
不知道我下面稍微该一下可不可以啊?
#include<stdio.h>
void main()
{
int i,j;
for (i=0;i<5;i++)
{
for&nb ....详细内容  

--------------------------------------------------------------------------------
 
发表人：朋友   发表人邮件：[e-mail]   发表时间：2004-10-20 10:47:38 
 
快速排序好复杂，还没有看懂。我觉得还是冒泡法最好编写程序了，不过时间复杂度大了点。  

--------------------------------------------------------------------------------
 
发表人：gg.NO.1   发表人邮件：[e-mail]   发表时间：2004-11-8 21:57:36 
 
 
求质数的程序代码有问题
for (a=1;a<c;a++)
               {
      &n ....详细内容