「ソートの挿入」--ソートの直接挿入

「ソートの挿入」--直接ソート
基本的な考え方:最初から順番に並べられているのは1つの要素だけで、並べ替えられる要素には残りのすべての要素が含まれています.ソートする要素を取り出し、順序付けされたシーケンスに挿入する操作を繰り返します.ソートする要素が挿入されるまで.
挿入方法:挿入する要素を順序付けされたシーケンスと比較し、挿入する要素がソートする次の要素より小さい(より大きい)まで前(後)にシフトします.
C++コード実装:

#include<iostream>
#include<time.h>
using namespace std;

template<class Type> struct ElementType
{
	Type key;
};
template<class Type> struct SqList
{
	ElementType<Type>* elem;
	int length;//      
	int listsize;//   
};

template<class Type> void insertSort(SqList<Type>& List)
{
	//      
	for (int i = 2; i < List.length; i++)
	{
		//        ，        
		if (List.elem[i].key < List.elem[i-1].key)
		{
			List.elem[0] = List.elem[i];
			//      ，     
			int j = i - 1;
			for (; List.elem[0].key < List.elem[j].key; j--)
				List.elem[j + 1] = List.elem[j];
			List.elem[j + 1] = List.elem[0];
		}
	}
}
void main()
{
	SqList<int> List;
	List.length = 0;
	List.listsize = 20;
	List.elem = new ElementType<int>[List.listsize];
	//        
	for (int i = 1; i < 10; i++)
	{
		srand(time(0)+i*10000);
		List.elem[i].key = rand() % 50;
		List.length++;
	}

	for (int i = 1; i < List.length; i++)
		cout << List.elem[i].key << ' ';
	cout << endl;
	//    
	insertSort(List);
	cout << "Sorted: " << endl;
	for (int i = 1; i < List.length; i++)
		cout << List.elem[i].key << ' ';
	cout << endl;
	system("pause");
}