详解直接插入排序算法与相关的Java版代码实现

详解直接插入排序算法与相关的Java版代码实现

直接插入排序

直接插入排序的思路很容易理解，它是这样的：

1.把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的。

2.从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。

3.重复上述过程直到最后一个元素被插入有序子数组中。

4.排序完成。

示例：

思路很简单，但代码并非像冒泡排序那么好写。首先，如何判断合适的位置？大于等于左边、小于等于右边？不行，很多边界条件需要考虑，而且判断次数太多。其次，数组中插入元素，必然需要移动大量元素，如何控制它们的移动？

实际上，这并不是算法本身的问题，而多少和编程语言有点关系了。有时候算法本身已经很成熟了，到了具体的编程语言还是要稍作改动。这里讲的是java算法，那就拿Java说事儿。

为了解决上述问题，我们对第二步稍作细化，我们不从子数组的起始位置开始比较，而从子数组尾部开始逆序比较，只要比需要插入的数大，就向后移动。直到不大于该数的数，那么，这个空出来的位置就安放需要插入的数字。因此，我们可以写出以下代码：

InsertArray.java

public class InsertArray {

// 数组

private long[] arr;

// 数组中有效数据的大小

private int elems;

// 默认构造函数

public InsertArray() {

arr = new long[50];

}

public InsertArray(int max) {

arr = new long[max];

}

// 插入数据

public void insert(long value) {

arr[elems] = value;

elems++;

}

// 显示数据

public void display() {

WOnvdv for (int i = 0; i < elems; i++) {

System.out.print(arr[i] + " ");

}

System.out.println();

}

// 插入排序

public void insertSort() {

long select = 0L;

for(int i = 1; i < elems; i++) {

select = arr[i];

int j = 0;

for(j = i;j > 0 && arr[j - 1] >= select; j--) {

arr[j] = arr[j - 1];

}

arr[j] = select;

}

}

}

测试类：

TestInsertArray.java

public class TestInsertArray {

public static void main(String[] args) {

InsertArray iArr = new InsertArray();

iArr.insert(85);

iArr.insert(7856);

iArr.insert(12);

iArr.insert(8);

iArr.insert(5);

iArr.insert(56);

iArr.display();

iArr.insertSort();

iArr.display();

}

}

打印结果：

算法性能/复杂度

现在讨论下直接插入算法的时间复杂度。无论输入如何，算法总会进行n-1轮排序。但是，由于每个元素的插入点是不确定的，受输入数据影响很大，其复杂度并不是一定的。我们可以分最佳、最坏、平均三种情况讨论。

1.最佳情况：由算法特点可知，当待排数组本身即为正序（数组有序且顺序与需要的顺序相同，于我们的讨论前提，即为升序）时为最佳，理由是这种情况下，每个元素只需要比较一次且无需移动。算法的时间复杂度为O(n);

2.最坏情况：很显然，当待排数组为逆序时为最坏情况，这种情况下我们的每轮比较次数为i-1, 赋值次数为i。总的次数为级数2n-1的前n项和，即n^2.算法的时间复杂度为O(n^2);

3.平均情况：由上述分析可以得到平均情况下算法的运算次数大约为（n^2）/2（注：这里计算以赋值和比较计，若按移动和比较，则大约为n^2/4），显然，时间复杂度还是O(n^2)。

至于算法的空间复杂度，所有移动均在数据内部进行，唯一的开销是我们引入了一个临时变量（有的数据结构书上称为“哨兵”），因此，其空间复杂度（额外空间）为O(1)。

算法稳定性

由于只需要找到不大于当前数的位置而并不需要交换，因此，直接插入排序是稳定的排序方法。

算法变种

如果待排列的数据比较多，那么每次从后往前找就造成了很大的开销，为了提高查找速度，可以采用二分查找（Binary Search）进行性能优化。由于二分查找的效率很高，保证了O(㏒n)复杂度，在数据比较多或输入数据趋向最坏情况时可以大幅提高查找效率。在有些书上将这种方法称为折半插入排序。它的代码实现比较复杂，以后有时间可以贴出来。

此外，还有2-路插入排序和表插入排序。2-路插入排序是在折半插入排序的基础上进一步改进，其移动次数大为降低，大约为n^2/8。但是，它并不能避免移动次数，也不能降低复杂度级别。表插入排序则完全改变存储结构，不移动记录，但需要维护一个链表，以链表的指针修改代替移动记录。因此，其复杂度仍然是O(n^2)。

有关2-路插入排序和表插入排序，可以参考严蔚敏、吴伟民编著的《数据结构》一书。

算法适用场景

插入排序由于O(n^2)的复杂度，在数组较大的时候不适用。但是，在数据比较少的时候，是一个不错的选择，一般做为快速排序的扩充。例如，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序。又如，在JDK 7 java.util.Arrays所用的sort方法的实现中，当待排数组长度小于47时，会使用插入排序。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。