比较冒泡排序、插入排序、二分插入排序、选择排序、快速排序的运行时间。

比较冒泡排序、插入排序、二分插入排序、选择排序、快速排序的运行时间。

#include 
#include 
#include 

#define N 20000  //随机生成20000个测试数据

#define MAXSIZE 100000  //用于要排序数组个数最大值
typedef struct
{
int r[MAXSIZE+1]; //用于存储要排序数组，r[0]用作哨兵或临时变量
int length; //用于记录顺序表的长度
}SqList;

//交换L中数组r的下标为i和j的值
void swap(SqList *L,int i,int j)
{
int temp=L->r[i];
L->r[i]=L->r[j];
L->r[j]=temp;
}

//冒泡排序
void BubbleSort(SqList *L)
{
int i,j;
for(i=1 ; i < L->length ; i++)
{
for(j=L->length-1 ; j>=i ; j--)  //注意j是从后往前循环
{
if(L->r[j] > L->r[j+1])  //若前者大于后者
{
 swap(L,j,j+1);   //交换L->r[j]与L->r[j+1]的值
}
}
}
}

//选择排序
void SelectSort(SqList *L)
{
int i,j,min;

for(i=1 ; ilength ; i++)
{
min = i;
for (j = i+1;j <= L->length;j++)
        {
if (L->r[min] > L->r[j]) //如果有小于当前最小值的关键字
            {
                min = j;             //将此关键字的下标赋值给min
            }
        }
if(i!=min)  //若min不等于i，说明找到最小值，交换
        {
            swap(L,i,min);
        }
}
}

//直接插入排序
void InsertSort(SqList *L)
{
int i,j;
for(i=2 ; i <= L->length ; i++)
{
if (L->r[i] < L->r[i-1])
{
L->r[0] = L->r[i]; //设置哨兵
for(j=i-1 ; L->r[j] > L->r[0] ; j--)
            {
                L->r[j+1] = L->r[j]; //记录后移
            }
L->r[j+1] = L->r[0]; //插入到正确位置
}
}
}
//二分插入排序
void InsertSortTwo(SqList *L)
{
    int low,high,mid;
    int i,j;
    int n=L->length;
    for(i=2;  i<=n; i++)
    {
        L->r[0]=L->r[i];
        low=1;
        high=i-1;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(L->r[mid]>L->r[0])
            {
                high=mid-1;
            }
            else
            {
                low=mid+1;
            }
        }
        for(j=i-1 ; j>=high+1 ; j--)
        {
            L->r[j+1]=L->r[j];
        }
        L->r[high+1]=L->r[0];
    }
}

//交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置
//此时在它之前(后)的记录均不大(小)于它
int Partition(SqList *L,int low,int high)
{
int pivotkey;

pivotkey=L->r[low]; //用子表的第一个记录作枢轴记录
while(low {
 while(lowr[high]>=pivotkey)
         {
             high--;
         }
 swap(L,low,high); //将比枢轴记录小的记录交换到低端
 while(lowr[low]<=pivotkey)
         {
             low++;
         }
 swap(L,low,high); //将比枢轴记录大的记录交换到高端
}
return low;  //返回枢轴所在位置
}

//对顺序表L中的子序列L->r[low..high]作快速排序
void QSort(SqList *L,int low,int high)
{
int pivot;
if(low {
pivot=Partition(L,low,high); //将L->r[low..high]一分为二，算出枢轴值pivot
QSort(L,low,pivot-1); //对低子表递归排序
QSort(L,pivot+1,high); //对高子表递归排序
}
}

//对顺序表L作快速排序
void QuickSort(SqList *L)
{
QSort(L,1,L->length);
}

int data[N];
SqList L1,L2,L3,L4,L5;

int main()
{
   int i;

    clock_t start_time,end_time;
    int work_time;

   srand((int)time(0));
   for(i=0;i   {
       data[i]=rand() % N; //随机数
   }

   for(i=0;i   {
      L1.r[i+1]=data[i];
   }
   L1.length=N;
   L2=L3=L4=L5=L1;

   printf("随机生成 %d 个测试数据
",N);

   start_time = clock();//获取程序开始运算时间
   printf("冒泡排序     ");
   BubbleSort(&L1);
   end_time = clock();//获取程序结束运算时间
   work_time = end_time - start_time;//计算程序运算时间
   printf("运行时间 %d 毫秒 
",work_time);

   start_time = clock();//获取程序开始运算时间
   printf("直接插入排序 ");
   InsertSort(&L2);
   end_time = clock();//获取程序结束运算时间
   work_time = end_time - start_time;//计算程序运算时间
   printf("运行时间 %d 毫秒 
",work_time);

   start_time = clock();//获取程序开始运算时间
   printf("二分插入排序 ");
   InsertSortTwo(&L3);
   end_time = clock();//获取程序结束运算时间
   work_time = end_time - start_time;//计算程序运算时间
   printf("运行时间 %d 毫秒 
",work_time);

   start_time = clock();//获取程序开始运算时间
   printf("选择排序     ");
   SelectSort(&L4);
   end_time = clock();//获取程序结束运算时间
   work_time = end_time - start_time;//计算程序运算时间
   printf("运行时间 %d 毫秒 
",work_time);

   start_time = clock();//获取程序开始运算时间
   printf("快速排序     ");
   QuickSort(&L5);
   end_time = clock();//获取程序结束运算时间
   work_time = end_time - start_time;//计算程序运算时间
   printf("运行时间 %d 毫秒 
",work_time);

   return 0;
}

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息