和我这个很相似。。大牛写了多久?
List * inPlaceInsertionSort(List *head){
if(!head) throw(“empty list”);
// assume head is sorted, and unsort is unsorted
List *unsort = head->next;
while(unsort){
// take the front element from unsort
List *prev = NULL;
List *iter = head;
List *key = unsort;
// iterate within sorted list
while(iter){
if(iter->data < key->data){
prev = iter;
iter = iter->next;
}
else
break;
}
// if iter reaches end of sorted list, then sort the next node
unsort = unsort->next;
if(iter==key)
continue;
// mark the place where to insert key
List *place = iter;
// move iter to the end of sorted list and connnect to new unsort
while(iter->next!=key)
iter=iter->next;
iter->next = unsort;
// insert key to place
if(prev==NULL)
head = key;
else
prev->next = key;
key->next = place;
}
return head;
}