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

现在找工作的压力这么大，为了以后好找工作，现在开始要多看看算法，所以以后可以每天做个小题目，练习一下。今天作为第一天，说个最简单的直接插入排序。 直接插入排序可以这么理解，把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;
}

今天一练，到此结束。