A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 雪人 中级黑马   /  2013-10-13 03:06  /  1306 人查看  /  3 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 雪人 于 2013-10-13 11:32 编辑

排序的效率问题~
小弟不才,只会三种排序(选择排序,冒泡排序,插入排序),也不知道哪种排序效率最高.于是就做个小测试.
  1. public class Test3 {

  2.         public static void main(String[] args) {
  3.                
  4.                 long start = System.currentTimeMillis();
  5.                 for(int i=0;i<10000000;i++){
  6.                         int[] arr = { 122, 342, 53, 14, 333, 523, 888, 77, 1, 664 };
  7. //                        insertSort(arr);
  8. //                        bubbleSort(arr);
  9. //                        selectSort(arr);
  10.                 }
  11.                 System.out.println(System.currentTimeMillis() - start);
  12.         }

  13.         /**
  14.          * 插入排序
  15.          */
  16.         static void insertSort(int[] arr) {
  17.                 for (int i = 1; i < arr.length; i++) {
  18.                         int pos = i;
  19.                         while (pos > 0 && arr[pos] < arr[pos - 1]) {
  20.                                 int temp = arr[pos];
  21.                                 arr[pos] = arr[pos - 1];
  22.                                 arr[pos - 1] = temp;
  23.                                 pos--;
  24.                         }
  25.                 }
  26.         }

  27.         /**
  28.          * 冒泡排序
  29.          */
  30.         static void bubbleSort(int[] arr) {
  31.                 for (int i = 0; i < arr.length - 1; i++) {
  32.                         for (int j = 0; j < arr.length - 1 - i; j++) {
  33.                                 if (arr[j] > arr[j + 1]) {
  34.                                         int temp = arr[j];
  35.                                         arr[j] = arr[j + 1];
  36.                                         arr[j + 1] = temp;
  37.                                 }
  38.                         }
  39.                 }
  40.         }

  41.         /**
  42.          * 选择排序
  43.          */
  44.         static void selectSort(int[] arr) {
  45.                 for (int i = 0; i < arr.length - 1; i++)
  46.                 {
  47.                         int pos = i;
  48.                         for (int j = i + 1; j < arr.length; j++) {
  49.                                 if (arr[j] < arr[pos])
  50.                                         pos = j;
  51.                         }
  52.                         int temp = arr[i];
  53.                         arr[i] = arr[pos];
  54.                         arr[pos] = temp;
  55.                 }
  56.         }
  57. }
复制代码
大家可以复制一下,然后打开上面被注掉的方法.测试一下, 经过我多次测试,插入排序速度是最快的.

我不太明白里面的原因...有谁懂???

评分

参与人数 1技术分 +1 收起 理由
杨增坤 + 1

查看全部评分

3 个回复

倒序浏览
效率差排序在比较的次数以及交换的频率比插入排序要多
回复 使用道具 举报
冒泡排序:
对于n个数据的数组,共进行n-1趟排序,第一趟排序中有n-1次比较,第二趟有n-2次比较,依次类推,最后一趟有1次比较
(n-1)+(n-2)...+1 = n *(n-1)/2    总共进行了n*n/2次比较
如果数据是随机的,大概有一半数据需要交换,则交换的次数为n*n/4,在最坏的情况下,即初始是逆序的,每次都需要交换。
交换和比较次数都和n的平方成正比,时间复杂度为O(n*n)

选择排序:
和冒泡排序相比,执行了相同的比较次数n *(n-1)/2,但对于n个数据,只需要少于n次的交换。
时间复杂度为O(n*n),选择排序比冒泡排序快,因为它进行的交换少的多,当n值较小时,特别是交换的时间大于比较时间,选择排序是相当快

的。

插入排序:
在第一趟排序中,最多比较1次,第二趟最多比较2次,依次类推,最后一趟最多比较n-1次,因此有(n-1)+(n-2)...+1 = n *(n-1)/2,
然而,在每一趟发现插入点之前,平均只有全体数据项的一半真的进行了比较,除以2得到n *(n-1)/4
复制的次数大致等于比较的次数,即n *(n-1)/4,然而,一次复制与一次交换的耗时不同,所以,相对于随机数据,这个算法比冒泡排序快一倍

,比选择排序略快。
对于基本有序的数据,只需要O(n)的时间,插入排序对于基本有序的数据是一个简单有效的方法。

评分

参与人数 1技术分 +1 收起 理由
周志龙 + 1

查看全部评分

回复 使用道具 举报 1 0
张运 发表于 2013-10-13 09:09
冒泡排序:
对于n个数据的数组,共进行n-1趟排序,第一趟排序中有n-1次比较,第二趟有n-2次比较,依次类推 ...

神回复...NB...!!
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马