这里有一个实证证明，插入排序比冒泡排序更快（对于30个元素，在我的机器上使用Java的附加实现...）。
我运行了附加的代码，并发现冒泡排序平均花费6338.515纳秒，而插入排序只需要3601.0纳秒。
我使用wilcoxon signed test检查了这是否是一个错误，它们实际上应该是相同的 - 但结果低于数值误差范围（有效P_VALUE ~= 0）。
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int j = i;
while (j > 0 && arr[j-1] > arr[j]) {
swap(arr, j, j-1);
j--;
}
}
}
public static void bubbleSort(int[] arr) {
for (int i = 0 ; i < arr.length; i++) {
boolean bool = false;
for (int j = 0; j < arr.length - i ; j++) {
if (j + 1 < arr.length && arr[j] > arr[j+1]) {
bool = true;
swap(arr,j,j+1);
}
}
if (!bool) break;
}
}
public static void main(String... args) throws Exception {
Random r = new Random(1);
int SIZE = 30;
int N = 1000;
int[] arr = new int[SIZE];
int[] millisBubble = new int[N];
int[] millisInsertion = new int[N];
System.out.println("start");
for (int t = 0; t < 100; t++) {
insertionSort(arr);
}
for (int t = 0; t < N; t++) {
arr = generateRandom(r, SIZE);
int[] tempArr = Arrays.copyOf(arr, arr.length);
long start = System.nanoTime();
insertionSort(tempArr);
millisInsertion[t] = (int)(System.nanoTime()-start);
tempArr = Arrays.copyOf(arr, arr.length);
start = System.nanoTime();
bubbleSort(tempArr);
millisBubble[t] = (int)(System.nanoTime()-start);
}
int sum1 = 0;
for (int x : millisBubble) {
System.out.println(x);
sum1 += x;
}
System.out.println("end of bubble. AVG = " + ((double)sum1)/millisBubble.length);
int sum2 = 0;
for (int x : millisInsertion) {
System.out.println(x);
sum2 += x;
}
System.out.println("end of insertion. AVG = " + ((double)sum2)/millisInsertion.length);
System.out.println("bubble took " + ((double)sum1)/millisBubble.length + " while insertion took " + ((double)sum2)/millisBubble.length);
}
private static int[] generateRandom(Random r, int size) {
int[] arr = new int[size];
for (int i = 0 ; i < size; i++)
arr[i] = r.nextInt(size);
return arr;
}
编辑:
(1) 优化冒泡排序（上面已更新）将冒泡排序所需的总时间减少至：6043.806，但不足以产生显著变化。Wilcoxon测试仍然得出结论：插入排序更快。
(2) 我还添加了一个选择排序测试（附带代码）并将其与插入排序进行比较。结果为：选择排序花费了4748.35，而插入排序花费了3540.114。
Wilcoxon的P_VALUE仍然低于数值误差范围（实际上~=0）
使用的选择排序代码:
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length ; i++) {
int min = arr[i];
int minElm = i;
for (int j = i+1; j < arr.length ; j++) {
if (arr[j] < min) {
min = arr[j];
minElm = j;
}
}
swap(arr,i,minElm);
}
}
f(x)=x^2，而g(x)=9999999n log n，那么对于小的n，具有复杂度f(x)的算法将比具有复杂度g(x)的算法更快。渐近符号只保证**存在一个数字n，使得对于所有的m > n，我们都有f(m) > g(m)**。 - Haile