详解直接插入排序算法与相关的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() { 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时,会使用插入排序。