算法初体验 (2)

插入排序的Java语言实现如下：

public void sort(Comparable[] arr){ int n = arr.length; for (int i = 0; i < n; i++) { // 寻找元素arr[i]合适的插入位置 for( int j = i; j > 0 && arr[j].compareTo(arr[j-1]) < 0 ; j--) swap(arr, j, j-1); } }

通过比较选择排序和插入排序的代码实现，我们可以发现一旦有部分排序好之后，新插入一个数如果比排好序最大值还要大，则不用再和其他数字比较，减少了比较次数。但是，我们应该注意到插入排序在每次遍历的时候都需要进行交换操作，这个交换操作包含三次赋值操作，导致插入排序的时间要比选择排序的时间更长。针对这个问题，我们的先辈们想到了一个方法：先将待比较元素复制一份，然后依次和有序数组中的元素进行比较，如果比有序数组中的元素小，则将有序数组中的元素覆盖待比较元素，以此类推。如下图所示，首先我们将元素6复制一份，接着验证元素6是否应当放在当前位置，通过比较6和它之前的元素大小，发现元素8应该放在元素6的位置上，因此将元素8覆盖元素6，然后我们考查元素6是否应该放在前一个元素位置上，此时，由于元素8在第0个位置上我们就不用比较直接覆盖。它的Java代码实现如下：

for (int i = 0; i < n; i++) { // 寻找元素arr[i]合适的插入位置 Comparable e = arr[i]; int j = i; for( ; j > 0 && arr[j-1].compareTo(e) > 0 ; j--) arr[j] = arr[j-1]; arr[j] = e; }

这样一来，内循环只需要进行一次赋值操作，效率得到了大大优化，不仅超过了选择排序，而且在待排序数组是有序的情况下，时间复杂度可以达到O(n)。

欢迎关注微信公众号：木可大大，所有文章都将同步在公众号上。