关于2.2-2题的派生：插入排序与选择排序的时间分析对比

关于2.2-2题的衍生：插入排序与选择排序的时间分析对比

答案索引帖

插入排序时间分析

这里为了方便观察，将for循环变为while循环

//这里只对主要程序段进行时间分析
//假设c是执行时间，n是执行次数
#include <stdio.h>
int main()
{
    int i,j,right_hand;
    int card[10]={1,2,3,4,5,6,7,8,9,10};
    i=0;//c0
    while(i<=9)//c1  n=11
    {
        right_hand=card[i];//c2  n-1
        j=i-1;//c3  n-1
        while(j>=0&&card[j]<right_hand)//c4  1+2+···+n-1
        {
            card[j+1]=card[j];//c5  1+2+···+n-2
            j--;//c6  1+2+···+n-2
        }
        card[j+1]=right_hand;//c7  n-1
        i++;//c8  n-1
    }
    for(i=0;i<10;i++)
        printf("%d ",card[i]);
    return 0;
}

好了，现在我们要进行求和，也就是求总时间。我们先假设最坏情况，我写的那个C语言代码就是最坏情况。
\[ \begin{equation}\begin{split} T(n)&=c0+c1*n+c2*(n-1)+c3*(n-1)\\ &+c4*\sum _{ 1 }^{ n-1 }{ t } +c5*\sum _{ 1 }^{ n-2 }{ t } +c6*\sum _{ 1 }^{ n-2 }{ t } \\&+c7*(n-1)+c8*(n-1)\\ &=c0+c1*n+c2*(n-1)+c3*(n-1)\\ &+c4*\frac { n*(n-1) }{ 2 } +c5*\frac { (n-1)*(n-2) }{ 2 } +c6*\frac { (n-1)*(n-2) }{ 2 }\\& +c7*(n-1)+c8*(n-1)\\ &=(c0-c1-c3+c5+c6-c7-c8)\\ &+(c1+c2+c3-\frac { c4 }{ 2 } -\frac { 3*c5 }{ 2 } -\frac { 3*c6 }{ 2 }\\& +c7+c8)*n +(\frac { { c4 }^{ 2 } }{ 2 } +\frac { { c5 }^{ 2 } }{ 2 } +\frac { { c6 }^{ 2 } }{ 2 } )*{ n }^{ 2 }\\ &=a*{ n }^{ 2 }+b*n+c \end{split}\end{equation} \]
所以结合书上的解释我们很容易得到其效率为：

• best-case: \(\Theta (n)\);
• average-case: \(\Theta ({ n }^{ 2 })\);
• worst-case: \(\Theta ({ n }^{ 2 })\);

选择排序时间分析

#include <stdio.h>
int main()
{
    int A[10]={1,2,3,4,5,6,7,8,9,10};
    int i,j,temp_index,temp;
    i=0;
    while(i<9)
    {
        temp_index=i;
        j=i+1;
        while(j<10)
        {
            if(A[j]>A[temp_index])
                temp_index=j;
            j++;
        }
        temp=A[i];
        A[i]=A[temp_index];
        A[temp_index]=temp;
        i++;
    }
    for(i=0;i<10;i++)
        printf("%d ",A[i]);
    return 0;
}

我们不难发现，在内层循环中，插入排序有可能不会被执行，而选择排序无论如何内层循环都会被执行，所以我们认定在一定的情况下，插入排序的效率会比选择排序的效率高。这里我们同样得出了一个结论：选择排序在所有情况下都是 \(\Theta ({ n }^{ 2 })\)