黑马程序员技术交流社区

标题: 排序效率问题 [打印本页]
作者: 雪人    时间: 2013-10-13 03:06
标题: 排序效率问题
本帖最后由 雪人 于 2013-10-13 11:32 编辑

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

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

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

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

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

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

作者: 枫儿    时间: 2013-10-13 08:21
效率差排序在比较的次数以及交换的频率比插入排序要多
作者: 张运    时间: 2013-10-13 09:09
冒泡排序：
对于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）的时间，插入排序对于基本有序的数据是一个简单有效的方法。
作者: 雪人    时间: 2013-10-13 11:31
张运 发表于 2013-10-13 09:09
冒泡排序：
对于n个数据的数组，共进行n-1趟排序，第一趟排序中有n-1次比较，第二趟有n-2次比较，依次类推 ...

神回复...NB...!!



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2