[{"createTime":1735734952000,"id":1,"img":"hwy_ms_500_252.jpeg","link":"https://activity.huaweicloud.com/cps.html?fromacct=261f35b6-af54-4511-a2ca-910fa15905d1&utm_source=V1g3MDY4NTY=&utm_medium=cps&utm_campaign=201905","name":"华为云秒杀","status":9,"txt":"华为云38元秒杀","type":1,"updateTime":1735747411000,"userId":3},{"createTime":1736173885000,"id":2,"img":"txy_480_300.png","link":"https://cloud.tencent.com/act/cps/redirect?redirect=1077&cps_key=edb15096bfff75effaaa8c8bb66138bd&from=console","name":"腾讯云秒杀","status":9,"txt":"腾讯云限量秒杀","type":1,"updateTime":1736173885000,"userId":3},{"createTime":1736177492000,"id":3,"img":"aly_251_140.png","link":"https://www.aliyun.com/minisite/goods?userCode=pwp8kmv3","memo":"","name":"阿里云","status":9,"txt":"阿里云2折起","type":1,"updateTime":1736177492000,"userId":3},{"createTime":1735660800000,"id":4,"img":"vultr_560_300.png","link":"https://www.vultr.com/?ref=9603742-8H","name":"Vultr","status":9,"txt":"Vultr送$100","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":5,"img":"jdy_663_320.jpg","link":"https://3.cn/2ay1-e5t","name":"京东云","status":9,"txt":"京东云特惠专区","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":6,"img":"new_ads.png","link":"https://www.iodraw.com/ads","name":"发布广告","status":9,"txt":"发布广告","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":7,"img":"yun_910_50.png","link":"https://activity.huaweicloud.com/discount_area_v5/index.html?fromacct=261f35b6-af54-4511-a2ca-910fa15905d1&utm_source=aXhpYW95YW5nOA===&utm_medium=cps&utm_campaign=201905","name":"底部","status":9,"txt":"高性能云服务器2折起","type":2,"updateTime":1735660800000,"userId":3}]
<>链表的插入排序
插入排序我们在对数组的排序中应该都了解过,基本的思想是这样的:每一步将一个待排序的数据插入到前面已经排好序的有序序列中,直到插完所有元素为止。
通俗易懂的举一个例子,给一个班的人身高排序,计算机和人类最大的区别就是计算机不能自己思考,计算机最擅长的是循环和重复,因此它只能用最普遍的办法,先找出第一个人拿出来,让他站在另一个队伍里,然后再找第二个人,如果比他个子矮就站在他前面,比他高就站在他后面,再往后每一个人从第一个人的位置开始逐个比较,直到找到比他高的人,站在他的身前即可,如果比队伍里的人都高,就站在队伍的最后一个。
我们先来看一下数组的插入排序代码,和后面的链表插入排序做对比:
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; }
我们仔细看代码就能找到和数组插入排序相同之处,如果会了数组的插入排序,链表的插入排序也就迎刃而解了。