插入排序算法:
插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
重复直到所有输入数据插入完为止。
来源:力扣(LeetCode)
struct ListNode* insertionSortList(struct ListNode* head){
if(head == NULL||head->next == NULL)
return head;
//初始条件
struct ListNode* sortHead = head;
struct ListNode* cur = head->next;
sortHead->next = NULL;
while(cur)//终止条件
{
//迭代条件
struct ListNode* next = cur->next;
//将cur节点插入到前面有序区间
struct ListNode* p = NULL,*c = sortHead;
while(c)
{
if(cur->val < c->val)
{
break;
}
else
{
p = c;
c = c->next;
}
}
if(p == NULL)
{
cur->next = c;
sortHead = cur;
}
else
{
p->next = cur;
cur->next = c;
}
cur = next;
}
return sortHead;
}
cs