为什么实际上插入排序比冒泡排序和堆排序快？
我已经在链接中看到了(http://bigocheatsheet.com/)插入排序的复杂性与冒泡排序相同，堆排序也优于这两种排序。但是，当我创建一个示例程序并比较插入排序所花费的时间时，我感到难以置信。
类用于测试排序算法。
public class TestSorts {
public static void main(String[] args) {
System.out.println("starting");
Calendar startInstance = null;
Calendar endInstance = null;
//Getting the array to sort
startInstance= Calendar.getInstance();
//int[] arrayToSort = ArrayClass.getArray(1000);
int[] arrayToSort = ArrayClass.getWorstArray(10000000);
endInstance= Calendar.getInstance();
long timeTakenToGetArray = endInstance.getTimeInMillis()- startInstance.getTimeInMillis();
System.out.println("StartTime : "+startInstance.getTimeInMillis());
System.out.println("EndTime : "+endInstance.getTimeInMillis());
System.out.println("TimeTakenToGetArray : "+timeTakenToGetArray);
//Bubble Sort
startInstance= Calendar.getInstance();
int[] bubbleSorted = BubbleSort.sort(arrayToSort);
endInstance= Calendar.getInstance();
long timeTakenBubble = endInstance.getTimeInMillis() - startInstance.getTimeInMillis();
System.out.println("StartTime : "+startInstance.getTimeInMillis());
System.out.println("EndTime : "+endInstance.getTimeInMillis());
System.out.println("Bubble : "+timeTakenBubble);
//InsertionSort
startInstance= Calendar.getInstance();
int[] insertionSorted = InsertionSort.sort(arrayToSort);
endInstance= Calendar.getInstance();
long timeTakenInsertion = endInstance.getTimeInMillis() - startInstance.getTimeInMillis();
System.out.println("StartTime : "+startInstance.getTimeInMillis());
System.out.println("EndTime : "+endInstance.getTimeInMillis());
System.out.println("Insertion : "+timeTakenInsertion);
//HeapSort
startInstance= Calendar.getInstance();
int[] heapSorted = HeapSort.sort(arrayToSort);
endInstance= Calendar.getInstance();
long timeTakenHeap = endInstance.getTimeInMillis() - startInstance.getTimeInMillis();
System.out.println("StartTime : "+startInstance.getTimeInMillis());
System.out.println("EndTime : "+endInstance.getTimeInMillis());
System.out.println("Heap : "+timeTakenHeap);
startInstance= Calendar.getInstance();
arraysAreEqual(bubbleSorted, insertionSorted, heapSorted);
endInstance= Calendar.getInstance();
long timeTakenToCompare = endInstance.getTimeInMillis() - startInstance.getTimeInMillis();
System.out.println("StartTime : "+startInstance.getTimeInMillis());
System.out.println("EndTime : "+endInstance.getTimeInMillis());
System.out.println("TimeTakenToCompare : "+timeTakenToCompare);
}
//Method to compare whether the sorted arrays are equal
static void arraysAreEqual(int[] bubbleSorted,int[] insertionSorted,int[] heapSorted)
{
for(int i =0;i<bubbleSorted.length;i++)
{
if((bubbleSorted[i]!=insertionSorted[i])||(heapSorted[i]!=insertionSorted[i])||(heapSorted[i]!=bubbleSorted[i]))
{
System.out.println("Bubble : "+bubbleSorted[i]);
System.out.println("Insertion : "+insertionSorted[i]);
System.out.println("Heap : "+heapSorted[i]);
}
}
}
}
泡泡排序类
public class BubbleSort {
static int[] sort(int[] arrayToSort)
{
int length = arrayToSort.length;
for(int i = 0;i<length;i++)
{
for(int j = i+1;j<length;j++)
{
if(arrayToSort[i]>arrayToSort[j])
{
arrayToSort[i]+=arrayToSort[j];
arrayToSort[j] = arrayToSort[i] - arrayToSort[j];
arrayToSort[i] = arrayToSort[i] - arrayToSort[j];
}
}
}
return arrayToSort;
}
}
用于插入排序的类
public class InsertionSort {
static int[] sort(int[] arrayToSort)
{
for (int i = 0; i < arrayToSort.length; i++) {
int value = arrayToSort[i];
int j = i - 1;
while (j >= 0 && arrayToSort[j] > value) {
arrayToSort[j + 1] = arrayToSort[j];
j = j - 1;
}
arrayToSort[j + 1] = value;
}
return arrayToSort;
}
}
堆排序类
public class HeapSort {
static int a[];
static int[] sort(int[] arrayToSort)
{
a = arrayToSort;
heapsort();
return a;
}
static void heapsort()
{
int size = a.length;
maxHeapify(size);
for(int i =a.length-1;i>=1;i--)
{
swap(0,i);
size--;
maxHeapify(size);
}
}
static void maxHeapify(int size)
{
for(int i =size/2-1;i>=0;i--)
{
heapify(i,size);
}
}
static void heapify(int i,int size)
{
int left = 2*i+1;
int right = 2*i+2;
int max = i;
if(left<size&&a[left]>a[i])
{
max = left;
}
if(right<size&&a[right]>a[max])
{
max = right;
}
if(max!=i)
{
swap(i,max);
heapify(max,size);
}
}
static void swap(int i,int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
用于创建数组的类
import java.util.Random;
public class ArrayClass {
public static int[] getArray(int size)
{
int array[] = new int[size];
for(int i =0;i<size;i++)
{
int s = randomInt(10,size);
array[i] = s;
}
return array;
}
private static int randomInt(int min,int max)
{
Random rn = new Random();
int randomNumber = rn.nextInt((max - min) + 1) + min;
return randomNumber;
}
public static int[] getBestArray(int size)
{
int array[] = new int[size];
for(int i =0;i<size;i++)
{
array[i]=i+1;
}
return array;
}
public static int[] getWorstArray(int size)
{
int array[] = new int[size];
for(int i =size-1;i>0;i--)
{
array[i]=i;
}
return array;
}
}
我尝试了所有的情况，比如最好的情况、最坏的情况和一般情况。但在所有情况下，插入排序都比冒泡排序和堆排序快得多。理论上，堆排序在最坏的情况下应该是最好的。
当我使用100000作为最坏情况场景的输入时，请查找以下测试结果。
starting
StartTime : 1413470225347
EndTime : 1413470225362
TimeTakenToGetArray : 15
StartTime : 1413470225362
EndTime : 1413470226894
Bubble : 1532
StartTime : 1413470226894
EndTime : 1413470226896
Insertion : 2
StartTime : 1413470226896
EndTime : 1413470233474
Heap : 6578
StartTime : 1413470233474
EndTime : 1413470233488
TimeTakenToCompare : 14
你能告诉我为什么插入排序比堆排序输出更快吗？
共有3个答案
对于小列表，插入排序可以比其他排序更快，因为它们在第一次迭代（循环）中将每个项放在正确的位置。让它慢下来的是把所有的东西都转移到插入的方式上。这就是为什么名单必须很小。
排序方法实际上是对原始数组进行排序，对于已经排序的列表，InsertionSort是O（n）。由于您首先执行BubbleSort，因此您给了InsertionSort一个不公平的优势。
为了进行更公平的比较，您应该制作原始数组的相同副本（在计时之外），并为每个排序例程提供一个单独的副本。这样你就可以用相同的输入进行正面比较。
有几个bug：
>
您的BubbleSort对数组进行排序（就位！），然后将相同的数组传递给下一个方法（InsertionSort）。
getWorstArray正在返回排序数组。在另一个方向运行循环不会改变元素的顺序。不管怎么说，您使用的是一个角落案例（排序、反向排序，无所谓），您的结果将有偏差。
好的BubbleSort具有提前终止（如果在扫描过程中没有进行交换，则进行排序）。
在这一点上，我会质疑代码的其余部分。bug通常以集群形式出现（糟糕的一天，没有经验的程序员，…）。检查更多的bug。做单元测试。
-
本文向大家介绍ruby实现的插入排序和冒泡排序算法，包括了ruby实现的插入排序和冒泡排序算法的使用技巧和注意事项，需要的朋友参考一下 1、插入排序 2、冒泡排序
-
冒泡排序 from typing import List """ 核心思想是循环length-1次，每次循序找出最大或者最小的一个数，每次比较相邻的两个数，如果大或者小就交换位置，每一次循环可以比较当次最大的一个数。 例如 3, 10, -1, 20,8 - 第一次循环 1. 指针下移指向 3 3和10比较 不交换 3 10 -1 20 8 2. 指针下移指向 10 10>-1 交换
-
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位
-
1. 前言 本节内容是排序算法系列之一：冒泡排序，主要讲解了冒泡排序的主体思路，选取了一个待排序的数字列表对冒泡排序算法进行了演示，给出了冒泡排序算法的 Java 代码实现，帮助大家可以更好地理解冒泡排序算法。 2. 什么是冒泡排序？ 冒泡排序（Bubble Sort），是计算机科学与技术领域中较为简单的一种排序算法。 它重复地遍历要排序的序列，会依次比较两个相邻的元素，如果发现两个相邻的元素顺序
-
冒泡排序需要多次遍历列表。它比较相邻的项并交换那些无序的项。每次遍历列表将下一个最大的值放在其正确的位置。实质上，每个项 冒泡 到它所属的位置。 Figure 1 展示了冒泡排序的第一次遍历。阴影项正在比较它们是否乱序。如果在列表中有 n 个项目，则第一遍有 n-1 个项需要比较。重要的是要注意，一旦列表中的最大值是一个对的一部分，它将不断地被移动，直到遍历完成。 Figure 1 在第二次遍历的