这是一种基于原位比较的排序算法。在此,将始终维护一个子列表。例如,数组的下部保持被排序。要插入此已排序子列表中的元素,必须找到其适当的位置,然后再将其插入该位置。因此,名称,插入排序。
依次搜索该数组,然后将未排序的项目移动并插入到已排序的子列表中(在同一数组中)。
1.If it is the first element, it is already sorted. return 1; 2.Pick next element 3.Compare with all elements in the sorted sub-list 4.Shift all the elements in the sorted sub-list that is greater than the value to be sorted 5.Insert the value 6.Repeat until the list is sorted
public class InsertionSort { public static void main(String args[]){ int array[] = {10, 20, 25, 63, 96, 57}; int size = array.length; for (int i=1 ;i< size; i++){ int val = array[i]; int pos = i; while(array[pos-1]>val && pos>0){ array[pos] = array[pos-1]; pos = pos-1; } array[pos] = val; } for (int i=0 ;i< size; i++){ System.out.print(" "+array[i]); } } }
输出结果
10 20 25 57 63 96