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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 曾经的迷失 中级黑马   /  2014-2-25 08:38  /  1228 人查看  /  7 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

请问,数组排序用哪种方法效率比较高? Arrays.sort()除外。

评分

参与人数 1技术分 +1 收起 理由
zzkang0206 + 1

查看全部评分

7 个回复

倒序浏览
排序算法的分类如下:
1.插入排序(直接插入排序、折半插入排序、希尔排序);
2.交换排序(冒泡泡排序、快速排序);
3.选择排序(直接选择排序、堆排序);
4.归并排序;
5.基数排序。

关于排序方法的选择:
(1)若n较小(如n≤50),可采用直接插入或直接选择排序。
   当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜;
(3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序。

冒泡排序:
         方法:相邻两元素进行比较,如有需要则进行交换,每完成一次循环就将最大元素排在最后(如从小到大排序),下一次循环是将其他的数进行类似操作。
         性能:比较次数O(n[sup]2[/sup]),n[sup]2[/sup]/2;交换次数O(n[sup]2[/sup]),n[sup]2[/sup]/4
直接选择排序法----选择排序的一种
         方法:每一趟从待排序的数据元素中选出最小(或最大)的一个元素, 顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
         性能:比较次数O(n[sup]2[/sup]),n[sup]2[/sup]/2
               交换次数O(n),n
               交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CUP时间多,所以选择排序比冒泡排序快。
               但是N比较大时,比较所需的CPU时间占主要地位,所以这时的性能和冒泡排序差不太多,但毫无疑问肯定要快些。
插入排序:
         方法:将一个记录插入到已排好序的有序表(有可能是空表)中,从而得到一个新的记录数增1的有序表。
         性能:比较次数O(n[sup]2[/sup]),n[sup]2[/sup]/4
               复制次数O(n),n[sup]2[/sup]/4
               比较次数是前两者的一般,而复制所需的CPU时间较交换少,所以性能上比冒泡排序提高一倍多,而比选择排序也要快
快速排序:
         快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。
         步骤为:
         1. 从数列中挑出一个元素,称为 "基准"(pivot),
         2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。
         3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
         递回的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递回下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。


评分

参与人数 1技术分 +1 收起 理由
zzkang0206 + 1

查看全部评分

回复 使用道具 举报
基础视频学习刚学到两个排序方法...
  1. //冒泡法排序
  2. class Bubblesort
  3. {
  4.         public static void main(String args[])
  5.         {
  6.                 int [] arr={5,1,6,4,2,8,9};
  7.                 bubble(arr);
  8.                 printarray(arr);

  9.         }
  10.         public static void bubble(int[] arr)
  11.         {
  12.                 for (int i=0;i<arr.length-1 ;i++ )
  13.                 {
  14.                         for (int y=0;y<arr.length-i-1 ; y++) //让每一次比较的元素减少,-1是为了防止数组角标越界;
  15.                         {
  16.                                 if(arr[y]>arr[y+1])  //相邻两元素相比
  17.                                 {
  18.                                         int temp = 0;
  19.                                         temp = arr[y];
  20.                                         arr[y] = arr[y+1] ;
  21.                                         arr[y+1] = temp;
  22.                                 }
  23.                         }
  24.                 }
  25.         }
  26.         public static void printarray(int[] arr)
  27.         {

  28.                 for (int i=0;i<arr.length ;i++ )
  29.                 {
  30.                         if(i!=arr.length-1)
  31.                         System.out.print(arr[i]+",");                               
  32.                         else
  33.                                 System.out.println(arr[i]);
  34.                 }
  35.         }

  36. }
  37. //选择排序
  38. public class Demo6 {
  39.         public static void main(String[] args) {
  40.                 int []age = {1,2,36,363,56,95,12,32,1232,3263};
  41.                
  42.                 for (int i = 0; i < age.length; i++) {
  43.                         for (int j = i+1; j <= age.length-1; j++) {
  44.                                 if(age[i] > age[j]){
  45.                                         int temp = age[i];
  46.                                         age[i] = age[j];
  47.                                         age[j] = temp;
  48.                                 }
  49.                         }
  50.                 }
  51.                 System.out.println(Arrays.toString(age));
  52.         }
  53. }       
  54. //输出为:[1, 2, 12, 32, 36, 56, 95, 363, 1232, 3263]
复制代码

评分

参与人数 1技术分 +1 收起 理由
何伟超 + 1

查看全部评分

回复 使用道具 举报
本帖最后由 wdtdcm 于 2014-2-25 14:26 编辑

排序的方法还挺多的,最近发现了个非常有意思的视频

直观表现了各种排序的方法.可以看看

[tianchai_youku]XNjIwNTEzMTA0[/tianchai_youku]
虽然排序方法有很多,但是常见的基本的排序方法有四种
1,直接插入排序:当数据表A中每个元素距其最终位置不远,数据表A按关键字值基本有序,可用此方法排序较快。
2,冒泡排序法:将较小的值“上浮”到数组顶部,而较大值“下沉”到数组底部,这种排序技术要比较好几趟,每一趟要比较连续的数组元素对,如果某对数值是按升序排序的(或者这两个值相等),那就保持原样,如果某对数组是按降序排列的,就要交换它们的值。
3,快速排序法:快速排序是对冒泡排序的一种改进。它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
4,直接选择排序法:直接选择排序的作法是:第一趟扫描所有数据,选择其中最小的一个与第一个数据互换;第二趟从第二个数据开始向后扫描,选择最小的与第二个数据互换;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。它比起冒泡排序有一个优点就是不用不断的交换。




我个人觉得,了解这些基本原理花的时间还不算多,但是深入研究还是要花比较多时间了.

点评

这个视频有点意思  发表于 2014-2-26 04:49

评分

参与人数 1技术分 +1 收起 理由
zzkang0206 + 1

查看全部评分

回复 使用道具 举报
据说哈希算法是排序效率最高的一种算法。

  1. <P>package fanqi;</P>
  2. <P>import java.util.HashSet;</P>
  3. <P>import java.util.Iterator;</P>
  4. <P>import java.util.Map.Entry;</P>
  5. <P>import java.util.TreeMap;public class WuZiQi </P>
  6. <P> { </P>
  7. <P>   public static void main(String[] args)</P>
  8. <P>     { </P>
  9. <P>TreeMap<Integer, String> map = new TreeMap<Integer, String>(); </P>
  10. <P>map.put(new Integer(2), "String 2");</P>
  11. <P>map.put(new Integer(1), "String 1"); </P>
  12. <P>map.put(new Integer(3), "String 3"); </P>
  13. <P>map.put(new Integer(6), "String 6"); </P>
  14. <P>map.put(new Integer(5), "String 5");</P>
  15. <P> Iterator<Entry<Integer, String>> pointer = map.entrySet().iterator(); while (pointer.hasNext()) </P>
  16. <P>     { </P>
  17. <P>Entry<Integer, String> e = pointer.next(); System.out.println(e.getKey() + "<===>" + e.getValue()); </P>
  18. <P>     }</P>
  19. <P>   }</P>
  20. <P>}</P>
复制代码

评分

参与人数 1技术分 +1 收起 理由
zzkang0206 + 1

查看全部评分

回复 使用道具 举报
排序的方法有:
回复 使用道具 举报
排序的方法有:
1:选择排序
2:冒泡排序
3:插入排序
4:归并排序
5:快速排序
6:希尔排序
其中效率最高的是快速排序.

评分

参与人数 1技术分 +1 收起 理由
zzkang0206 + 1

查看全部评分

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