黑马程序员技术交流社区

标题: 排序的问题 [打印本页]
作者: 赵国刚    时间: 2013-8-13 08:12
标题: 排序的问题
一个数组
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;
                                   }
   
                         }
             }
  }

问题是：这两种排序方法哪种更高效率，还有比这两种更高效的嘛？写出来让我学习下
               请大家指教
作者: べPNヤ    时间: 2013-8-13 08:40
1  public static int[] insertSort(int[] args){//插入排序算法
2                 for(int i=1;i<args.length;i++){
3                         for(int j=i;j>0;j--){
4                                 if (args[j]<args[j-1]){
5                                         int temp=args[j-1];
6                                         args[j-1]=args[j];
7                                         args[j]=temp;        
8                                 }else break;
9                         }
10                 }
11                 return args;
12         }
作者: べPNヤ    时间: 2013-8-13 08:44
还有一个毕老师讲过的排序  选择排序
1 public static int[] selectSort(int[] args){
2                 for (int i=0;i<args.length-1 ;i++ ){
3                         int min=i;
4                         for (int j=i+1;j<args.length ;j++ ){
5                                 if (args[min]>args[j]){
6                                         min=j;
7                                 }
8                         }
9                         if (min!=i){
10                         int temp=args[i];
11                         args[i]=args[min];
12                         args[min]=temp;        
13                         }
14                 }
15                 return args;
16         }
作者: 心灵之歌    时间: 2013-8-13 10:28
一个数组
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;
                                   }
   
                         }
             }
  }

问题是：这两种排序方法哪种更高效率，还有比这两种更高效的嘛？写出来让我学习下
               请大家指教
////////这俩种排序，冒泡排序效率要高。
比这俩种排序效率更高的有啊，只要保证排序的时候，每一个元素访问的次数最少，那效率就会最高！
作者: 以防万一    时间: 2013-8-13 22:32
亲，如问题已解决请将分类的未解决改为已解决。

以后的问题贴也要及时更改分类哦~


保持队形，谢谢合作
作者: yangxin540    时间: 2013-8-14 00:39
毕老师好像提到过要快的还是希尔排序，我也还是在学习中，就从百度给找了个例子
  1. public class Test {
  2. 　　public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 };
  3. 　　public static void main(String args[]) {
  4. 　　int i; // 循环计数变量
  5. 　　int Index = a.length;// 数据索引变量
  6. 　　System.out.print("排序前: ");
  7. 　　for (i = 0; i < Index - 1; i++)
  8. 　　System.out.printf("%3s ", a[i]);
  9. 　　System.out.println("");
  10. 　　ShellSort(Index - 1); // 选择排序
  11. 　　// 排序后结果
  12. 　　System.out.print("排序后: ");
  13. 　　for (i = 0; i < Index - 1; i++)
  14. 　　System.out.printf("%3s ", a[i]);
  15. 　　System.out.println("");
  16. 　　}
  17. 　　public static void ShellSort(int Index) {
  18. 　　int i, j, k; // 循环计数变量
  19. 　　int Temp; // 暂存变量
  20. 　　boolean Change; // 数据是否改变
  21. 　　int DataLength; // 分割集合的间隔长度
  22. 　　int Pointer; // 进行处理的位置
  23. 　　DataLength = (int) Index / 2; // 初始集合间隔长度
  24. 　　while (DataLength != 0) // 数列仍可进行分割
  25. 　　{
  26. 　　// 对各个集合进行处理
  27. 　　for (j = DataLength; j < Index; j++) {
  28. 　　Change = false;
  29. 　　Temp = a[j]; // 暂存Data[j]的值,待交换值时用
  30. 　　Pointer = j - DataLength; // 计算进行处理的位置
  31. 　　// 进行集合内数值的比较与交换值
  32. 　　while (Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index) {
  33. 　　a[Pointer + DataLength] = a[Pointer];
  34. 　　// 计算下一个欲进行处理的位置
  35. 　　Pointer = Pointer - DataLength;
  36. 　　Change = true;
  37. 　　if (Pointer < 0 || Pointer > Index)
  38. 　　break;
  39. 　　}
  40. 　　// 与最后的数值交换
  41. 　　a[Pointer + DataLength] = Temp;
  42. 　　if (Change) {
  43. 　　// 打印目前排序结果
  44. 　　System.out.print("排序中: ");
  45. 　　for (k = 0; k < Index; k++)
  46. 　　System.out.printf("%3s ", a[k]);
  47. 　　System.out.println("");
  48. 　　}
  49. 　　}
  50. 　　DataLength = DataLength / 2; // 计算下次分割的间隔长度
  51. 　　}
  52. 　　}
  53. }
复制代码
作者: 张俊生    时间: 2013-8-15 23:58
亲，如问题已解决请将分类的未解决改为已解决。

以后的问题贴也要及时更改分类哦~

保持队形，谢谢合作
作者: 静以修身    时间: 2013-8-16 01:31
其实那两个效率都差不多，使用的都是蛮力法，时间复杂度是O（n^2），可以说效率很低。而且没有改进，选择排序可以减少移动的次数，从而提高性能。而冒泡排序也可以改进，在一趟冒泡排序过程中，如果有多个记录交换到最终位置，则下一趟冒泡排序将不处理这些记录；另外，在一趟冒泡排序过程中，如果没有记录想交换，那么表明这个数组已经有序，算法终止，可以在你的算法基础上加个标志位就能够改进。
下面我给出这两个改进的算法：
改进的选择排序算法：
void SelectSort(int r [],int n)  {
　　for(int i = 0;i<n-1;i++){
　　int index = i;
　　for(int j = i+1;i<n;j++){  //在无序区中找最小记录
　　if(r[j]<r[index]);
　　index = j;
　　i(index != i){
　　b = a^b;a = a^b;b = a^b; //若最小记录不在最终位置则交换
　　}
　　}
　　}
}
改进的冒泡排序算法：
Void BubbleSort(int r [] ,int n){
　　int exchange = n;
　　while(exchange){
　　int bound = exchange;exchange= 0;
　　ror(int j = 1;j<bound;j++)
　　if(r[j]>r[j+1]){
　　r[j+1];= r[j]^r[j+1];
　　r[j] = r[j]^r[j+1];
　　r[j+1];= r[j]^r[j+1];
　　exchange = j;
　　}
　　}
}
希望对你有用！



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