每日一练--直接插入排序

现在找工作的压力这么大，为了以后好找工作，现在开始要多看看算法，所以以后可以每天做个小题目，练习一下。今天作为第一天，说个最简单的直接插入排序。
直接插入排序可以这么理解，把A[j]和A[0]….A[j-1]的数进行比较，如果比他们小，就插入到比它小的前一位，直接插入排序的时间复杂度是O(n^2).
先给出伪代码分析

//the index of array is from 0
for j=1 to num.length
    key = num[j];
    i = j-1;
    while i >= 0 and num[i] > key
    {
        num[i+1] = num[i];
        i--;
    }
    num[i+1] = key;

下面用c++来实现

// insertsort.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
#include<stdlib.h>
using namespace std;

int main()
{
    int num[10] = {10,20,1,78,34,99,12,21,2,55};
    int key;
    cout << "the number has not been sorted:" << endl;
    for (int i = 0;i < 10;i++)
    {
        cout << num[i] << ' ';
    }
    cout << endl;
    cout << "the number has been sorted:" << endl;
    for (int j =1;j <10;j++)
    {
        int key = num[j];
        int i = j-1;
        while(i >=0&&num[i]>key)
        {
            num[i+1] = num[i];
            i--;
        }
        num[i+1] = key;
    }

    for (int m = 0;m < 10;m++)
    {
        cout << num[m] << ' ';
    }
    cout << endl;
    return 0;
}

今天一练，到此结束。

每日一练--直接插入排序

推荐阅读