1. 问题描述
输入:n个数的序列<a1,a2,a3,...,an>。
输出:原序列的一个重排<a1*,a2*,a3*,...,an*>;,使得a1*<=a2*<=a3*<=...<=an*。
2.问题分析
(1)从有序数列和无序数列{a2,a3,…,an}开始进行排序;
(2)处理第i个元素时(i=2,3,…,n),数列{a1,a2,…,ai-1}是已有序的,而数列{ai,ai+1,…,an}是无序的。用ai与ai-1,a i-2,…,a1进行比较,找出合适的位置将ai插入;
(3)重复第二步,共进行n-i次插入处理,数列全部有序。
3. 算法实现
template <typename T> void InsertSort( CVector<T> &vec ) { for ( size_t i=1; i<vec.GetSize(); i++ ) { T temp = vec[i]; int j = i-1; while ( j >= 0 && vec[j] > temp ) { vec[j+1] = vec[j]; j--; } vec[j+1] = temp; } }
测试:
#define DATA_MAGNITUDE 1000 double random(double start, double end) { return start+(end-start)*rand()/(RAND_MAX + 1.0); } //----------------------------------------------------------- srand( unsigned(time(0))); for ( int i=0; i<DATA_MAGNITUDE; i++ ) { vec2.PushBack( random(1, DATA_MAGNITUDE) ); } int size = 20>DATA_MAGNITUDE? 20 : DATA_MAGNITUDE; InsertSort<int>( vec2 ); for ( size_t i =0; i < size; i++ ) { cout<<vec2[i]<<" "; } cout<<endl;
4. 算法分析
comp | move | |
best | n-1 | 0 |
worst | n(n-1)/2 = o(n^2) | n(n-1)/2 = o(n^2) |
avg | n(n-1)/4 = o(n^2) | n(n-1)/4 = o(n^2) |