- 浏览: 108790 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (75)
- JVM (22)
- 数据结构 (11)
- java 基础 (16)
- gc (6)
- jmock (1)
- Google (2)
- MapReduce (1)
- Memory (2)
- 算法 (2)
- cglib (1)
- jdk (3)
- 虚拟机 (3)
- 安全 (2)
- 多线程 (1)
- 工作 (1)
- 生活 (1)
- MongoDB (2)
- Hadoop (4)
- HDFS (2)
- cms (2)
- Spring (1)
- 网络协议 (1)
- GitHub (1)
- MYSQL 调优和使用必读(转) (1)
- 分布式 (2)
- Big Data (0)
- 技术Blog (1)
- Hbase (2)
- Zookeeper (1)
- paper (0)
最新评论
-
lzc_java:
Java线程安全兼谈DCL -
select*from爱:
it's nice
IT业薪水大揭秘
转载自 ---- http://yiyickf.iteye.com/blog/1047010
先推荐一篇关于排序算法的文章:http://www.cppblog.com/guogangj/archive/2009/11/13/100876.html
本文思路部分来源于上篇文章,但测得的结果似乎不大相同,不知是因为java的缘故还是因为我算法的缘故,欢迎拍砖。
复习排序,顺便比下各种算法的速度,榜单如下:
1、冒泡排序
2、简单选择排序
3、直接插入排序
4、折半插入排序
5、希尔排序
6、堆排序
7、归并排序
8、快速排序
当然这是慢速排行,哈哈~~
直接上图:单位毫秒
冒泡排序 |
简单选择排序 |
直接插入排序 |
折半插入排序 |
希尔排序 |
堆排序 |
归并排序 |
快速排序 |
|
10000 个 |
1578 |
1250 |
672 |
250 |
0 |
15 |
16 |
0 |
15000 个 |
3453 |
2765 |
1563 |
531 |
16 |
15 |
16 |
0 |
20000 个 |
6140 |
4547 |
2453 |
828 |
16 |
16 |
15 |
16 |
25000 个 |
10079 |
7171 |
3969 |
1313 |
31 |
16 |
15 |
16 |
30000 个 |
14641 |
10313 |
5578 |
1906 |
31 |
31 |
16 |
31 |
35000 个 |
20141 |
14328 |
7890 |
2563 |
31 |
31 |
32 |
15 |
40000 个 |
25766 |
18359 |
10094 |
3422 |
47 |
31 |
31 |
32 |
45000 个 |
32469 |
24063 |
13062 |
4359 |
47 |
47 |
31 |
47 |
由于"希尔排序","堆排序","归并排序","快速排序"太快,以至于在上图几乎是条直线,故有了下面转为他们准备的加强版
数量 |
希尔排序 |
堆排序 |
归并排序 |
快速排序 |
100000 个 |
172 |
140 |
110 |
93 |
200000 个 |
469 |
406 |
235 |
234 |
300000 个 |
812 |
703 |
422 |
375 |
400000 个 |
1125 |
1031 |
516 |
531 |
500000 个 |
1406 |
1282 |
719 |
656 |
600000 个 |
1828 |
1703 |
860 |
859 |
700000 个 |
2531 |
2063 |
1000 |
968 |
800000 个 |
2735 |
2453 |
1140 |
1188 |
900000 个 |
3047 |
2843 |
1391 |
1266 |
1000000 个 |
3375 |
3187 |
1516 |
1422 |
1100000 个 |
3922 |
3500 |
1625 |
1609 |
1200000 个 |
4421 |
3954 |
1969 |
1812 |
1300000 个 |
4797 |
4422 |
2000 |
1953 |
1400000 个 |
5391 |
4797 |
2547 |
2094 |
1500000 个 |
5437 |
5219 |
2625 |
2328 |
1600000 个 |
6203 |
5546 |
2469 |
2485 |
1700000 个 |
6532 |
5953 |
2844 |
2672 |
1800000 个 |
7125 |
6421 |
2984 |
2844 |
补上代码:
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.List;
- /**
- * 插入排序:直接插入排序、折半插入排序和系尔排序
- * 交换排序:冒泡排序和快速排序
- * 选择排序:简单选择排序和堆排序
- * 归并排序:归并排序
- *
- * 基本思想
- * 插入排序:将第N个记录插入到前面(N-1)个有序的记录当中。
- * 交换排序:按照某种顺序比较两个记录的关键字大小,然后根据需要交换两个记录的位置。
- * 选择排序:根据某种方法选择一个关键字最大的记录或者关键字最小的记录,放到适当的位置。
- *
- * 排序方法比较
- * 排序方法 平均时间 最坏时间 辅助存储
- * 直接插入排序 O(N2) O(N2) O(1)
- * 起泡排序 O(N2) O(N2) O(1)
- * 快速排序 O(Nlog2N) O(N2) O(Nlog2N)
- * 简单选择排序 O(N2) O(N2) O(1)
- * 堆排序 O(Nlog2N) O(Nlog2N) O(1)
- * 归并排序 O(Nlog2N) O(Nlog2N) O(n)
- * 基数排序 O(d(n+radix)) O(d(n+radix)) O(radix)
- *
- *
- *
- * @author Administrator
- *
- */
- public class SortTest {
- public static void main(String[] args) throws Exception {
- //测试排序是否正确
- //String[] testErr=new String[]{"冒泡排序","简单选择排序","直接插入排序","折半插入排序","系尔排序","堆排序","归并排序","快速排序"};
- //new SortTest().testErr(testErr);
- //排序1(全部)
- String[] strs=new String[]{ "冒泡排序" , "简单选择排序" , "直接插入排序" , "折半插入排序" , "希尔排序" , "堆排序" , "归并排序" , "快速排序" };
- new SortTest().test(strs, 10000 , 50000 , 5000 );
- //排序2(加强)
- String[] strs2=new String[]{ "希尔排序" , "堆排序" , "归并排序" , "快速排序" };
- new SortTest().test(strs2, 100000 , 1900000 , 100000 );
- }
- private void testErr(String[] strings) throws Exception{
- //System.out.println(Arrays.toString(old));
- System.out.println(Arrays.toString(strings));
- Number[] old=getRundom(50 );
- Integer[] oo={1 , 2 , 3 , 3 , 2 , 21 , 5 , 6 , 7 , 78 , 5 , 65 , 8 , 7 , 6 , 6 , 6 , 6 , 6 , 9 , 56544 , 354 , 32 , 4 , 456 , 8 , 89 ,- 9 , 0 , 3 , 243 ,- 321 , 321 ,- 3 ,- 2 , 21 };
- old=oo;
- for (String s:strings){
- Number[] testNum=Arrays.copyOf(old, old.length);
- long begin=System.currentTimeMillis();
- SortTest.class .getMethod(s, Number[]. class ).invoke( this , (Object)testNum);
- long end=System.currentTimeMillis();
- System.out.println(s+":" +(end-begin)+ "\t" );
- System.out.println(Arrays.toString(testNum));
- }
- System.out.println();
- }
- private void test(String[] strings, long begin, long end, long step) throws Exception{
- System.out.print("数量\t" );
- for (String str:strings){
- System.out.print(str+"\t" );
- }
- System.out.println();
- for ( long i=begin;i<end;i=i+step){
- System.out.print(i+"个\t" );
- Number[] old=getRundom(i);
- for (String s:strings){
- Number[] testNum=Arrays.copyOf(old, old.length);
- long beginTime=System.currentTimeMillis();
- SortTest.class .getMethod(s, Number[]. class ).invoke( this , (Object)testNum);
- long endTime=System.currentTimeMillis();
- System.out.print((endTime-beginTime)+"\t" );
- //System.out.println(Arrays.toString(testNum));
- }
- System.out.println();
- }
- }
- private static Integer[] getRundom( long num) {
- List<Integer> list=new ArrayList<Integer>();
- for ( long i= 0 ;i<num;i++){
- int k;
- if (Math.random()> 0.5 ){
- k=(int )(Math.random()*Integer.MAX_VALUE);
- }else {
- k=(int )(Math.random()*Integer.MIN_VALUE);
- }
- list.add(k);
- }
- return list.toArray( new Integer[list.size()]);
- }
- /**
- * 插入排序————直接插入排序
- * @param data
- */
- public static void 直接插入排序(Number[] data)
- {
- Number tmp=null ;
- for ( int i= 1 ;i<data.length;i++){
- tmp = data[i];
- int j=i- 1 ;
- while (j>= 0 && tmp.doubleValue()<data[j].doubleValue()){
- data[j+1 ]=data[j];
- j--;
- }
- data[j+1 ]=tmp;
- }
- }
- /**
- * 插入排序————折半插入排序
- * @param data
- */
- public static void 折半插入排序(Number[] data)
- {
- Number tmp=null ;
- for ( int i= 1 ;i<data.length;i++){
- tmp = data[i];
- int smallpoint= 0 ;
- int bigpoint=i- 1 ;
- while (bigpoint>=smallpoint){
- int mid=(smallpoint+bigpoint)/ 2 ;
- if (tmp.doubleValue()>data[mid].doubleValue()){
- smallpoint=mid+1 ;
- }else {
- bigpoint=mid-1 ;
- }
- }
- for ( int j=i;j>smallpoint;j--){
- data[j]=data[j-1 ];
- }
- data[bigpoint+1 ]=tmp;
- }
- }
- /**
- * 插入排序————希尔排序
- * @param data
- */
- public static void 希尔排序(Number[] data)
- {
- int span=data.length/ 7 ;
- if (span== 0 )span= 1 ;
- while (span>= 1 ){
- for ( int i= 0 ;i<span;i++){
- for ( int j=i;j<data.length;j=j+span){
- //组内直接插入排序
- int p = j-span;
- Number temp = data[j];
- while ( p >= 0 && data[p].doubleValue() > temp.doubleValue()){
- data[p+span] = data[p];
- p -=span;
- }
- data[p + span] = temp;
- }
- }
- span=span/2 ;
- }
- }
- /**
- * 交换排序————冒泡排序
- *
- * @param data
- */
- public static void 冒泡排序(Number[] data)
- {
- for ( int i = 0 ; i < data.length; i++) {
- //将相邻两个数进行比较,较大的数往后冒泡
- for ( int j = 0 ; j < data.length - i- 1 ; j++) {
- if (data[j].doubleValue()> data[j + 1 ].doubleValue()) {
- //交换相邻两个数
- swap(data, j, j + 1 );
- }
- }
- }
- }
- /**
- * 交换排序————快速排序
- * @param data
- */
- public static void 快速排序(Number[] data)
- {
- QuickSort(data,0 ,data.length- 1 );
- }
- private static void QuickSort(Number[] data, int begin, int end) {
- // System.out.println(begin+":"+end);
- if (begin<end){
- //取中点
- int mid=(begin+end)/ 2 ;
- if (data[end].doubleValue()<data[begin].doubleValue()){
- swap(data, end, begin);
- }
- if (data[end].doubleValue()<data[mid].doubleValue()){
- swap(data, end, mid);
- }
- if (data[mid].doubleValue()<data[begin].doubleValue()){
- swap(data, mid, begin);
- }
- swap(data, mid, begin);
- // System.out.println(Arrays.toString(Arrays.copyOfRange(data, begin, end)) );
- int min=begin+ 1 ;
- int big=end;
- while ( true ){
- while (min<big && data[min].doubleValue()<data[begin].doubleValue()){min++;}
- while (min<big && data[big].doubleValue()>=data[begin].doubleValue()){big--;}
- if (min>=big){
- break ;
- }
- swap(data, min, big);
- }
- if (data[begin].doubleValue()>data[min].doubleValue()){
- swap(data, begin, min);
- }
- if (min> 1 )
- QuickSort(data,begin,min-1 );
- //if(min<end)
- QuickSort(data,min,end);
- }
- }
- /**
- * 选择排序————简单选择排序
- * @param data
- */
- public static void 简单选择排序(Number[] data)
- {
- for ( int i = 0 ; i < data.length- 1 ; i++) {
- int smallPoint=i;
- for ( int j = i+ 1 ; j < data.length; j++) {
- if (data[smallPoint].doubleValue()> data[j].doubleValue()) {
- smallPoint=j;
- }
- }
- swap(data, i, smallPoint);
- }
- }
- /**
- * 选择排序————堆排序
- * @param data
- */
- public static void 堆排序(Number[] data)
- {
- int n = data.length;
- for ( int i=n/ 2 ;i>= 0 ;i--){
- keepHeap(data, n, i);
- }
- while (n > 0 ) {
- swap(data, 0 , n- 1 );
- keepHeap(data, --n, 0 );
- }
- }
- private static void keepHeap(Number[] a, int n, int i) {
- Number x = a[i];
- int j = 2 * i + 1 ;
- while (j <= n - 1 ) {
- if (j < n - 1 && a[j].doubleValue() < a[j + 1 ].doubleValue())
- ++j;
- if (a[j].doubleValue() > x.doubleValue()) {
- a[i] = a[j];
- i = j;
- j = 2 * i ;
- } else {
- break ;
- }
- }
- a[i] = x;
- }
- /**
- * 归并排序法————归并排序
- * @param data
- */
- public static void 归并排序(Number[] data)
- {
- Number[] result = merge_sort(data,0 ,data.length- 1 );
- for ( int i= 0 ;i<result.length;i++){
- data[i]=result[i];
- }
- }
- private static Number[] merge_sort(Number[] array, int start, int end){
- Number[] result = new Number[end-start+ 1 ];
- if (start< end){
- int mid= (start+end)/ 2 ;
- Number[] left= merge_sort(array, start, mid);
- Number[] right = merge_sort(array, mid+1 , end);
- result= merge(left,right);
- } else if (start == end) {
- result[0 ] = array[start];
- return result;
- }
- return result;
- }
- private static Number[] merge(Number[] left, Number[] right) {
- Number[] result = new Number[left.length+right.length];
- int i= 0 ;
- int j= 0 ;
- int k= 0 ;
- while (i< left.length&&j< right.length){
- if (left[i].doubleValue()< right[j].doubleValue()){
- result[k++] = left[i++];
- }else {
- result[k++] = right[j++];
- }
- }
- while (i< left.length){
- result[k++] = left[i++];
- }
- while (j< right.length) {
- result[k++]= right[j++];
- }
- return result;
- }
- /**
- * 交换数组中指定的两元素的位置
- * @param data
- * @param x
- * @param y
- */
- private static void swap(Number[] data, int x, int y) {
- Number temp = data[x];
- data[x] = data[y];
- data[y] = temp;
- }
-
}
发表评论
-
哈希表
2013-05-03 11:03 1629转载自 ---- http://blog.java ... -
Java 链表
2013-01-18 15:27 970转载自 ---- http://359094247.iteye ... -
哈夫曼与压缩
2013-01-18 15:24 907转载自 ---- http://359094247.iteye ... -
Java基础 之软引用、弱引用、虚引用 ·[转载]
2012-06-07 18:13 11391、概述 在JDK1.2以前的版本中,当一个对象不 ... -
Java中常用的加密方法(JDK)
2012-03-30 16:35 10932转载自 ---- http://www.iteye.co ... -
java的内存管理
2012-03-29 16:59 1601转载自 ---- http://yangzhiyong77 ... -
Java栈与堆
2011-10-10 16:39 865转载自 ---- http://mylir.i ... -
Java内存泄露的理解与解决
2011-10-10 16:38 965转载自 ---- http://henryyang.itey ... -
JVM问题诊断常用命令:jinfo,jmap,jstack
2011-08-18 11:19 1557转载自 ---- http://singleant.iteye ... -
Java HotSpot 性能引擎架构
2011-08-17 17:04 1037转载自 ---- http://lifethink ... -
Java线程安全兼谈DCL
2011-08-17 17:02 1542转载自 ---- http://www.iteye.com/t ... -
用happen-before规则重新审视DCL
2011-08-17 17:00 823转载自 ---- http://lifethink ... -
CMS gc实践总结(转载)
2011-08-10 15:09 1068首先感谢阿宝 同学的帮助,我才对这个gc算法的调整有 ... -
GC机制小结
2011-08-10 14:07 719转载自 ---- http://zhangjian ... -
Java内存模型(JMM) 资料整理(转载)
2011-08-10 13:35 981转载自 ---- http://blog.csdn.net/o ... -
ClassLoader解析(转载)
2011-08-05 14:35 970转载自 ---- http://shangjava ... -
深入理解java的finalize
2011-08-03 17:01 732转载自 ---- http://zhang-xzhi-x ... -
深入理解java的clone
2011-08-03 17:01 767转载自 ---- http://zhang-xzh ... -
(转)B树、B-树、B+树、B*树都是什么
2011-08-03 16:55 704B 树 即二叉搜 ... -
(转)深入研究B树索引(五)续
2011-08-03 16:53 8735.3 重建 B 树索引对于查询性能的影响 ...
相关推荐
堆排序算法 java
本文将详细探讨标题所提及的几种排序算法:合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序,并结合Java语言的实现进行解析。 1. **合并排序(Merge Sort)**: 合并排序是一种基于分治策略的排序算法...
本资源提供了Java语言实现的五种经典排序算法:冒泡排序、快速排序、插入排序、选择排序以及测试程序。下面将详细介绍这四种排序算法的原理、特点以及Java实现的关键点。 1. **冒泡排序**: 冒泡排序是一种简单...
"9大排序算法java版"这个压缩包可能包含了以下九种经典的排序算法的Java实现: 1. 冒泡排序(Bubble Sort):这是一种简单的排序算法,通过重复遍历待排序的数组,依次比较相邻元素并交换位置来完成排序。时间...
本压缩包"常见的七大排序算法Java实现.zip"包含了七种经典的排序算法在Java语言中的实现。尽管文件列表中并未明确列出每种排序算法的名称,但根据常规,这七大排序算法可能包括冒泡排序、插入排序、选择排序、快速...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer),通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的...
"快速排序算法java代码" 快速排序算法是由Tony Hoare在1960年提出的一种排序算法,它的平均时间复杂度为O(n log n),是目前最快的排序算法之一。下面我们将详细地讲解快速排序算法的java代码实现。 快速排序算法的...
### 七种排序算法Java版 #### 内容概述 本文档主要介绍了七种常见的排序算法在Java中的实现,包括冒泡排序、选择排序、快速排序、插入排序、希尔排序、归并排序以及堆排序。这些算法是计算机科学中基础且重要的组成...
**基于Java语言十大经典排序算法** 排序算法是计算机科学中不可或缺的一部分,特别是在数据处理和算法设计领域。在Java编程中,理解并掌握各种排序算法能够帮助开发者提高代码效率,优化性能。以下是Java语言中十大...
### Java版本排序算法详解 #### 插入排序 插入排序是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。在Java中,我们可以创建一个`...
本文将详细分析七种常见的Java排序算法:冒泡排序、选择排序、快速排序、插入排序、希尔排序、归并排序和堆排序,并探讨它们在不同条件下的性能表现。 1. **冒泡排序**: - 时间复杂度:平均和最坏情况下都是O(n^2...
【IT面试笔试中的排序算法Java实现】 在IT面试和笔试中,掌握各种排序算法的实现是必不可少的技能。本文将详细介绍几种经典的排序算法,并提供Java语言的实现代码,包括冒泡排序、插入排序、选择排序和快速排序。...
除了插入排序和希尔排序,压缩包中还可能包含了其他几种常见的排序算法的Java实现,如冒泡排序、快速排序、选择排序、归并排序和堆排序等。每种排序算法都有其特定的适用场景和性能特点。例如,冒泡排序虽然简单,但...
在编程领域,排序算法是数据结构与算法学习中的基础部分,尤其在JAVA中,掌握不同的排序算法对于提高程序效率至关重要。本节将深入探讨两种常见的排序算法:冒泡排序和快速排序。 首先,我们来详细讲解冒泡排序。...
本资源提供的Java实现包括了三种线性排序算法:桶排序(Bucket Sort)、基数排序(Radix Sort)和计数排序(Counting Sort)。这三种算法在特定条件下可以达到线性的平均或最好时间复杂度,效率相对较高。 1. **桶...
在编程领域,排序算法是计算机科学的基础之一,尤其在Java这样的多用途编程语言中,对数据进行高效排序是至关重要的。本资源包含了七大经典排序算法的Java实现,这对于学习、复习或面试准备都非常有价值。接下来,...
在编程领域,排序算法是计算机科学中的核心概念,特别是在Java这样的高级编程语言中。本文将深入探讨Java中常见的几种排序算法,包括它们的工作原理、优缺点以及如何在实际编程中应用。 首先,我们来看`BubbleSort...
java排序算法java排序算法插入选择冒泡java排序算法插入选择冒泡
### Java 实现数据结构常见排序算法及详解 #### 排序算法概述 排序算法是计算机科学中的基础概念之一,主要用于将一系列数据按照特定规则进行排列。根据数据处理方式的不同,排序算法大致分为两大类:比较排序与非...
### Java常用的七大排序算法 #### 1. 插入排序算法 插入排序是一种简单直观的排序算法。它的基本思想是:对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 - **算法步骤**: 1. 将第一待排序...