内部排序演示C++ 第3页

内部排序演示C++ 第3页
#include <stdio.h>
#define N 100//定义数组最大为100
const int t=3;//定义希尔排序次数
int d[t]={4,3,1};//定义希尔排序比较量
int qmt;//快速排序的移动次数
int qct;//快速排序的比较次数

void output(int n,int a[],int ct,int mt)//内部排序中调用的输出函数
{
       int i;
       printf("\n排序结果:");
       for( i=0;i<n;i++)
              printf("%d ",a[i]);//输出各排序完成的数组
       printf("\n比较次数:%d\n",ct);//输出各排序比较次数
       printf("移动次数:%d\n\n",mt);//输出各排序移动次数
}

void bubble_sort(int n,int A[])//冒泡排序
{
       int mt=0;//移动次数mt=movetime
       int ct=0;//比较次数ct=cmdtime
       int i,j,temp;
       int a[N];
       for(i=0;i<n;i++)
              a[i]=A[i];//使数组a[]与数组A[]完全相同,对数组a[]进行操作(不改动A[],可以使A[]被其他函数调用)
       for(i=0;i<n-1;i++)
       {
              for(j=0;j<n-1-i;j++,ct++)
              {
                     if(a[j+1]<a[j])//前后比较
                            temp=a[j],
                            a[j]=a[j+1],
                            a[j+1]=temp,
                            mt+=3;//关键字交换计为3次移动
              }    
       }
       printf("冒泡排序");
       output(n,a,ct,mt);
}

void selection_sort(int n,int A[])//选择排序
{
       int mt=0;//移动次数movetime
       int ct=0;//比较次数cmdtime
       int i,j,temp,k;
       int a[N];
       for(i=0;i<n;i++)
              a[i]=A[i];//使数组a[]与数组A[]完全相同,对数组a[]进行操作(不改动A[],可以使A[]被其他函数调用)
       for(i=0;i<n-1;i++)
       {
              k=i;
              for(j=i+1;j<n;j++,ct++)
                     if(a[k]>a[j])
                            k=j;
                     temp=a[i],
                     a[i]=a[k],
                     a[k]=temp,
                     mt+=3;//关键字交换计为3次移动                 
       }
       printf("选择排序");
       output(n,a,ct,mt);
}

void quick(int a[],int low,int up)//快速排序递归算法
{
       int i,j,temp;
       if(low<up)
       {
              i=low;
              j=up;
              temp=a[low],
              qmt++;
              while(i!=j)
              {
                     qct++;
                     while(i<j&&a[j]>temp)
                            j--,
                            qct++;
                     if(i<j)
                            a[i++]=a[j],
                            qct++;
                            qmt++;
                     while(i<j&&a[i]<=temp)
                            i++,
                            qct++;
                     if(i<j)
                            a[j--]=a[i],
                            qct++,
                            qmt++;
              }
              a[i]=temp,
              qmt++;
              quick(a,low,j-1);
              quick(a,i+1,up);
       }
}

void quick_sort(int n,int A[])//快速排序(通过调用快速排序递归算法完成)
{
       int i;
       int a[N];
       for(i=0;i<n;i++)
              a[i]=A[i];//使数组a[]与数组A[]完全相同,对数组a[]进行操作(不改动A[],可以使A[]被其他函数调用)
       quick(a,0,n-1);//调用快速排序递归算法
       printf("快速排序");
       output(n,a,qct,qmt);
}

void insertion_sort(int n,int A[])//插入排序
{
       int mt=0;//移动次数movetime
       int ct=0;//比较次数cmdtime
       int i,j,temp;
       int a[N];
       for(i=0;i<n;i++)
              a[i]=A[i];//使数组a[]与数组A[]完全相同,对数组a[]进行操作(不改动A[],可以使A[]被其他函数调用)
       for(i=1;i<n;i++)
       {
              temp=a[i],
              mt++;
              for(j=i-1;j>=0&&temp<a[j];j--,ct++)
                     a[j+1]=a[j],
                     mt++;
              a[j+1]=temp,
              mt++;
       }
       printf("插入排序");
       output(n,a,ct,mt);
}

void shell_sort(int n,int A[])//希尔排序
{
       int mt=0;//移动次数movetime
       int ct=0;//比较次数cmdtime
       int i,j,k,h,y;
       int a[N];
       for(i=0;i<n;i++)
              a[i]=A[i];//使数组a[]与数组A[]完全相同,对数组a[]进行操作(不改动A[],可以使A[]被其他函数调用)
       for(i=0;i<t;i++)
       {
              h=d[i];
              for(j=h;j<n;j++)
              {
                     y=a[j],
                     mt++;
                     for(k=j-h,ct++,mt++;k>=0&&y<a[k];k-=h)
                            a[k+h]=a[k];
                     a[k+h]=y;
              }
       }
       printf("希尔排序");
       output(n,a,ct,mt);
}

void main()
{
       int n;
       int i;
       int A[N];
       printf("\t*******************************************************\n");
    printf("\t******************内部排序时间复杂度比较***************\n");
    printf("\t*******************************************************\n");
    printf("请输入数组大小(小于100):");
       scanf("%d",&n);//输入所需排序数组大小
       for(i=0;i<n;i++)
       {
              printf("请输入数组a[%d]:",i);
              scanf("%d",&A[i]);//依次输入数组A[0]~A[n]
       }
       bubble_sort(n,A);//冒泡排序
       insertion_sort(n,A);//插入排序
       selection_sort(n,A);//选择排序
       quick_sort(n,A);//快速排序
       shell_sort(n,A);//希尔排序
} 710

上一页  [1] [2] [3] 

Copyright © 2007-2012 www.chuibin.com 六维论文网 版权所有