各种排序算法

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <conio.h>

#include <iostream.h>

#define N 25000 // 待排序元素的个数

void insertsort(int R[N+1]) // 直接插入排序

{

int i,j;

for (i=2; i<=N; i++) {

R[0]=R[i]; // 设置监视哨

j=i-1;

while (R[0]<R[j]) {

R[j+1]=R[j];

j--;

}

R[j+1]=R[0];

}

}

void shellsort(int R[N+1]) // 希尔排序

{

int i,j,gap;

int x;

gap=N/2; // 设置初始增量

while (gap>0) {

for (i=gap+1; i<=N; i++) {

j=i-gap;

while (j>0)

if(R[j]>R[j+gap]) {

x=R[j];

R[j]=R[j+gap];

R[j+gap]=x;

j=j-gap;

}

else

j=0;

}

gap=gap/2; // 减小增量

}

}

void bubblesort(int R[N+1]) // 起泡排序

{

int i,j,noswap;

int temp;

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

noswap=1;

for (j=N; j>=i+1; j--)

if(R[j]<R[j-1]) {

temp=R[j];

R[j]=R[j-1];

R[j-1]=temp;

noswap=0;

}

if(noswap)

break;

}

}

int partition(int R[N+1],int low,int high) // 快速排序的子函数(取定枢轴元素)

{

int i,j;

i=low;

j=high;

R[0]=R[low]; // 取定枢轴元素

do { // 从表的两端交替地向中间扫描

while ((j>i) && (R[j]>=R[0]))

j--;

if(i<j) {

R[i]=R[j];

i++;

}

while ((i<j) && (R[i]<=R[0]))

i++;

if(i<j) {

R[j]=R[i];

j--;

}

} while (i<j);

R[i]=R[0]; // 枢轴元素到位

return i; // 返回枢轴位置

}

void quicksort(int R[N+1],int low,int high) // 快速排序

{

int i;

if(low<high) {

i=partition(R,low,high); // 将表R一分为二

quicksort(R,low,i-1); // 对低子表递归排序

quicksort(R,i+1,high); // 对高子表递归排序

}

}

void selectsort(int R[N+1]) // 直接选择排序

{

int i,j,k;

int temp;

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

k=i;

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

if(R[j]<R[k])

k=j; // 用k指出每趟在无序区间段的最小元素

if(k!=i) {

temp=R[i];

R[i]=R[k];

R[k]=temp;

}

}

}

void sift(int R[N+1],int s,int m) // 堆排序的子函数(筛选算法,使R[s..m]成为一个大根堆)

{

int i,j;

int temp;

temp=R[s];

i=s;

j=2*i; // R[j]是R[i]的左孩子

while (j<=m) {

if((j<m) && (R[j]<R[j+1]))

j++; // 若右孩子较大,则把j修改为右孩子的下标

if(temp<R[j]) {

R[i]=R[j]; // 将R[j]调到父亲的位置上

i=j;

j=2*i; // 修改i和j的值,以便继续向下筛选

}

else

break; // 筛选完成,终止循环

}

R[i]=temp; // 被筛结点的值放入最终位置

}

void heapsort(int R[N+1]) // 堆排序

{

int i;

int temp;

for (i=N/2; i>=1; i--)

sift(R,i,N); // 建立初始堆

for (i=N; i>=2; i--) { // 进行N-1次循环,完成堆排序

temp=R[1];

R[1]=R[i];

R[i]=temp; // 将第一个元素同当前区间内最后一个元素对换

sift(R,1,i-1); // 筛选R[1]结点,得到(N-1)个结点的堆

}

}

void main()

{

int R[N+1],RR[N+1]; // 待排序的元素组

clock_t start,finish; // 用于函数运行的记时

double duration;

int i;

cout<<"The initial data: "<<endl;

for (i=1; i<=N; i++) {

R[i]=rand()%5001;

RR[i]=R[i];

cout<<R[i]<<" ";

if(i%10==0)

cout<<endl;

}

///////////////////////////////////////////////////////////

getchar(); // 直接插入排序

start = clock(); // 记时开始

insertsort(RR);

finish = clock(); // 记时结束

duration = (double)(finish-start) / CLOCKS_PER_SEC;

cout<<"The result based on the insert sort is :"<<endl;

for (i=1; i<=N; i++) {

cout<<RR[i]<<" ";

if(i%10==0)

cout<<endl;

}

cout<<"The Run Time is: "<<duration<<" seconds"<<endl;

///////////////////////////////////////////////////////////

getchar(); // 希尔排序

for (i=1; i<=N; i++) {

RR[i]=R[i];

}

start = clock(); // 记时开始

shellsort(RR);

finish = clock(); // 记时结束

duration = (double)(finish-start) / CLOCKS_PER_SEC;

cout<<"The result based on the shell sort is :"<<endl;

for (i=1; i<=N; i++) {

cout<<RR[i]<<" ";

if(i%10==0)

cout<<endl;

}

cout<<"The Run Time is: "<<duration<<" seconds"<<endl;

///////////////////////////////////////////////////////////

getchar(); // 起泡排序

for (i=1; i<=N; i++) {

RR[i]=R[i];

}

start = clock(); // 记时开始

bubblesort(RR);

finish = clock(); // 记时结束

duration = (double)(finish-start) / CLOCKS_PER_SEC;

cout<<"The result based on the shell sort is :"<<endl;

for (i=1; i<=N; i++) {

cout<<RR[i]<<" ";

if(i%10==0)

cout<<endl;

}

cout<<"The Run Time is: "<<duration<<" seconds"<<endl;

///////////////////////////////////////////////////////////

getchar(); // 快速排序

for (i=1; i<=N; i++) {

RR[i]=R[i];

}

start = clock(); // 记时开始

quicksort(RR,1,N);

finish = clock(); // 记时结束

duration = (double)(finish-start) / CLOCKS_PER_SEC;

cout<<"The result based on the shell sort is :"<<endl;

for (i=1; i<=N; i++) {

cout<<RR[i]<<" ";

if(i%10==0)

cout<<endl;

}

cout<<"The Run Time is: "<<duration<<" seconds"<<endl;

///////////////////////////////////////////////////////////

getchar(); // 直接选择排序

for (i=1; i<=N; i++) {

RR[i]=R[i];

}

start = clock(); // 记时开始

selectsort(RR);

finish = clock(); // 记时结束

duration = (double)(finish-start) / CLOCKS_PER_SEC;

cout<<"The result based on the shell sort is :"<<endl;

for (i=1; i<=N; i++) {

cout<<RR[i]<<" ";

if(i%10==0)

cout<<endl;

}

cout<<"The Run Time is: "<<duration<<" seconds"<<endl;

///////////////////////////////////////////////////////////

getchar(); // 堆排序

for (i=1; i<=N; i++) {

RR[i]=R[i];

}

start = clock(); // 记时开始

heapsort(RR);

finish = clock(); // 记时结束

duration = (double)(finish-start) / CLOCKS_PER_SEC;

cout<<"The result based on the shell sort is :"<<endl;

for (i=1; i<=N; i++) {

cout<<RR[i]<<" ";

if(i%10==0)

cout<<endl;

}

cout<<"The Run Time is: "<<duration<<" seconds"<<endl;

///////////////////////////////////////////////////////////

}

/*冒泡法排序*/

for(i=0; i<NUM-1; i++) /*外循环:控制比较趟数*/

for(j=NUM-1; j>i; j--) /*内循环:进行每趟比较*/

if(data[j]<data[j-1]) /*如果data[j]大于data[j-1],交换两者的位置*/

{temp=data[j];

data[j]=data[j-1];

data[j-1]=temp;

};

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航