双向循环链表的插入排序

Dear 丶 2022-06-04 01:41 284阅读 0赞

前两篇博文,我讨论了链表的冒泡排序和选择排序(以Linux内核链表为例),这篇文章,我想说说插入排序。

一、复习数组的插入排序

插入排序在算法思想中属于“减治法”。

减治法的基本思想是:规模为n的原问题的解与较小规模的子问题的解之间具有某种关系。由于存在这种关系,所以只需求解其中一个较小规模的子问题就可以得到原问题的解。

插入排序就是基于“减治法”中的“减一技术”实现的。如果题目要求对a[0]a[n-1]进行排序,我幻想从a[0]a[n-2]已经是有序的了,那么我需要做的就是在这些有序的元素中为a[n-1]找到一个合适的位置,然后把它插到那里就行。

虽然插入排序基于递归思想,可从顶至下实现;但是,从底至上地实现这个算法——使用迭代会效率更高。从a[1]开始,到a[n-1]为止,a[i]被插入到数组的前i个有序元素中的适当位置上(但是,和选择排序不同,这个位置一般来说并不是它的最终位置)。

示意图如下:

这里写图片描述

二、内核链表的插入排序

完整代码如下。(list.h文件这里就不列了,有需要的话可以参考我的博文http://blog.csdn.net/longintchar/article/details/78034827)

  1. #include <stdio.h>
  2. #include "list.h"
  3. struct data_info {
  4. int data;
  5. struct list_head list;
  6. };
  7. int cmp_data(struct list_head *a, struct list_head *b)
  8. {
  9. struct data_info *pa = list_entry(a, struct data_info, list);
  10. struct data_info *pb = list_entry(b, struct data_info, list);
  11. return pa->data - pb->data;
  12. }
  13. void swap(struct list_head *a, struct list_head *b)
  14. {
  15. struct list_head flag = {NULL, NULL};
  16. __list_add(&flag, b->prev, b);
  17. list_del(b);
  18. __list_add(b, a->prev, a);
  19. list_del(a);
  20. __list_add(a, flag.prev, &flag);
  21. list_del(&flag);
  22. }
  23. void insert_sort(struct list_head *head,
  24. int(*cmp)(struct list_head *a,
  25. struct list_head *b))
  26. {
  27. struct list_head *i, *j,*temp;
  28. i = head->next->next; //i指向第2个结点
  29. list_for_each_from(i,head){ //i从第2个结点开始遍历,因为第1个已经有序
  30. j = i->prev; //j指向i的前一个结点
  31. if (cmp(j, i) <= 0) //从表头开始,按照升序排列
  32. continue;
  33. list_for_each_reverse_continue(j,head){
  34. if(cmp(j,i) <= 0)
  35. break;
  36. }
  37. temp = i->next; //因为下文要删除i结点,所以记录i结点的下一个结点
  38. list_del(i);
  39. __list_add(i,j,j->next); //把i插入到j的后面
  40. i = temp->prev; //i指针归位
  41. }
  42. }
  43. int main(void)
  44. {
  45. struct data_info s[] = {
  46. {
  47. 6}, {
  48. 4}, {
  49. 7}, {
  50. 9}, {
  51. 2}, {
  52. 8}, {
  53. 5}, {
  54. 1}, {
  55. 3}, {
  56. 7}};
  57. LIST_HEAD(head);
  58. int i;
  59. for (i = 0; i < sizeof s/ sizeof *s; ++i)
  60. {
  61. list_add_tail(&s[i].list, &head);
  62. } //尾插,构成链表
  63. struct data_info *pdata = NULL;
  64. list_for_each_entry(pdata, &head, list)
  65. {
  66. printf("%d ", pdata->data);
  67. }
  68. printf("\n"); //排序之前
  69. insert_sort(&head, cmp_data); //进行排序
  70. list_for_each_entry(pdata, &head, list)
  71. {
  72. printf("%d ", pdata->data);
  73. }
  74. printf("\n"); //排序之后
  75. return 0;
  76. }

以上代码运行结果如下:

6 4 7 9 2 8 5 1 3 7
1 2 3 4 5 6 7 7 8 9

三、代码解析

1. swap函数

可以参考我的博文http://blog.csdn.net/longintchar/article/details/78638975

2. list_for_each_from

  1. #define list_for_each_from(cur, head) \
  2. for (; cur != head; cur = (cur)->next)

这个宏表示从当前结点开始遍历,一直到链表尾端。

3. list_for_each_reverse_continue

  1. #define list_for_each_reverse_continue(cur, head) \
  2. for (cur = (cur)->prev; cur != (head); cur = (cur)->prev)

这个宏表示从当前结点的前一个结点开始,逆序遍历,一直到第一个结点。

4. __list_add函数

  1. static inline void __list_add(struct list_head *new,
  2. struct list_head *prev,
  3. struct list_head *next)
  4. {
  5. next->prev = new;
  6. new->next = next;
  7. new->prev = prev;
  8. prev->next = new;
  9. }

new指向的结点插入到prevnext结点之间。

5. insert_sort函数

  1. void insert_sort(struct list_head *head,
  2. int(*cmp)(struct list_head *a,
  3. struct list_head *b))
  4. {
  5. struct list_head *i, *j,*temp;
  6. i = head->next->next; //i指向第2个结点
  7. list_for_each_from(i,head){ //i从第2个结点开始遍历,因为第1个已经有序
  8. j = i->prev; //j指向i的前一个结点
  9. if (cmp(j, i) <= 0) //从表头开始,按照升序排列
  10. continue;
  11. list_for_each_reverse_continue(j,head){
  12. if(cmp(j,i) <= 0)
  13. break;
  14. }
  15. temp = i->next; //因为下文要删除i结点,所以记录i结点的下一个结点
  16. list_del(i);
  17. __list_add(i,j,j->next); //把i插入到j的后面
  18. i = temp->prev; //i指针归位
  19. }
  20. }

6~7行:i从第二个结点开始,一直遍历到最后一个结点;
第10行:j指向i结点的前驱,如果j结点小于等于i结点,说明i不需要插入,它已经在合适的位置(不一定是最终位置)上了,此时进入下一轮迭代;
第12~14行:能执行到第12行,说明j结点大于i结点,这时候我们要做的是——从j向前找,找到第一个小于等于i的结点,这个结点用j指示。找到后跳出这层循环。
17~18行:我们需要把i结点插入到j的后面。
16和19行:因为i结点移动了,所以i指针需要归位,第16行记录了i结点的下一个结点,叫temp,第19行让i指向temp的前驱,完成归位。为什么要归位?可以参考我的博文 http://blog.csdn.net/longintchar/article/details/78638975 中的4.4节。

【完】

发表评论

表情:
评论列表 (有 0 条评论,284人围观)

还没有评论,来说两句吧...

相关阅读

    相关 循环双向

    一、循环链表 循环链表是与单链表一样,是一种链式的存储结构,所不同的是,循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。

    相关 双向循环

    一、双向链表 每个结点有两个指针域和若干数据域,其中一个指针域指向它的前趋结点,一个指向它的后继结点。它的优点是访问、插入、删除更方便,速度也快了。但“是以空间换时间”。

    相关 双向循环插入排序

    前两篇博文,我讨论了链表的冒泡排序和选择排序(以Linux内核链表为例),这篇文章,我想说说插入排序。 一、复习数组的插入排序 插入排序在算法思想中属于“减治法”。

    相关 双向循环选择排序

    一、复习数组的选择排序 选择排序属于蛮力法。 首先,扫描整个列表,找到最小的元素,将其和第一个元素交换位置;然后从第二个元素开始扫描列表,找到最小的元素,再将其和第二