java排序算法比较

Question

我有一个项目，我需要测试3种排序算法，找出其中哪一种是插入排序、冒泡排序、选择排序。我无法找到这些方法，所以我使用Java中的秒表进行测试。我创建了3个数组

int[] arr = new int[100000]; //This array is sorted
int[] randomarr = new int[100000]; //This array is random
int[] reversearr = new int[100000]; //This array is reversed

我测试了这些算法，以下是我的结果：

- sort1 

 Sorted array took 11 seconds--Reversed array took 13 seconds--Random array took 24 seconds

- sort2

 Sorted array took 12 second--Reversed array took 12 seconds--Random array took 10 seconds

- sort3

 Sorted array took 1 millisecond--Reversed array took 12 seconds--Random array took 4 seconds

我非常确定sort3是插入排序，因为它比排序数组中的其他排序更快。但我对sort1和sort2感到困惑。冒泡排序的最佳情况是O（n），插入排序的最佳情况也是O（n），但当我检查结果时，插入排序的最佳情况是1毫秒，所以冒泡排序的最佳情况也应该是1毫秒？我如何比较它们

Answer 1

因此，您显然必须通过检查排序各种数组所需的时间来确定哪个是哪个

下面是每种算法的一些细节（列为最佳、平均、最差、最佳空间）

因此，通过将不同大小的排序列表传递给算法，并查看需要多长时间，可以快速确定哪一个是选择排序。二次作用的是selection sort

然后，要在bubble sort和insertion sort之间做出决定，您需要更深入地了解算法的工作原理bubble sort有一个亲切命名的问题dinosaurs and turtles，也就是说，开头的大元素处理得很快，但结尾的小元素处理得效率很低。然后，您可以尝试用排序列表分析剩下的两个算法（bubble和insertion），最后一个元素是最小的，然后看看它们是如何工作的。性能更好的是插入排序

如果使用这些算法的简单版本，在不同大小的阵列上进行这些测试，我会得到以下结果：

根据以上信息，我知道sort1是冒泡排序，sort3是选择排序，sort2是插入排序