CentOS 7.0 环境编译thinstation

插入排序

void insertionSort( ElementType A[], int N )
{
    int i, j;
    ElementType tmp;
    for( i = 1; i < N; i++ )
    {
        tmp = A[i];
        for( j = i; j > 0 && A[j-1] > tmp; j-- )
        {
            A[j] = A[j-1];
        }
        A[j] = tmp;   
    }

}

Key Mind:

将下标i读取到的值保存（隐喻腾空i的位置），第二个for循环指针回走检查，只要比与保存的值大就往后移。j最大值为N-1，所以两个for循环总次数为N^2 ，即时间复杂度为O(N^2 )。

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 876208453@qq.com