Collections类里自带有sort()方法可以对给定的集合排序,今天我就要拿最简单的冒泡排序来跟他PK,看谁快!废话不多说,上代码:
首先是冒泡排序:
public void sort(Integer[] arr)
{
long start=System.nanoTime();
int lastChgIndex=arr.length-1;
int poz=0;
while(lastChgIndex>0)
{
poz=0;
for(int j=0;j<lastChgIndex;j++)
{
if(arr[j]>arr[j+1])
{
int temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
poz=j;
}
}
lastChgIndex=poz;
}
long end=System.nanoTime();
printTimeCost(end-start);
}
然后是collections.sort()
public void sort(Integer[] arr) {
List<Integer> list=Arrays.asList(arr);
long start=System.nanoTime();
Collections.sort(list);
long end=System.nanoTime();
printTimeCost(end-start);
}
测试数据集:new Integer[]{1,2,3,4,5,6,7,8,10,20,18,15,17,30}
冒泡排序:18884ns
collections.sort() 171598ns
为什么效率差距如此之大:莫非java开发者写的排序算法还比不上冒泡排序? 其实最根本的原因在于两种排序算法的原理上的差别,对于给定的数据集,如果大部分是排好序甚至本身就是有序的,使用冒泡排序算法还更快。那么,collections.sort()采用的是什么算法呢?阅读源码后,注释告诉我们是merged sort(归并排序),归并排序中无论数据集是否大致有序,都是需要进行大量的归并操作的,这其中包括元素的比较和移动。虽然归并排序具有O(nlogn)的效率,好于冒泡的O(n²),但是对于比较极端的情况,我们需要另外单独考虑,这一切也当然是建立在对于两种算法实现原理上的熟悉上,而不是仅仅记得他们的时间复杂度。
分享到:
相关推荐
以上三个知识点总结了关于 Java 排序的一些基本应用,包括基础的冒泡排序算法、使用标准库 `Collections.sort()` 进行排序以及使用 `RuleBasedCollator` 实现国际化排序等。这些技术对于编写高效、可维护的 Java ...
在编程领域,排序是至关重要的一个主题...同时,理解这些基础排序算法也有助于学习更高级的排序算法,如归并排序、希尔排序等,以及现代库中如Java的`Collections.sort()`和`Arrays.sort()`等内置排序方法的工作原理。
在计算机科学中,排序算法是数据处理的重要...在Java中,这些排序算法可以通过Collections.sort()方法或者自定义Comparator来实现,方便快捷。通过理解和掌握这些算法,开发者可以更好地优化代码性能,提升程序效率。
java List 排序之冒泡排序实例代码 Java List 排序之冒泡排序实例代码是 Java 语言中实现 List 排序的一种方法。该方法主要使用冒泡排序算法对 List 集合中的元素进行排序。 1.Collections.sort() 排序 ...
1. **冒泡排序**:这是一种简单的排序算法,通过不断交换相邻的不正确顺序元素来达到排序的目的。虽然效率较低,但对于小规模数据,它易于理解和实现。 2. **选择排序**:每次从未排序的元素中选取最小(或最大)的...
理解各种排序算法的原理,如冒泡排序、插入排序、选择排序、归并排序、快速排序等,有助于在特定场景下选择最合适的排序方法。 13. 内存与空间复杂度 在考虑排序效率的同时,也要关注其内存占用,特别是在处理大...
这里有四种常见的排序算法,它们分别是冒泡排序、插入排序、选择排序以及Java内置的`Arrays.sort()`或`Collections.sort()`方法,这些方法通常利用了更高效的排序算法,如快速排序、归并排序等。下面我们将对这四种...
1. **冒泡排序**:冒泡排序是一种简单的排序算法,通过重复遍历数组,比较相邻元素并交换位置来完成排序。C#实现冒泡排序时,通常会用到嵌套循环结构,时间复杂度为O(n^2)。 2. **选择排序**:选择排序每次从待排序...
4. **冒泡排序、选择排序、希尔排序等**:这些简单的排序算法在Java中并不常用,因为它们的时间复杂度相对较高,但对于理解排序算法原理来说很有价值。例如,冒泡排序通过重复遍历数组,每次比较相邻元素并交换,...
在面试中,可能会要求手写一个基本的排序算法,如冒泡排序或选择排序,以此来评估应聘者对排序算法原理的理解。例如,冒泡排序的基本思路是从第一个元素开始,比较相邻元素,并交换位置直到整个数组排序完成。 ####...
2. **冒泡排序(Bubble Sort)**:冒泡排序也称为肥皂泡排序,它通过不断地比较相邻元素并交换(如果需要)来逐渐将最大(或最小)元素“冒泡”到数组的一端。在这个Java版本中,外层循环控制总的遍历次数,内层循环...
1. **冒泡排序(Bubble Sort)** 冒泡排序是一种简单直观的排序算法,它重复地遍历待排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该...
例如,在快速排序或冒泡排序中,`Collections.swap()`可以简洁地完成元素交换操作。 4. **线程安全的集合** Collections API 提供了一些线程安全的集合实现,如`ConcurrentHashMap`, `CopyOnWriteArrayList`, 和 `...
常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。每种排序算法都有其优缺点,选择合适的排序算法取决于具体的应用场景。 在 Java 中,对列表进行排序的最快方法是使用Collections....
1. 冒泡排序(Bubble Sort) 冒泡排序是一种简单直观的排序算法,其主要原理是通过重复遍历待排序的数据列表,依次比较相邻的元素,如果顺序错误就交换位置。在每次遍历时,最大的元素会逐渐“冒泡”到列表末尾。...
对于小规模数据排序,可以选择时间复杂度为O(n^2)的排序算法,如冒泡排序、插入排序等,这些算法实现简单,但在数据量增大时效率显著下降。对于大规模数据排序,时间复杂度为O(nlogn)的算法将更为高效,常见的有归并...
2. **冒泡排序**(Bubble Sort): 冒泡排序通过比较相邻元素并交换位置来实现排序,重复地遍历待排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要...
冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成...
它涉及到将一组元素按照特定的顺序排列,常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序等。本篇文章主要探讨Java中的排序方法,以及与之相关的工具和技术。 首先,我们来了解几种基本的排序...
1. 冒泡排序(Bubble Sort) 冒泡排序是最简单的排序算法之一,通过重复遍历数组,比较相邻元素并交换位置来实现排序。它的效率较低,时间复杂度为O(n²)。在Java中,你可以用两个for循环实现冒泡排序。 2. 选择...