©2020-2024 ioDraw All rights reserved,
Privacy Policy
<>链表的插入排序
插入排序我们在对数组的排序中应该都了解过，基本的思想是这样的：每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。
通俗易懂的举一个例子，给一个班的人身高排序，计算机和人类最大的区别就是计算机不能自己思考，计算机最擅长的是循环和重复，因此它只能用最普遍的办法，先找出第一个人拿出来，让他站在另一个队伍里，然后再找第二个人，如果比他个子矮就站在他前面，比他高就站在他后面，再往后每一个人从第一个人的位置开始逐个比较，直到找到比他高的人，站在他的身前即可，如果比队伍里的人都高，就站在队伍的最后一个。
我们先来看一下数组的插入排序代码，和后面的链表插入排序做对比：
void insertSort(int arry[], int len) { int i; int temp;//保存要插入的元素 int j;
//从当前要要比较插入的元素的前面一个开始 for ( i = 1; i < len; i++)//第一个元素视为有序,把后面的元素一个一个的插入到前面 {
temp= arry[i]; for ( j = i - 1;j >= 0&&arry[j]>temp; j--) { arry[j + 1] = arry[j
];//前面的元素往后面移动 } arry[j + 1] = temp;//把要插入的元素,插入进对应的位置 }
对链表排序的话道理相同，但是链表和数组的不同是数组的每一项有下标，可以直接确定到每一个数组元素，但是链表只能从头到尾逐个找,因此我们需要的参数需要更多，我们先来看一下代码：
struct ListNode *insertionSortList(struct ListNode *head) { if (head == NULL) {
return head;//判断链表是否为空链表 } struct ListNode *dummyHead = malloc(sizeof(struct
ListNode)); dummyHead->val = 0; dummyHead->next = head; struct ListNode *
lastSorted= head;//定义一个临时节点=head struct ListNode *curr = head->next; while (curr
!= NULL) { if (lastSorted->val <= curr->val) { lastSorted = lastSorted->next; }
else {//当前一个的数字大于后面一个的时候 struct ListNode *prev = dummyHead; while (prev->next->
val<= curr->val) { prev = prev->next;//从头开始找到比curr大的一项，把curr放在它的前面 } lastSorted
->next = curr->next; curr->next = prev->next; prev->next = curr;
//用于更换curr和前面一项顺序 } curr = lastSorted->next; } return dummyHead->next; }
我们仔细看代码就能找到和数组插入排序相同之处，如果会了数组的插入排序，链表的插入排序也就迎刃而解了。