插入排序

|
算法

往一个有序数组中插入元素

原理

对于一个有序的数组，往其中插入一个元素，跟数组中个每一个元素进行比较，直到找到一个合适的位置，进行插入操作，这就是插入排序。

我们进行排序的时候，给定的往往都是一个无序的数组。这个时候，我们可以把第一个元素当作一个长度为1的有序的数组，往这个数组中进行插入，就把它转换成了插入排序。

代码

1
2
3
4
5
6
7
8
9
10
11
public void sort(Comparable[] arr) {
	/*
	从第二个元素开始，跟之前的每一个元素进行比较，小于时进行交换
	*/
    for (int i = 1; i < arr.length; i++) {
    	//
        for (int j = i; j > 0 && less(arr[j], arr[j - 1]); j++) {
            exch(arr, j, j - 1);
        }
    }
}

缺点

只能交换相邻位置的元素，如果最小的元素刚好在数组的最后，那么对于一个长度为n的数组，就需要交换n-1次。如果在比较时，可以加入二分查找等类似操作可以减少元素交换的次数。