摘要:前面三期分别写了三篇简单排序的算法,今天来讲一点稍微难一点的排序算法-----插入排序。
-
基本思想:
- 设n个数据已经按照顺序排列好(假定从小排到大)。
- 输入一个数据x,将其放在恰当的位置,使其顺序依旧从小到大。
- 输出已经排序完的数据。
-
适宜人群:
- 有一定Java SE基础,明白Java的数据类型,数组的定义、初始化以及常用数组的方法,还有Java的循环操作。
-
前期准备:
- 最好有一个开发工具比如说:eclipse或者myeclipse都可以,当然你使用DOS系统进行编译运行都可以,只不过改bug会麻烦一点。
-
插入排序的应用范围:
- 适合已经排序好的数据中插入一个或多个数据。
-
算法的优缺点:
- 优点:稳定,快;
- 缺点:比较次数不一定,比较次数越少,插入点后的数据移动越多,特别是当数据总量庞大的时候,但用链表可以解决 这个问题。
-
算法实现:
package liuenci.cn.package_3; public class HomeWork { public static void main(String[] args) {
int a[] = { 38,65,97,76,13,27,49 };
insertSort(a);
for(int i:a){
System.out.print(i +" ");
}
}
public static void insertSort(int[] a) {
int i, j, insertNote;
for (i = 1; i < a.length; i++) {
insertNote = a[i];
j = i - 1;
while (j >= 0 && insertNote < a[j]) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = insertNote;
}
}
}