黑马程序员技术交流社区

标题: 排序选择之超级优化 [打印本页]
作者: lizhichao    时间: 2015-7-25 18:11
标题: 排序选择之超级优化
[img]
下面的
选择排序1()这个方法
是我自己写的。虽然结果不尽人意但是思想还是不错的。希望能带动思考

第一步：跟普通的选择排序区别在于这个排序机一次性记录两个连续的角标。这样的话外层循环 每次的遍历就能够减少到原来的1/2左右；一次遍历就能找到最小的两个数。下面是详细步骤
1.定义数组封装方法
a：明确返回类型：对遍历后的集合 我们在方法体内打印出来辨别是否排序正常不需要排序所以把返回类型定义为void ：
b：明确参数列表：在这里我们是对数组进行从小到大遍历，只需要一个数组就可以了 int[] arr
第二步： .建立for（int i;i<arr.length-2;i=i+2）循环在循环体内声明两个变量temp1，temp2记录住arrarr[i=1];比较这两个数的大小。再定义两个记录住角标因为循环一次能够比较两个数所以将循环的角标i一次自加2；
第三步：建立内层循环for();遍历集合将集合中最小的两个数的值记录下来和角标记录下来；
待循环完毕
对记录的两个最小值于i，i+1进行替换，
就这样循环下去；
下面是代码

2.比较它们的大小。小的用temp1记录大的用temp2记录，
3



  1. public static void main(String[] args) {
  2.                 int[] arr = {98,76,45,68,90,79,88,99,84,54,55,47,60,94,54,50,98,98,23,23,45,21,};
  3.                  int a = 0;
  4.                  for (int i = 0; i < arr.length; i++) {
  5.                         a++;
  6.                 }
  7.                  System.out.println(a+"\n\r");
  8.                 long a1 = System.currentTimeMillis();
  9.                 选择排序(arr);
  10.                  long a2 = System.currentTimeMillis();
  11.                  选择排序1(arr);
  12.                  long a3 = System.currentTimeMillis();
  13.                  if((a3-a2)>(a2-a1)){
  14.                          System.out.println("真");
  15.                  }else{
  16.                          System.out.println("假");
  17.                  }
  18.         }
  19.         public static void 选择排序(int[] arr){
  20.             for(int i = 0 ; i < arr.length-1; i++){//i1 j 2
  21.                     int temp = arr[i];
  22.                     int index = i;
  23.                 for(int j = i +1;j < arr.length;j++){
  24.                      if(temp > arr[j]){
  25.                             temp = arr[j];
  26.                             index = j;
  27.                      }
  28.                 }
  29.                arr[index] = arr[i];
  30.                arr[i] = temp;
  31.             }
  32.             for(int i = 0 ;i<arr.length;i++){
  33.             System.out.println(arr[i]);
  34.             }
  35.         }
  36.         public static void 选择排序1(int[] arr){//超级优化
  37.                  
  38.        
  39.                  for (int i = 0; i < arr.length-2;i = i + 2) {
  40.                                           int temp1 = arr[i];
  41.                                           int temp2 = arr[i+1];
  42.                                          if(temp1 > temp2){
  43.                                                  temp1 = temp1+temp2;
  44.                                                  temp2 = temp1 - temp2;
  45.                                                  temp1 = temp1 - temp2;
  46.                                   }
  47.                          int index1 =i , index2 =i+1;
  48.                                                                         for (int j = i+2; j < arr.length; j++) {
  49.                                                                                                                          if(arr[j] < temp1){
  50.                                                                                                                                  temp2 = temp1;
  51.                                                                                                                                  index2 = index1 ;
  52.                                                                                                                                   temp1 = arr[j];
  53.                                                                                                                                  index1 = j;
  54.                                                                                                                          }else if(arr[j]<temp2){
  55.                                                                                                                                  temp2 =        arr[j];
  56.                                                                                                                                  index2= j;
  57.                                                                                                                          }                               
  58.                                                                          }
  59.                                         arr[index1] =arr[i];
  60.                                          arr[index2]= arr[i+1];
  61.                                          arr[i] = temp1;
  62.                                          arr[i+1]= temp2;
  63.                          }
  64.                  for (int i = 0; i < arr.length; i++) {
  65.                         System.out.println(arr[i]);
  66.                 }
  67.         }
复制代码


[/img]

选择排序.png (132.18 KB, 下载次数: 17)

选择排序.png
作者: lizhichao    时间: 2015-7-25 18:16
代码是老版本没有优化但更容易理解



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