本文共 1448 字，大约阅读时间需要 4 分钟。

排序思想：

假设目标是从小到大。在一列无序的队伍中，从第一值开始，始终让它左边的值是从小到大排序的，其右边的值暂时不变，直到最后一个值。

比如一共10值，当遍历到第5个值时，要保证前4个值是排序的，而且第5个值遍历完之后要将第5个值插入到前4个值里。直到第10个值。

第一次遍历从第二个值开始，让第一个值和第二个值从小到大。

如下图所示：

代码如下：

// Defines the entry point for the console application.//#include "stdafx.h"#include "windows.h"#include "time.h"const int N = 100000;int O = 0;int* GenRandom(){	srand( (unsigned)time( NULL ) );	int* a = new int[N];	for (int i = 0; i < N; i++)	{		a[i] = rand() * rand();	}	return a;}void swap(int& a, int& b){	int temp = 0;	temp = a;	a = b;	b = temp;}//small -> largevoid InsertSort(int* ua){	O = 0;	//round times	for (int i = 1; i <= N; i++)	{		//printf("round %d \r\n", i);		//for (int i = 0; i < N; i++)		//{		//	printf("a[%d]=%d \r\n",i, *(ua+i));		//}		for (int j = i; j > 0; j--)		{			if( ua[j] < ua[j-1] )			{				swap(ua[j], ua[j-1] );			}			O++;		}	}}SYSTEMTIME StartTime = {0};FILETIME StartFileTime = {0};SYSTEMTIME EndTime= {0};FILETIME SEndFileTime= {0};int _tmain(int argc, _TCHAR* argv[]){        int* a = GenRandom(); 	///InsertSort	GetSystemTime(&StartTime);	printf("timeBefore %d:%d:%d \r\n", StartTime.wMinute, StartTime.wSecond, StartTime.wMilliseconds);	printf("InsertSort \r\n");	InsertSort(a);	GetSystemTime(&EndTime);	printf("timeAfter %d:%d:%d \r\n", EndTime.wMinute, EndTime.wSecond, EndTime.wMilliseconds);	printf("times %d \r\n", O);	return 0;}

转载地址：http://fmlgb.baihongyu.com/