#排序(1)#
##插入排序## 插入排序是一个对少量数据进行排序的有效算法。现实中最常见的插入排序的例子莫过于打扑克，整理手中的扑克。开始摸牌时，我们左手为空的，牌面朝下放在桌上。接着，一次从桌子上摸起一张牌，并将它插入左手正确的位置，并确保左手的牌从左到右是按照从小到大的顺序排列的。
如下用TypeScript做了一个简单的演示:代码地址。
以下是基于链表的c语言版本实现:
#include <stdio.h>
#include <stdlib.h>
const int max = 100;
const int maxnode = 20;
typedef struct node_s{
int value;
struct node_s * next;
}node_t;
int get_random(){
return (rand() % max);
}
int create_new_node_t(int v,node_t ** n){
node_t * node = calloc(sizeof(node_t),1);
node->value = v;
node->next = NULL;
*n = node;
return 0;
}
void insert_node(node_t * h,node_t * newnode){
if(h->next!=NULL){
node_t * p = h->next;
h->next = newnode;
newnode->next = p;
}else{
h->next = newnode;
}
}
void print_node_list(node_t * h){
node_t * p = h->next;
printf("list nodes:");
while(p != NULL){
printf("%d ",p->value);
p = p->next;
}
printf("\n");
}
void free_node_list(node_t * h){
node_t * p = h->next;
node_t * q = NULL;
while(p != NULL){
q = p->next;
free(p);
p = q;
}
}
void insertion_sort(node_t * h,node_t * n){
int ibool = 0;
node_t * p = h;
node_t * q = p->next;
while(q != NULL){
if(q->value > n->value){
insert_node(p,n);
ibool = 1;
break;
}
p=q;
q = q->next;
}
if(ibool < 1){
p->next = n;
}
}
int main(int argc, char *argv[])
{
node_t h;
node_t * p = NULL;
node_t * q = NULL;
int i = 0;
h.next = NULL;
while(i< maxnode){
int r = get_random();
create_new_node_t(r,&p);
printf("insert node :% d\n",p->value);
insertion_sort(&h,p);
print_node_list(&h);
i++;
}
free_node_list(&h);
return 0;
}
运行环境:ubuntu12.04
参考文献:
«算法导论» 第二章 2.1节