插入排序

Leecode第147题：

题目描述

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。
链接：https://leetcode.cn/problems/insertion-sort-list

输入: head = [4,2,1,3]
输出: [1,2,3,4]

题解代码：

public ListNode insertionSortList(ListNode head) {
     ListNode cur = new ListNode();
     cur = head.next;
     ListNode pre = new ListNode();
     pre = head;
     while (cur.next != null) {
         if (cur.val < pre.val) {
             swap(cur, pre);
         }
         if (pre.next == cur) {
             pre = head;
             cur = cur.next;
         } else {
             pre = pre.next;
         }
     }
     return head;
 }
 public void swap(ListNode cur, ListNode pre) {
     int temp;
     temp = cur.val;
     cur.val = pre.val;
     pre.val = temp;
 }

题解思路：

1. 首先我们创建两个指针一个指向head的pre和一个指向head.next的cur

2. 我们来判断终止的条件就是当cur指针指向的最后一个元素比较完成后结束也就是(cur!=null)

3. 在循环里面我们要知道如果当前的cur.val<pre.val这时我们需要交换两者的数据。

4. 交换完毕后有两种情况：

   • 当pre.next==cur时证明两者刚刚交换过此时直接让cur指向下一位而pre回到head
   • 当pre.next!=cur时这时候cur不能指向下一位而是让pre指向下一位进行和cur的值进行比较完成循环。

5. 最终直接返回head的指针。

Leecode题解时间更快

class Solution {
    public ListNode insertionSortList(ListNode head) {
        //首先判断头节点是否为空
        if (head == null) {
            return head;
        }
        //其次创建一个虚拟的头节点
        ListNode dummyHead = new ListNode(0);
        //让该虚拟头节点指向head
        dummyHead.next = head;
        //接着创建两个指着一个指向头一个指向头的下一个节点
        ListNode lastSorted = head, curr = head.next;
        //判断当最快到达链表尾部的元素不为空时进行循环
        while (curr != null) {
            //如果发现靠后的节点小于当前靠前的节点直接让靠后的节点++
            if (lastSorted.val <= curr.val) {
                lastSorted = lastSorted.next;
            } else {
                //否则的话 就创建一个prev节点指向虚拟节点
                ListNode prev = dummyHead;
                //直至prev指向=当前靠前节点
                while (prev.next.val <= curr.val) {
                    prev = prev.next;
                }
                //然后进行节点的交换
                lastSorted.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
            }
            curr = lastSorted.next;
        }
        return dummyHead.next;
    }

}

插入排序算法的图解和代码详解；

public class InsertionSort {
    //核心代码---开始
    public static void sort(Comparable[] arr){
		//首先获取数组的长度
        int n = arr.length;
        //其次对数组进行遍历
        for (int i = 0; i < n; i++) {
            // j从第1开始每次和前面的作比较如果比前面的数据小则直接交换数据反之则退出内循环
          //这个相当于j每次--从后面开始直至比到比他小的数为止也是插入排序的精髓
            for( int j = i ; j > 0 ; j -- )
                if( arr[j].compareTo( arr[j-1] ) < 0 )
                    swap( arr, j , j-1 );
                else
                    break;
        }
    }
    //交换两个数组的内容
    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }