八种内部排序算法时间性能分析

这是大二时候自己的课程设计，内部排序算法主要有八种，下面通过每种排序算法的比较次数和移动次数来分析每种排序方法的性能。

# include <iostream>
# include <fstream>
# include <iomanip>
# include <string>
using namespace std;

typedef struct//定义顺序表
{
    int elem[100];
    int length;
}SqList;

void copy(SqList &p, SqList &q)//复制p至q
{
    q.length=p.length;
    for(int i=1; i<=p.length; i++)
        q.elem[i]=p.elem[i];
}

int com=0,mov=0;//比较及移动次数初始化
ifstream in("in.txt");//关联文件

void CreateSqList(SqList &q)//读取文件数据
{
    in>>q.length;
    for(int i=1;i<=q.length;i++)
        in>>q.elem[i];
}

void SqSort(SqList &q);//函数声明部分
void Halfsort(SqList &q);
void Shellsort(SqList &q,int dlta[],int t);
void bubble(SqList &q);
void Qsort(SqList &q,int low,int high);
void QuickSort(SqList &q);
int  SelectMin(SqList &q,int i);
void Select(SqList &q);
void MergeSort(SqList &q);
void HeapSort(SqList &q);
void output(SqList q);

int main()//主函数
{
    SqList p,q;
    int dlta[3]={5,3,1},t=3;//希尔函数增量数组
    string mess[4]={"","随机","逆序","正序"};
    int count=3;

while(count)//count不为0时执行
    {
        CreateSqList(p);
        cout<<"["<<mess[count]<<"]"<<endl;
        cout<<"元 素 为 :";
        output(p);
        cout<<"-------------------------------------------|"<<endl;
        cout<<"        |   比 较次数    |    移 动次数    | "<<endl;
        cout<<"--------|----------------------------------|"<<endl;
        copy(p,q);//将p中元素的值赋给q
        SqSort(q);
        cout<<"直插排序|"<<setw(12)<<com<<setw(20)<<mov<<endl;
        cout<<"--------|----------------------------------|"<<endl;
        copy(p,q);
        Halfsort(q);
        cout<<"折半排序|"<<setw(12)<<com<<setw(20)<<mov<<endl;
        cout<<"--------|----------------------------------|"<<endl;
        copy(p,q);
        Shellsort(q,dlta,t);
        cout<<"希尔排序|"<<setw(12)<<com<<setw(20)<<mov<<endl;
        cout<<"--------|----------------------------------|"<<endl;
        copy(p,q);
        bubble(q);
        cout<<"冒泡排序|"<<setw(12)<<com<<setw(20)<<mov<<endl;
        cout<<"--------|----------------------------------|"<<endl;
        copy(p,q);
        QuickSort(q);
        cout<<"快速排序|"<<setw(12)<<com<<setw(20)<<mov<<endl;
        cout<<"--------|----------------------------------|"<<endl;
        copy(p,q);
        Select(q);
        cout<<"选择排序|"<<setw(12)<<com<<setw(20)<<mov<<endl;
        cout<<"--------|----------------------------------|"<<endl;
        copy(p,q);
        HeapSort(q);
        cout<<"堆排序  |"<<setw(12)<<com<<setw(20)<<mov<<endl;
        cout<<"--------|----------------------------------|"<<endl;
        copy(p,q);
        MergeSort(q);
        cout<<"归并排序|"<<setw(12)<<com<<setw(20)<<mov<<endl;
        cout<<"--------|----------------------------------|"<<endl;
        cout<<endl;
        count--;
    }
    return 0;

}

void SqSort(SqList &q)//直接插入排序
{
    int j=0;
    for(int i=2;i<=q.length;i++)
    {
        com++;
        if(q.elem[i]<q.elem[i-1])//“<”,需将q.elem[i]插入有序子表
        {
            q.elem[0]=q.elem[i];//复制为哨兵
            q.elem[i]=q.elem[i-1];
            for(j=i-2;q.elem[0]<q.elem[j];--j)
            {
                q.elem[j+1]=q.elem[j]; //记录后移
                mov++;
                com++;
            }
            q.elem[j+1]=q.elem[0];//插入到正确位置
            mov+=3;
        }
    }
}

void Halfsort(SqList &q)//折半排序
{
    com=0;mov=0;//执行每个排序算法前mov,com需清零
    for(int i=2;i<=q.length;++i)
    {
        q.elem[0]=q.elem[i];
        mov++;
        int low=1,high=i-1,m=0;
        while(low<=high)//小于时一直循环
        {
            com++;
            m=(low+high)/2;//取中值
            if(q.elem[0]<q.elem[m])
                high=m-1;//在低半区查找
            else low=m+1;//在高半区查找
        }
        for(int j=i-1;j>=high+1;--j)
        {
            q.elem[j+1]=q.elem[j];mov++;//后移
        }
        q.elem[high+1]=q.elem[0];
        mov++;
    }
}

void Shellinsert(SqList &q,int dk )//对顺序表L做一趟希尔插入排序，q.elem[0]做暂存单元，当j<=0时插入位置找到
{
    int j;
    for(int i=dk+1;i<=q.length;i++)
    {
        com++;
        if(q.elem[i]<q.elem[i-dk])//需将q.elem[i]插入到有序增量子表
        {
            q.elem[0]=q.elem[i];//暂存在q.elem[0]
            mov++;
            for( j=i-dk;j>0&&(q.elem[0]<q.elem[j]);j-=dk)
            {
                q.elem[j+dk]=q.elem[j];//记录后移，查找插入位置
                mov++;
                com++;
            }
            q.elem[j+dk]=q.elem[0];//插入
            mov++;
        }
    }
}

void Shellsort(SqList &q,int dlta[],int t)//按增量序列dlta[0...t-1]对顺序表q做希尔排序
{
    int k;
    com=0;mov=0;
    for(k=0;k<t;k++)
        Shellinsert(q,dlta[k]);//一趟增量为dlta[k]的插入排序
}

void bubble(SqList &q)//冒泡排序
{
    int t=0,i=0,j=0;
    com=0;mov=0;
    for(i=1;i<=q.length-1;i++)
    {
        for(j=1;j<=q.length-i;j++)
        {
            com++;
            if(q.elem[j]>q.elem[j+1])
            {t=q.elem[j];q.elem[j]=q.elem[j+1];q.elem[j+1]=t;mov++;}//交换
        }
    }
}

int QsortPartion(SqList &q,int low,int high)//快速排序子函数
{
    int key=0;
    key=q.elem[low];//枢轴记录关键字
    mov++;
    while(low<high)//从表的两端交替地向中间扫描
    {
        com+=2;
        while(low<high&&q.elem[high]>=key) --high;
        q.elem[low]=q.elem[high];//将比枢轴记录小的记录移动到低端
        mov++;
        while(low<high&&q.elem[low]<=key) ++low;
        q.elem[high]=q.elem[low];//将比枢轴记录大的记录移动到高端
        mov++;
    }
    q.elem[low]=key;//枢轴记录到位
    mov++;
    return low;//返回枢轴位置
}

void Qsort(SqList &q,int low,int high)//对顺序表中的子序列q.elem[low...high]做快速排序
{
    int pivot=0;
    if(low<high)//长度大于1
    {
        pivot=QsortPartion(q,low,high);//将q.elem[low...high]一分为二
        Qsort(q,low,pivot-1);//对低子表递归排序，pivot是枢轴位置
        Qsort(q,pivot+1,high);//对高子表递归排序
    }
}

void QuickSort(SqList &q)//快速排序
{
    Qsort(q,1,q.length);
}

void Select(SqList &q)//选择排序
{
    int i=0,j=0,t=0;
    com=0;mov=0;
    for(i=1;i<=q.length;i++)//选择第i小的记录，并交换到位
    {
        j=SelectMin(q,i);//在q.elem[i....q.lengh]中选择key最小的记录
        if(i!=j)//与第i个记录交换
        {mov++; t=q.elem[i];q.elem[i]=q.elem[j];q.elem[j]=t;}
    }
}

int SelectMin(SqList &q,int i)//选取最小
{
    int j=1,k=1;
    for(j=i;j<=q.length;j++)
    {com++; if(q.elem[j]<=q.elem[i]) k=j;}
    return k;
}

void HeapAdjust(SqList &q,int s,int m)//建堆函数
{
    int j,rc;
    rc=q.elem[s];
    for(j=2*s;j<=m;j*=2)//沿key较小的孩子结点向下筛选
    {
        com+=2;
        if(j<m&&(q.elem[j]<q.elem[j+1]))	++j; //j为key较小的记录的下标
        if(!(rc<q.elem[j])) break;// 堆调整结束
        q.elem[s]=q.elem[j]; s=j;//较小的孩子结点值换到父结点位置
        mov++;
    }
    q.elem[s]=rc;//rc应插入的位置在s处
    mov++;
}

void HeapSort(SqList &q)//堆排序
{
    int i=1,t=0;
    com=0;mov=0;
    for(i=q.length/2;i>0;i--)
        HeapAdjust(q,i,q.length);

for(i=q.length;i>1;i--)
    {
        mov++;
        {t=q.elem[1];q.elem[1]=q.elem[i];q.elem[i]=t;}
        HeapAdjust(q,1,i-1);
    }
}

void Merge(SqList q,SqList &Mq,int i,int m,int n)//归并排序子函数
{
    int j=1,k=1,t=1;
    for(j=m+1,k=i;i<=m&&j<=n;++k)//将q中的记录由小到大并入Mq
    {
        if(q.elem[i]<q.elem[j])
            Mq.elem[k]=q.elem[i++];
        else
            Mq.elem[k]=q.elem[j++];
        mov++; com++;
    }
    if(i<=m)
        for(t=i;t<=m;t++,k++)//将剩余的q.elem[i..m]复制到Mq
        {
            Mq.elem[k]=q.elem[t];
            mov++;
        }
    if(j<=n)
        for(t=j;t<=n;t++,k++)//将剩余的q.elem[j..n]复制到Mq
        {
                Mq.elem[k]=q.elem[t];
                mov++;
        }
}

void Msort(SqList q,SqList &Mq,int s,int t)//将q[s..t]归并为Mq[s..t]
{

int m;
    SqList temp;
    if(s==t)
    {
        Mq.elem[s]=q.elem[s];
        mov++;
    }
    else
    {
        m=(s+t)/2;//将q[s..t]平分为q[s..m]和q[m+1..t]
        Msort(q,temp,s,m);//递归的将q[s..m]归并为有序的temp[s..m]
        Msort(q,temp,m+1,t);//递归的将q[m+1..t]归并为有序的temp[m+1..t]
        Merge(temp,Mq,s,m,t);
    }
}

void MergeSort(SqList &q)//归并排序
{
    mov=0;com=0;
    Msort(q,q,1,q.length);
}

void output(SqList q)//输出函数
{
    for(int i=1;i<=q.length;i++)
        cout<<q.elem[i]<<" ";
    cout<<endl;
}

C#版冒泡：

 int[] a = {1,4,2,0,9,6,12,3};
            int i = 0, j = 0, t = 0;
            for (i = 0; i < a.Length - 1; i++)
            {
                for (j = 0; j < a.Length -1- i; j++)
                {
                    if (a[j] > a[j + 1])
                    {
                        t = a[j+1];
                        a[j + 1] = a[j];
                        a[j] = t;
                    }
                }
            }
            for (i = 0; i <= a.Length -1; i++)
            {
                Console.WriteLine(a[i]);
            }

秒客网

八种内部排序算法时间性能分析

相关文章