<< Introduction to algorithms >> ( Second Edition )
2.1 Insertion Sort
We start with insertion sort, which is an efficient algorithm for sorting a small
number of elements. Insertion sor works the way many people sort a hand of
playing cards. We start with an empty left hand and the cards face down a on the
table. We then remove one card at a time from the table and insert it into the
correct position in the left hand. To find the correct position for a card, we compare
it with each of the cards already in the hand, from right to left, as illustrated in
Figure 2.1. At all times, the caess held in the left hand are sorted, and these cards
werer originally the top cards of the pile on the table.
Solution:
// 声明：本代码旨在实现原文的思想
// copyleft 2004 http://blog.csdn.net/mskia
// email: bitrain@hotmail.com
#ifndef Insertion_Sort_by_mskia
#define Insertion_Sort_by_mskia
namespace te {
template< class T >
void insertion_sort( T *first , T *last ) {
for ( T *i = first + 1; i <= last; ++i ) {
T *j = i - 1;
while ( j >= first && *j > *i ) {
T t = *i;
*i = *j;
*j = t;
i = j--;
}
}
return;
}
}
#endif