本文主要是介绍Insertion Sort Integer Array Insertion Sort Linked List，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Sort Integer Array using Insertion sort.
//********************************************************************************************************
/* Insertion Sort 原理：就是前面的sort部分全部是相对值，从后面拿一个元素，然后跟前面的比较，
* 只要比最后一个小，就swap，然后cur-1， 然后continue swap，直到这个元素到达它应该在的位置，这样最后，这个array就被sort了。 */
public class InsertionSort {public void insertionSort(int[] array) {if(array == null || array.length == 1) return;for(int i=1; i<array.length; i++) {int temp = array[i];int j=i;while(j>=1 && array[j-1] > temp) {array[j] = array[j-1];j--;}array[j] = temp;}}
}
再联想到如何Sort a linked list using insertion sort.
思路：这个insertion sort，思想也是跟Array Insertion sort一样，就是找到相对位置正确的地点，然后插入进去。因为linked list只能一直向前搜索，所以，只能每次从头向后搜索，直到pre.next.val > cur.val的时候，再进行插入。dummpy的node一定要先把第一个点加入，然后进行比较，要insert就需要pre。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
class Solution {public ListNode insertionSortList(ListNode head) {if(head == null) {return null;}ListNode dummpy = new ListNode(0);dummpy.next = head;ListNode pre = dummpy;// 因为linkedlist只能往前走，所以每次只能从头往后扫描，//找到pre.next.val > cur.val的位置停下来；注意这题，head要留在dummpy后面，//然后cut掉 head.next = null; 用cur去insert；ListNode cur = head.next;head.next = null;while(cur != null) {pre = dummpy;while(pre.next != null && pre.next.val < cur.val) {pre = pre.next;}ListNode curnext = cur.next;cur.next = pre.next;pre.next = cur;cur = curnext;}return dummpy.next;}
}
这篇关于Insertion Sort Integer Array Insertion Sort Linked List的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
