排序算法之直接插入排序
一、直接插入排序
思想：假设待排数据有n个，将待排序列分为有序和无序两个部分，初始时，有序部分仅有一个数据即为第一个数据，其余n-1个数据为无序序列，然后将无序序列的每个数据分别与有序序列的每个数据比较，插入到合适位置。（无序序列数据从有序序列最后一个数开始往前比较）。
例如：
分析：我们考虑最坏的情况，当数组完全逆序的时候比如{6,5,4,3,2,1}这种情况，我们进行升序排序，我们比较的次数：1+2+3+4+5，数据移动的次数：1+2+3+4+5。扩展到n个元素的数组 比较次数：1+2…+n-1 = n(n-1)/2，移动的次数同样为n(n-1)/2，所考虑数据随机的情况，时间复杂度为（n^2 -n）/2 = O(n2)。从这里可以看出同样的O(n2)时间复杂度，直接插入排序比选择排序和冒泡排序性能要要一些。直接插入排序对数组基本有序和数组元素比较少的时候，速度比较快。
代码：
/* 用直接插入排序算法实现对数组元素升序排列 */ package edu.java.InsertSort; import java.util.Scanner; public class InsertSortTest { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("请输入待排序列个数："); int n = scanner.nextInt(); int[] array = new int[n + 1]; System.out.println("请输入数组元素"); for (int i = 1; i <= n; i++) { array[i] = scanner.nextInt(); } insertSort(array,n); } public static void insertSort(int array[], int n) { //从第二个元素开始将无序区每个元素与有序区元素比较;array[0]为监视哨 for (int i = 2; i <= n; i++) { //若无序区第一个元素小于有序区最后一个元素 if (array[i] < array[i - 1]) { //将array[i]的值赋给监视哨 array[0] = array[i]; //从有序区后面开始与监视哨的值作比较 for (int j = i - 1; array[0] < array[j]; j--) { //元素后移 array[j+1] = array[j]; array[j] = array[0]; } } } System.out.println("----------------------"); System.out.println("排序完成，升序序列为："); for (int i = 1; i <= n ; i++) { System.out.println(array[i]); } } }
