2006年9月1日

折半插入排序的实现

     摘要: template
void insertion_sort( T * t, const int & size )
{
int key,
i, j,
low, high, mid;

for( i=1; i {
if( t[i] < t[i-1] )
{
low = 0;
high = i-1;
key = t[i];
while( low <= high )
{
mid = (low+high)/2;

if( key < t[mid] )
high = mid - 1;
else
low = mid + 1;
}
for( j=i; j>high+1; j-- )
t[j] = t[j-1];
t  阅读全文

posted @ 2006-09-01 16:22 樱木 阅读(1475) | 评论 (0) | 编辑 收藏

直接插入排序的链表实现

     摘要: template
void insertion_sort( node * & head )//
{
node * first_unsorted,
* last_sorted,
* insert,
* insertPre;
if( head )
{
last_sorted = head;
while( last_sorted->next )
{
first_unsorted = last_sorted->next;
if( first_unsorted->key < last_sorted->key )
{
insert = head;
while( first_unsorted->key>=insert->key ) //从前到后, 保持稳定
{
insertPre = insert  阅读全文

posted @ 2006-09-01 15:00 樱木 阅读(1396) | 评论 (0) | 编辑 收藏