过几天就是双
11
了,现在的我已经没有任何购物的欲望了。也许会在双11
,买几本书,充实一下自己,仅此而已。
timg.jpg
在一般情况下,插入排序是基本排序算法中最好的一种。虽然插入排序算法需要O(N^2)
的时间,但是一般情况下,它要比冒泡排序快一倍,比选择排序还要快一些。
public class InsertSortDemo {
public static int[] a = { 11, 20, 5, 4, 8, 14, 2, 10, 20, 9 };
public static void main(String[] args) {
// commonInsertSort();
binaryInsertSort();
display();
}
// 普通插入
public static void commonInsertSort() {
int count = a.length;
for (int i = 0; i < count; i++) {
int value = a[i];
int j = i - 1;
while (j >= 0 && a[j] > value) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = value;
}
}
// 二分法插入
public static void binaryInsertSort() {
int count = a.length;
int insertValue;
for (int i = 0; i < count; i++) {
int start = 0;
int end = i - 1;
int mid;
insertValue = a[i];
while (start <= end) {
mid = start + (end - start) / 2;
if (insertValue > a[mid]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
for (int k = i; k > start; k--) {
a[k] = a[k - 1];
}
a[start] = insertValue;
}
}
public static void display() {
int count = a.length;
for (int i = 0; i < count; i++) {
System.out.print(a[i] + " ");
}
System.out.println("");
}
}
image.png
2
次,以此类推,最后一趟最多,比较N - 1
次。因此是 N * (N - 1) / 2
。然而在每一趟排序发现插入点之前,平均只有全体数据项的一半进行了比较,我们除以2
就是N * (N - 1) / 4
。while
循环的条件总为假,所以它变成了外层循环中的一个简单的语句,执行 N - 1
次。在这种情况下,算法运行时间只需要O(N)
的时间。如果数据基本有序,插入排序几乎只需要O(N)
的时间。最近养着了白天睡觉,晚上写代码的习惯,于是乎成了一只特立独行的猪了。生活作息不规律,这是病,该治一治了。还是那一句话,勿以善小而不为。