三
31
2009
排序－插入
发布者: seasun插入排序总是假设指定位置的左边的数组是有序的，而后将指定位置的值插入左边的有序数组。
指定的位置从下标1开始，每次循环递增1，直到数组结束。
插入排序的比较次数与交换次数的时间效率均为O(n^2)，确切的说是O(n^2 / 4)，比冒泡排序快一倍。
对于一个基本有序数组，由于内循环基本都是空循环，插入排序的效率接近O(n)，但对于完全逆序数组，插入排序的效率与冒泡相同。因此插入排序对于 基本有序，或反复排序的数组比较有利，实是上插入排序常常用于其他排序的首尾工作，其他排序只要排到基本有序即可，比如快速排序。
下面是代码。
class Insert {
public static void main(String[] args) {
int[] a = {1,5,3,8,4,3,8};
sort(a);
print(a);
}
private static void sort(int[] a) {
int temp;
for(int i=1; i<a.length; i++) {
int pos = i; //确定位置，在此位置左边的数组是有序的。
temp = a[i]; //根据位置确定要插入的数值。
while(pos>0 && a[pos-1]>temp) { //选择第一个不大于要插入数值的的位置
a[pos] = a[pos - 1]; //将数据以此向后移动
pos–;
}
a[pos] = temp; //将指定数值插入恰当位置
}
}
private static void print(int[] a) {
for(int i: a) System.out.print(i + ” “);
System.out.println();
}
}
- 分享
