做商城网站哪里,网站官网建设的价格,西安网站建设 盈科,计算机软件开发培训对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始#xff0c;该链表可以被认为已经部分排序#xff08;用黑色表示#xff09;。 每次迭代时#xff0c;从输入数据中移除一个元素#xff08;用红色表示#xff09;#xff0c;并原地将其插入到已排好序的…对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始该链表可以被认为已经部分排序用黑色表示。 每次迭代时从输入数据中移除一个元素用红色表示并原地将其插入到已排好序的链表中。
插入排序算法
插入排序是迭代的每次只移动一个元素直到所有元素可以形成一个有序的输出列表。 每次迭代中插入排序只从输入数据中移除一个待排序的元素找到它在序列中适当的位置并将其插入。 重复直到所有输入数据插入完为止。
示例 1
输入: 4-2-1-3 输出: 1-2-3-4
代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val x; }* }*/
class Solution {public ListNode insertionSortList(ListNode head) {ListNode dumpynew ListNode(Integer.MIN_VALUE);dumpy.nexthead;ListNode predumpy;while (head!null)//遍历所以节点{ListNode tempdumpy.next,curPredumpy;boolean changefalse;while (temp!head)//从当头节点到当前节点查找放置的位置{if(head.valtemp.val)//将当前节点连到合适位置{pre.nexthead.next;head.nexttemp;curPre.nexthead;changetrue;break;}curPretemp;temptemp.next;} if(change)//当前节点已经变化位置的情况{headpre.next;}else {//不需要变化位置的情况prehead;headhead.next;}}return dumpy.next;}
}
