链表排序

你的名字 2022-03-27 13:19 346阅读 0赞

前言:

最近总结了一下针对只有头结点的单链表进行排序的几个简单的方法。

交换节点:插入排序,冒泡排序,简单选择排序
交换数据:快速排序

初始化:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4. //节点结构
  5. struct node
  6. {
  7. int val;
  8. struct node * next;
  9. };
  10. typedef struct node node, * list;
  11. //打印函数
  12. void printList(list mylist);
  13. //排序函数
  14. //插入排序
  15. void insertSort(list mylist);
  16. //冒泡排序
  17. void bubbleSort(list mylist);
  18. //简单选择
  19. void selectSort(list mylist);
  20. //快速排序
  21. void quickSort(list mylist);
  22. int main(void)
  23. {
  24. int arr[] = {5, 1, 7, 4, 2, 9, 6, 3, 8};
  25. //程序都是针对有头结点的单向链表
  26. list mylist = (list)malloc(sizeof(node));
  27. mylist -> val = 0;
  28. mylist -> next = NULL;
  29. int len = sizeof(arr) / sizeof(arr[0]);
  30. int i = 0;
  31. node * cur = mylist;
  32. while(i < len)
  33. {
  34. node * newNode = (node *)malloc(sizeof(node));
  35. newNode -> val = arr[i];
  36. newNode -> next = NULL;
  37. cur -> next = newNode;
  38. cur = cur -> next;
  39. i ++;
  40. }
  41. //insertSort(mylist);
  42. //bubbleSort(mylist);
  43. //selectSort(mylist);
  44. quickSort(mylist);
  45. printList(mylist);
  46. return 0;
  47. }
  48. void printList(list mylist)
  49. {
  50. node * cur = mylist -> next;
  51. while(cur != NULL)
  52. {
  53. printf("%d ", cur -> val);
  54. cur = cur -> next;
  55. }
  56. printf("\n");
  57. }

一、交换节点的单链表排序:

交换节点的情况比较复杂,所以我只是写了比较简单的三个。

1 、插入排序:

  1. //=============插入排序====================
  2. void insertSort(list mylist)
  3. {
  4. if((mylist -> next == NULL) || (mylist -> next -> next == NULL))
  5. {
  6. return;
  7. }
  8. node * head, * p1, * prep1, * p2, * prep2, * temp;
  9. head = mylist;
  10. prep1 = head -> next;
  11. p1 = prep1 -> next;
  12. //prep1和p1是否需要手动后移
  13. bool flag;
  14. while(p1 != NULL)
  15. {
  16. flag = true;
  17. temp = p1;
  18. //由于是单向链表,所以只能从头部开始检索
  19. for(prep2 = head, p2 = prep2 -> next; p2 != p1; prep2 = prep2 -> next, p2 = p2 -> next)
  20. {
  21. //发现第一个较大值
  22. if(p2 -> val > p1 -> val)
  23. {
  24. p1 = p1 -> next;
  25. prep1 -> next = p1;
  26. prep2 -> next = temp;
  27. temp -> next = p2;
  28. flag = false;
  29. break;
  30. }
  31. }
  32. //手动后移prep1和p1
  33. if(flag)
  34. {
  35. prep1 = prep1 -> next;
  36. p1 = p1 -> next;
  37. }
  38. }
  39. }
  40. //=============插入排序====================

2、冒泡排序:

  1. //=============冒泡排序====================
  2. void bubbleSort(list mylist)
  3. {
  4. if((mylist -> next == NULL) || (mylist -> next -> next == NULL))
  5. {
  6. return;
  7. }
  8. node *head, * pre, * cur, *next, * end, * temp;
  9. head = mylist;
  10. end = NULL;
  11. //从链表头开始将较大值往后沉
  12. while(head -> next != end)
  13. {
  14. for(pre = head, cur = pre -> next, next = cur -> next; next != end; pre = pre -> next, cur = cur -> next, next = next -> next)
  15. {
  16. //相邻的节点比较
  17. if(cur -> val > next -> val)
  18. {
  19. cur -> next = next -> next;
  20. pre -> next = next;
  21. next -> next = cur;
  22. temp = next;
  23. next = cur;
  24. cur = temp;
  25. }
  26. }
  27. end = cur;
  28. }
  29. }
  30. //=============冒泡排序====================

简单选择排序:

  1. //=============简单选择排序================
  2. void selectSort(list mylist)
  3. {
  4. if((mylist -> next == NULL) || (mylist -> next -> next == NULL))
  5. {
  6. return;
  7. }
  8. node * head, * prep1, * p1, * prep2, * p2, * premin, * min, * temp;
  9. head = mylist;
  10. for(prep1 = head, p1 = prep1 -> next; p1 -> next != NULL; prep1 = prep1 -> next, p1 = prep1 -> next)
  11. {
  12. //保存最小节点
  13. premin = prep1;
  14. min = p1;
  15. for(prep2 = p1, p2 = prep2 -> next; p2 != NULL; prep2 = prep2 -> next, p2 = prep2 -> next)
  16. {
  17. if(min -> val > p2 -> val)
  18. {
  19. premin = prep2;
  20. min = p2;
  21. }
  22. }
  23. if(p1 != min)
  24. {
  25. //一定要注意这个情况
  26. if(p1 -> next == min)
  27. {
  28. temp = min -> next;
  29. prep1 -> next = min;
  30. min -> next = p1;
  31. p1 -> next = temp;
  32. }else{
  33. temp = min -> next;
  34. prep1 -> next = min;
  35. min -> next = p1 -> next;
  36. premin -> next = p1;
  37. p1 -> next = temp;
  38. }
  39. }
  40. }
  41. }
  42. //=============简单选择排序================

一、交换数据的单链表排序:

交换数据的排序方式就特别简单了,因为不用考虑前驱和后继,只需要标记待交换的两个节点即可。因此在这里就直接介绍一下快速排序。

快速排序:

  1. //=============快速排序====================
  2. //交换节点
  3. void swap(node * a, node * b)
  4. {
  5. int temp = a -> val;
  6. a -> val = b -> val;
  7. b -> val = temp;
  8. }
  9. //求中间点
  10. node * partion(node * start, node * end)
  11. {
  12. if(start == end || start -> next == end)
  13. {
  14. return start;
  15. }
  16. //取第一个元素作为基准元素
  17. node * p = start, * q = start, * refer = start;
  18. //从start开始向后进行一次遍历(因为是单链表,无法按从左右向中间遍历的方法)
  19. while(p != end)
  20. {
  21. if(q -> val < refer -> val)
  22. {
  23. p = p -> next;
  24. swap(p, q);
  25. }
  26. q = q -> next;
  27. }
  28. swap(p, refer);
  29. return p;
  30. }
  31. //递归
  32. void quick_sort(node * start, node * end)
  33. {
  34. if(start == end || start -> next == end)
  35. {
  36. return;
  37. }
  38. node * mid = partion(start, end);
  39. quick_sort(start, mid);
  40. quick_sort(mid -> next, end);
  41. }
  42. void quickSort(list mylist)
  43. {
  44. if((mylist -> next == NULL) || (mylist -> next -> next == NULL))
  45. {
  46. return;
  47. }
  48. node * start = mylist -> next;
  49. node * end = NULL;
  50. quick_sort(start, end);
  51. }
  52. //=============快速排序====================

参考:

1、链表的基本排序——C语言
2、 单链表排序—-快排 &

发表评论

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

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

相关阅读

    相关 排序--归并排序

    要求在空间复杂度为O(1)的情况下对链表进行排序,在不考虑时间复杂度的情况下可以考虑冒泡排序,只对链表中的值进行操作,这样时间复杂度为O(n^2)。用归并排序,时间复杂度为O(

    相关 排序

    算法思想:采用直接插入排序算法的思想,先构成只含一个数据结点的有序单链表,然后一次扫描剩下的结点p(直至p==NULL为止),在有序表中通过比较查找插入p的前驱结点pre,然后

    相关 排序-归并

    链表排序,可以插入排序,我就不写了。 实现归并排序 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Con

    相关 排序

    前言: 最近总结了一下针对只有头结点的单链表进行排序的几个简单的方法。 交换节点:插入排序,冒泡排序,简单选择排序 交换数据:快速排序 初始化: i