排序算法----无表头链表插入排序
2018-06-18 04:12:00来源:未知 阅读 ()
- /* //对于很小的数源(N<=20),插入排序比快速排序好,此时,插入排序速度快也稳定。
-
//插入排序只用在小的或是非常接近排好序的输入数据上。
- ==========================
- 功能:直接插入排序(由小到大)
- 返回:指向链表表 头的指针
- ==========================
- */
- /*
- 直接插入排序的基本思想就是假设链表的前面n-1个节点是已经按键值
- (就是用它排序的字段,我们取学号num为键值)排好序的,对于节点n在
- 这个序列中找插入位置,使得n插入后新序列仍然有序。按照这种思想,依次
- 对链表从头到尾执行一遍,就可以使无序链表变为有序链表。
- 单向链表的直接插入排序图示:
- ---->[1]---->[3]----> [2]...---->[n]---->[NULL](原链表)
- head 1->next 3->next 2->next n->next
- ---->[1]---->[NULL](从原链表中取第1个节点作为只有一个节点的有序链表)
- head
- 图11
- ---->[3]---->[2]...---->[n]---->[NULL](原链表剩下用于直接插入排序的节点)
- first 3->next 2->next n->next
- 图12
- ---->[1]---->[2]---->[3]...---->[n]---->[NULL](排序后链表)
- head 1->next 2->next 3->next n->next
- 图13:有N个节点的链表直接插入排序
- 1、先在原链表中以第一个节点为一个有序链表,其余节点为待定节点。
- 2、从图12链表中取节点,到图11链表中定位插入。
- 3、上面图示虽说画了两条链表,其实只有一条链表。在排序中,实质只增加了一个用于指向剩下需要排序节点的头指针first罢了。
- 这一点请读者务必搞清楚,要不然就可能认为它和上面的选择排序法一样了。
- */
- struct student *InsertSort(struct student *head)
- {
- struct student *first; /*为原链表剩下用于直接插入排序的节点头指针*/
- struct student *t; /*临时指针变量:插入节点*/
- struct student *p; /*临时指针变量*/
- struct student *q; /*临时指针变量*/
- first = head->next; /*原链表剩下用于直接插入排序的节点链表:可根据图12来理解。*/
- head->next = NULL; /*只含有一个节点的链表的有序链表:可根据图11来理解。*/
- while (first != NULL) /*遍历剩下无序的链表*/
- {
- /*注意:这里for语句就是体现直接插入排序思想的地方*/
- for (t = first, q = head; ((q! = NULL) && (q->num < t->num)); p = q, q = q->next); /*无序节点在有序链表中找插入的位置*/
- /*退出for循环,就是找到了插入的位置*/
- /*注意:按道理来说,这句话可以放到下面注释了的那个位置也应该对的,但是就是不能。原因:你若理解了上面的第3条,就知道了。*/
- first = first->next; /*无序链表中的节点离开,以便它插入到有序链表中。*/
- if (q == head) /*插在第一个节点之前*/
- {
- head = t;
- }
- else /*p是q的前驱*/
- {
- p->next = t;
- }
- t->next = q; /*完成插入动作*/
- /*first = first->next;*/
- }
- return head;
- }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:C语言运算符优先级
下一篇:单链表实现多项式的加减乘运算
- C++ rand函数 2020-06-10
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash