注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

慵懒的乌龟

——若有,且珍惜~

 
 
 

日志

 
 

几种排序法比较[转]  

2011-04-06 11:41:06|  分类: C/C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

转自:http://blog.csdn.net/mishal/archive/2009/10/17/4689700.aspx

一、程序设计的基本思路:

?冒泡排序算法:起泡排序就是把小的元素往前调或者把大的元素往后调。比较的是相邻的两个元素的大小,交换也发生在这两个相邻元素之间。

?选择排序算法:选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。

?插入排序算法:插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。

?归并排序算法:归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。

?快速排序算法:快速排序算法是选择中枢元素,通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比中枢元素小,另外一部分的所有数据都比中枢元素大,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

二、程序清单:

/*******************************************************************/

/******************通过改变全局变量N,控制产生的数据个数***********/

/*******************************************************************/

#include<iostream>

using namespace std;

#include<time.h>

#include<stdlib.h>

 

#define CLOCKS_PER_SEC 1000

#define N  50000

 

int seconds_begin,seconds_end;                      //全局变量,记录排序时间

double  seconds_sort;

int Data[N+1]={0};                                  //随机数组

 

void Bubble_sort();                                 //起泡排序法函数声明

void Select_sort();                                 //选择排序法函数声明

void Insert_sort();                                 //插入排序法函数声明

void Quick_sort_time(int left,int right);           //快速排序法带计时函数声明

void Quick_sort(int Data[],int left,int right);     //快速排序法函数声明

void Merge_sort_time();                             //归并排序法带计时函数声明

void Merge_sort(int a[],int Len);                   //归并排序法函数声明

 

int main()

{

cout<<"排序算法比较:"<<endl;

    Bubble_sort();

Select_sort();

Insert_sort();

Quick_sort_time(0,N-1);

Merge_sort_time();

 

char delay=getchar();

return 0;

}

 

/**********************************随机数据生*********************************/

 

void rand_data()

{

int i;

srand(int(time(0)));

for(i=0;i<N;i++)

{

Data[i]=rand()%N;

}

Data[N]='\0';

}

 

/**************************************起泡排序法****************************/

 

void Bubble_sort()

{

int i,j,temp;

rand_data();

seconds_begin=clock();                          //保存排序开始时间

for(i=0;i<N-1;i++)                              //相邻元素比较,较大的置后

for(j=0;j<N-1-i;j++)

if(Data[j]>Data[j+1])

{

temp=Data[j];

Data[j]=Data[j+1];

    Data[j+1]=temp;

}

seconds_end=clock();                          //保存排序结束时间

seconds_sort=(double)(seconds_end-seconds_begin)/CLOCKS_PER_SEC;                       

            cout<<"起泡排序法对"<<N<<"个随机整数排序时间为"<<seconds_sort<<"秒"<<endl<<endl;

 

}

 

/*******************************直接选择排序法********************************/

 

void Select_sort()

{

int i,j,flag,temp_min;

seconds_begin=clock();                                  //保存排序开始时间

rand_data();

for(i=0;i<N-1;i++)

{

flag=i;                                         //相对较小元素的下标

for(j=i+1;j<N;j++)                              //找出最小元素,记录下标flag

if(Data[j]<Data[flag])

flag=j;

if(i!=flag)                                            

temp_min=Data[flag];

Data[flag]=Data[i];

Data[i]=temp_min;

}

}

seconds_end=clock();                          //保存排序结束时间

seconds_sort=(double)(seconds_end-seconds_begin)/CLOCKS_PER_SEC;     

            cout<<"选择排序法对"<<N<<"个随机整数排序时间为"<<seconds_sort<<"秒"<<endl<<endl;

}

 

/********************************直接插入排序法*******************************/

 

void Insert_sort()

{

int i,j,temp;

seconds_begin=clock();                               //保存排序开始时间

rand_data();

for(i=1;i<N;i++)                                     //将第i个元素插入已排好序的序列

{

if(Data[i]>=Data[i-1])

{}                                 

else

{

temp=Data[i];                                //保存要插入的值

for(j=i-1;j>=-1;j--)               //将第i个元素与从第i-1个元素开始向前一次比较

{

if(j>=0)

{            

           if(Data[j]>temp)                                     

   {

             Data[j+1]=Data[j];

   }

             else

{

         Data[j+1]=temp;                         

         break;

}

}

else

Data[0]=temp;

}

}

}

 

seconds_end=clock();                         //保存排序结束时间

seconds_sort=(double)(seconds_end-seconds_begin)/CLOCKS_PER_SEC;     

            cout<<"插入排序法对"<<N<<"个随机整数排序时间为"<<seconds_sort<<"秒"<<endl<<endl;

}

 

/*******************************快速排序法************************************/

 

void Quick_sort_time(int left,int right)

{

rand_data();

seconds_begin=clock();                             //保存排序开始时间

 

    Quick_sort(Data,left,right);

 

    seconds_end=clock();                                 //保存排序结束时间

seconds_sort=(double)(seconds_end-seconds_begin)/CLOCKS_PER_SEC;     

    cout<<"快速排序法对"<<right+1<<"个随机整数排序时间为"<<seconds_sort<<"秒"<<endl<<endl;

}

 

void Quick_sort(int Data[],int left,int right)

{

int i=left;

int j=right;

int middle=Data[i];                           //记录枢轴数值

while(i<j)

{

while (i<j&&middle<=Data[j])

{

j--;

}

Data[i]=Data[j];

while (i<j&&middle>=Data[i])

{

i++;

}

Data[j]=Data[i];

}

Data[i]=middle;

if (i>left)

{

Quick_sort(Data,left,i-1);                 //递归查找

}

if(i<right)

{

Quick_sort(Data,i+1,right);                //递归查找

}

}

 

 

/********************************归并排序法**********************************/

 

//有序子段合并

void num_merge(int *des,int *p,int *q,int pcount,int qcount)

{

int i=0;

int j=0;

for(int k=0;k<pcount+qcount;++k)

{

if(i<pcount&&j<qcount&&p[i]<=q[j])

{

des[k]=p[i];

i++;

}

else 

if(i<pcount&&j<qcount&&p[i]>q[j])

{

des[k]=q[j];

j++;

}

else if(i>=pcount)

{

des[k]=q[j];

j++;

}

else 

if(j>=qcount)

{

des[k]=p[i];

i++;

}

}

}

//有Len个元素的Data数组进行归并排序

void Merge_sort_time()

{

rand_data();

seconds_begin=clock();                                                        

Merge_sort(Data,N);

 

seconds_end=clock();  

seconds_sort=(double)(seconds_end-seconds_begin)/CLOCKS_PER_SEC;               

cout<<"归并排序法对"<<N<<"个随机整数排序时间为"<<seconds_sort<<"秒"<<endl<<endl;

}

void Merge_sort(int Data[],int Len)

{

if(Len>1)

{

int *p = new int[Len/2];

int *q = new int[Len-Len/2];

for(int i=0;i<Len/2;++i)

{

p[i]=Data[i];

}

for(int j=Len/2;j<Len;++j)

{

q[j-Len/2]=Data[j];

}

Merge_sort(p,Len/2);

Merge_sort(q,Len-Len/2);

num_merge(Data,p,q,Len/2,Len-Len/2);

}

}

  评论这张
 
阅读(577)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017