Java排序算法之简单插入排序

插入排序的基本排序思想是：逐个考察每个待排序元素，将每一个新元素插入到前面已经排好序的序列中适当的位置上，使得新序列仍然是一个有序序列。 在这一类排序中主要介绍三种排序方法：直接插入排序、折半插入排序和希尔排序。

直接插入排序

基本思想

直接插入排序是一种最简单的插入排序方法，它的基本思想是：在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

算法原理

直接插入排序法的排序原则是：将一组无序的数字排列成一排，左端第一个数字为已经完成排序的数字，其他数字为未排序的数字。然后从左到右依次将未排序的数字插入到已排序的数字中。 直接插入排序具体算法描述如下： 1. 从第一个元素开始，该元素可以认为已经被排序； 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描 ； 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置； 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 5. 将新元素插入到该位置中； 6. 重复步骤2；

源码

package com.algorithm.sorting; /** * 插入排序 * @author Administrator * */ public class InsertionSort { public static void insert_sort(int array[]) { System.out.print("要排序的数组："); for (int a = 0; a < array.length; a++) { System.out.print(array[a] + "\t"); } System.out.println(""); int temp; for (int i = 0; i < array.length - 1; i++) { for (int j = i + 1; j > 0; j--) { if (array[j] < array[j - 1]) {// 如果待排序列中的元素大于等于有有序序列中的元素，则插入 temp = array[j - 1]; array[j - 1] = array[j]; array[j] = temp; } else { // 不需要交换 break; } } System.out.print("第" + (i + 1) + "次排序结果："); for (int a = 0; a < array.length; a++) { System.out.print(array[a] + "\t"); } System.out.println(""); } System.out.print("最终排序结果："); for (int a = 0; a < array.length; a++) { System.out.print(array[a] + "\t"); } } public static void main(String[] args) { int array[]={100, 20, 30,-1,99,53}; insert_sort(array); } }

源码解析

源码结果

要排序的数组：100 20 30 -1 99 53 第1次排序结果：20 100 30 -1 99 53 第2次排序结果：20 30 100 -1 99 53 第3次排序结果：-1 20 30 100 99 53 第4次排序结果：-1 20 30 99 100 53 第5次排序结果：-1 20 30 53 99 100 最终排序结果：-1 20 30 53 99 100

源码解析:

关键字 要排序的数组：（100）100 20 30 -1 99 53 第1次排序结果：（20）（20 100） 30 -1 99 53 第2次排序结果：（30）（20 30 100） -1 99 53 第3次排序结果：（-1）（-1 20 30 100） 99 53 第4次排序结果：（99）（-1 20 30 99 100） 53 第5次排序结果：（53）（-1 20 30 53 99 100） 排完序的数组 最终排序结果：-1 20 30 53 99 100

效率分析

空间效率：仅使用一个辅存单元。 时间效率：假设待排序的元素个数为 n，则向有序表中逐个插入记录的操作进行了 n-1 趟，每趟操作分为比较关键码和移动记录，而比较的次数和移动记录的次数取决于待排序列 按关键码的初始排列。 ⑴ 在最好情况下，即待排序序列已按关键字有序，每趟操作只需 1 次比较 0 次移动。 此时有： 总比较次数 = n-1 次 总移动次数 = 0 次 ⑵ 在最坏情况下，即待排序序列按关键字逆序排序，这时在第 j 趟操作中，为插入元 素需要同前面的 j 个元素进行 j 次关键字比较，移动元素的次数为 j+1 次。此时有： 总比较次数 =

∑j=1n−1j2=(n)(n−1)2 ∑ j = 1 n − 1 j 2 = ( n ) ( n − 1 ) 2 次

总移动次数 =

∑j=1n−1(j+1)2=(n+2)(n−1)2 ∑ j = 1 n − 1 ( j + 1 ) 2 = ( n + 2 ) ( n − 1 ) 2 次

⑶ 平均情况下：即在第 j 趟操作中，插入记录大约需要同前面的 j/2 个元素进行关键字 比较，移动记录的次数为 j/2+1 次。此时有： 总比较次数 ≈ n 2 /4 次 总移动次数 ≈ n 2 /4 次 由此，直接插入排序的时间复杂度为O(n 2 )，并且是一个稳定的排序方法。

总结

直接插入法的实现可以有多种方式，并不是唯一的。算法通过新建一个数组存放比较结果，通过增加空间的复杂度，减少了算法的时间复杂度。 遍历是每一个排序算法必不可少的过程，顺序地把待插入的数据元素按其关键字值的大小插入到已排序元素集合的适当位置。子集的元素个数从只有一个元素开始，逐次增大，当子集大小最终和集合大小相同时，排序完毕。 写博客是为了帮助开发者学习使用技术，同时巩固自己所学技术。如果此篇博客有助于您的学习，那是我的荣幸！如果此篇博客有任何瑕疵，请多多指教!在此感谢您的学习和指教！