黑马程序员技术交流社区

标题: 排序问题----寻找最好方法 [打印本页]

---

作者: 孙万利    时间: 2012-11-24 18:44
标题: 排序问题----寻找最好方法
一个数组
int [] arr = new int[]{1,6,5,9,8,2,7}；
进行排序
下面是我学习的方法；

这是 普通排序
//选择排序法之升序，反之（<）就是降序
  public static void sort(int [] arr){
  
   int temp=0;
   
   for(int x=0;x<arr.length-1;x++){
   
            for(int y=x+1;y<arr.length;y++){
   
                     if(arr[x]>arr[y])
                      {
                          temp=arr[x];
                         arr[x]=arr[y];
                          arr[y]=temp;
                       }
     
                }
   
         }
  }

这是 冒泡排序
public static void maopaosort(int [] arr){
  
   for(int x=0;x<arr.length-1;x++){
        for(int y=0;y<arr.length-x-1;y++){
                 if(arr[y]>arr[y+1]){
                    int temp = arr[y];
                    arr[y]=arr[y+1];
                   arr[y+1]=temp;
                                   }
   
                         }
             }
  }

问题是：这两种排序方法哪种更高效率，还有比这两种更高效的嘛？写出来让我学习下
               请大家指教

---

作者: 徐大鹏    时间: 2012-11-24 19:28

1. import java.util.*;
   
2. public class SetTest {
   
3.         public static void main(String[] args) {
   
4.                 int[] array = { 1,6,5,9,8,2,7 };
   
5.                 ArrayList<Integer> listA = new ArrayList<Integer>();
   
6.                 for (int i = 0; i < array.length; i++) {
   
7.                         listA.add(new Integer(array[i]));
   
8.                 }
   
9.                 TreeSet<Integer> hsetA = new TreeSet<Integer>(listA);
   
10.                 Object[] result = hsetA.toArray();
    
11.                 int[] resultIntArray = new int[result.length];
    
12.                 for (int i = 0; i < result.length; i++) {
    
13.                         resultIntArray[i] = ((Integer) result[i]).intValue();
    
14.                 }
    
15.                 for (int i = 0; i < resultIntArray.length; i++) {
    
16.                         System.out.println(resultIntArray[i]);
    
17.                 }
    
18.         }
    
19. }

复制代码

---

作者: 林庆松    时间: 2012-11-24 19:33
听毕老师讲是 希尔排序 （shell sort）最快，如果数组元素不多。普通排序和冒泡排序效率都差不多。以后开发都是直接调用java自带的排序的。

---

作者: ljhheima    时间: 2012-11-24 20:09
下面的冒泡相对快一些，因为冒泡比上面的选择排序循环相对要少，即比较次数也少。
你写的两种方法都可以改进。
冒泡改进：
static void sort(int[]arr)
{
                for(int i=arr.length-1;i>1;i--)
                {
                        int t=Integer.MAX_VALUE;                //作为标记，当t不变时，排序结束，同时是交换临时变量
                for(int j=0;j<i-1-x;j++)
                {
                        if(arr[j]<arr[j+1])
                        {
                        t=arr[j];                        //arr[j]必然小于Integer.MAX_VALUE;
                        arr[j]=arr[j+1];
                        arr[j+1]=t;
                        }
                }
                if(t==Integer.MAX_VALUE)
                        break;
                }       
}
当排序结束是跳出循环；




选择改进版：
for(int i=0;i<arr.len-1;i++)
{
        int t=-1;                                        //作为临时变量，减少交换次数
        for(int j=i+1;j<arr.len;j++)
        {
                if(arr[i]>arr[j])
                                t=j;
        }
        if(t!=-1)
        {
                        //交换两个数
                arr[t]=arr[i]^arr[t];
                arr[i]=arr[i]^arr[t];
                arr[t]=arr[t]^arr[i];
        }

还有很多比较快得排序方法，像堆排序，快速排序效率都很高。

---

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

黑马程序员IT技术论坛 X3.2