直接插入排序
一、基本概念
直接插入排序( straight insertion sort )是一种最简单的排序方法。它的基本操作是将一个记录插入到一个长度为 m (假设)的有序表中,使之仍保持有序,从而得到一个新的长度为 m + 1 的有序表。
二、具体操作
设有一组关键字{ K 1 , K 2 ,…, K n };排序开始就认为 K 1 是一个有序序列;让 K 2 插入上述表长为 1 的有序序列,使之成为一个表长为 2 的有序序列;然后让 K 3 插入上述表长为 2 的有序序列,使之成为一个表长为 3 的有序序列;依次类推,最后让 K n 插入上述表长为 n-1 的有序序列,得一个表长为 n 的有序序列。
三、稳定性及复杂度
直接插入排序是稳定的排序方法。此算法外循环 n-1 次,在一般情况下内循环平均比较次数的数量级为O(n) ,所以算法总时间复杂度为O(n2) 。
四、示例代码
/** * 直接插入排序 */ public class ZhijieCharuPaixu { public static void main(String[] args) { int[] a = { 12, 3, 41, 23, 6, 9, 19, 0 }; sort(a); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + "->"); } } public static int[] sort(int[] arr) { int tmp = 0; for (int i = 1; i < arr.length; i++) { tmp = arr[i]; int j = i - 1; while (j >= 0 && tmp < arr[j]) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = tmp; } return arr; } }
参考链接:
http://sjjg.js.zwu.edu.cn/SFXX/paixu/paixu6.2.1.html
http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.2.1.1.htm
http://sjjg.js.zwu.edu.cn/SFXX/sf1/zjcr.html
http://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F