黑马程序员技术交流社区

标题: 数组排序方法问题？ [打印本页]
作者: 曾经的迷失    时间: 2014-2-25 08:38
标题: 数组排序方法问题？
请问，数组排序用哪种方法效率比较高？ Arrays.sort()除外。
作者: syw02014    时间: 2014-2-25 08:54
排序算法的分类如下：
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）中，它至少会把一个元素摆到它最后的位置去。


作者: 何建明    时间: 2014-2-25 09:30
基础视频学习刚学到两个排序方法...
  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);

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

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

  39. }
  40. //选择排序
  41. public class Demo6 {
  42.         public static void main(String[] args) {
  43.                 int []age = {1,2,36,363,56,95,12,32,1232,3263};
  44.                
  45.                 for (int i = 0; i < age.length; i++) {
  46.                         for (int j = i+1; j <= age.length-1; j++) {
  47.                                 if(age[i] > age[j]){
  48.                                         int temp = age[i];
  49.                                         age[i] = age[j];
  50.                                         age[j] = temp;
  51.                                 }
  52.                         }
  53.                 }
  54.                 System.out.println(Arrays.toString(age));
  55.         }
  56. }       
  57. //输出为：[1, 2, 12, 32, 36, 56, 95, 363, 1232, 3263]
复制代码
作者: wdtdcm    时间: 2014-2-25 14:19
本帖最后由 wdtdcm 于 2014-2-25 14:26 编辑

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

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

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




我个人觉得,了解这些基本原理花的时间还不算多,但是深入研究还是要花比较多时间了.
作者: 大茶壶    时间: 2014-2-25 21:13
据说哈希算法是排序效率最高的一种算法。

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

作者: 位俊鹏    时间: 2014-2-25 21:25
排序的方法有:
作者: 位俊鹏    时间: 2014-2-25 21:30
排序的方法有:
1:选择排序
2:冒泡排序
3:插入排序
4:归并排序
5:快速排序
6:希尔排序
其中效率最高的是快速排序.



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