链表排序问题

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

链表排序问题前言冒泡排序1.思想2.代码插入排序1.思想2.代码总结

前言

链表与数组一样也有许多排序方式

今天介绍链表的插入排序。

冒泡排序

1.思想

在数组中冒泡排序之所以容易实现的原因在于： 数组中数据在内存中的存储是连续的，并且通过下标的改变就可以轻松改变指针所指的地址

但在链表中，每个节点在内存中的位置是不确定的，所以不容易改变指针所指地址，来重复对链表内相邻节点的数据进行比较。

2.代码

数组

void bubble(int a[],int len){int i,j,t;for(i = 0; i < len; i++){for(j = 0; j < len - i -1; j++){if(a[j] > a[j + 1]){t = a[j];a[j] = a[j + 1];a[j + 1] = t;}} }}

链表

struct listnode* bubblesort(struct listnode *head){if(head == NULL)return head; struct listnode *p,*q,*dummyhead;int temp;dummyhead = (struct listnode*)malloc(sizeof(struct listnode));dummyhead->data = NULL;dummyhead->next = head;p = dummyhead;//p为冒牌中的交换趟数 q = head;while(p != NULL){q = head;//每次q都应该重新回到最初点 while(q->next != NULL){if(q->data > q->next->data)//冒泡里的交换 {temp = q->data;q->data = q->next->data;q->next->data = temp;}q = q->next;}p = p->next;}return dummyhead->next;}

插入排序

1.思想

插入排序的基本思想是，维护一个有序序列，初始时有序序列只有一个元素，每次将一个新的元素插入到有序序列中，将有序序列的长度增加 11，直到全部元素都加入到有序序列中

如果是数组的插入排序，则数组的前面部分是有序序列，每次找到有序序列后面的第一个元素（待插入元素）的插入位置，将有序序列中的插入位置后面的元素都往后移动一位，然后将待插入元素置于插入位置。

对于链表而言，插入元素时只要更新相邻节点的指针即可，不需要像数组一样将插入位置后面的元素往后移动。

对于单向链表而言，只有指向后一个节点的指针，因此需要从链表的头节点开始往后遍历链表中的节点，寻找插入位置。

2.代码

数组插入排序

代码如下（示例）：

void insert(int arr[],int len){int i,j,temp;for(i = 1; i < len; i++){temp = arr[i]; for(j = i - 1; j >= 0 && arr[j] > temp; j--)//找到比前一个大的值 {arr[j + 1] = arr[j];//将数组往后移一位 }arr[j + 1] = temp;//将temp储存的值赋予 }}

链表代码

struct listnode *insertsort(struct listnode *head){if(head == NULL) return head;//链表为空 struct listnode* phead;//一个记录头结点的结点 phead = (struct listnode*)malloc(sizeof(struct listnode));phead->data = 0;phead->next = head;struct listnode *p,*q;p = head;q = p->next;while(q != NULL){if(p->data <= q->data){p = p->next;}else{struct listnode* pre;pre = phead;while(pre->next->data <= q->data)//找到要插入位置的前一个结点 {pre = pre->next;} p->next = q->next;q->next = pre->next;pre->next = q;//插入结点}q = p->next;}return phead->next;//return head;}

总结

学习了一下链表排序问题