黑马程序员技术交流社区

标题: 选择排序算法的改进算法 [打印本页]

---

作者: 奔跑的小红帽    时间: 2015-10-15 21:51
标题: 选择排序算法的改进算法
class ArrayDemo{
       public static void main(String[] args) {
            int[] arr= {76,34,256,17,3,89};
            System.out.print("排序前数组：" );
            printArray(arr);
            selectSort(arr);
            System.out.print("排序后数组：" );
            printArray(arr);
      }

       public static void selectSort(int[] arr){
             for(int x = 0; x < arr.length - 1; x++){
                   for(int y = x + 1; y < arr.length; y++){
                         if(arr[x] > arr[y]){
                              int temp = arr[x];
                              arr[x] = arr[y];
                              arr[y] = temp;
                        }
                  }
            }
      }

       public static void printArray(int[] arr){
            System.out.print("[" );
            for(int x = 0; x < arr.length; x++){
                   if(x != arr.length - 1)
                        System.out.print(arr[x] + "," );
                   else
                        System.out.println(arr[x] + "]" );
            }
      }
}   
上面的选择排序算法效率比较低，因为数组每一个元素与剩下的元素比较就是为了获得最小的元素并且与之互换。例如：{76,34,256,17,3,89}这个数组，第一轮就要互换4次才能使第一个元素存储的是这个数组中最小的元素。如果是这样，那么更高效率的方式则是只需要通过两个变量，一个记录最小值，一个记录最小值所在的角标即可。等当前元素与余下的所有元素比较完，直接互换，这样只需互换一次就能达到目标，效率自然就会提高。
class ArrayDemo{
       public static void main(String[] args) {
             int[] arr= {76,34,256,17,3,89};
             System.out.print("排序前数组：" );
             printArray(arr);
             selectSort(arr);
             System.out.print("排序后数组：" );
             printArray(arr);
      }


       public static void selectSort(int[] arr){
             for(int x = 0; x < arr.length - 1; x++){
                   int num = arr[x];
                   int index = x;
                   for(int y = x + 1; y < arr.length; y++){
                         if(num > arr[y]){
                              num = arr[y];
                              index = y;
                        }
                  }
                  //如果最小的就是自己，就没有必要执行swap操作
                  if(index != x)
                        swap(arr,x,index);
            }
      }
      
      public static void swap(int[] arr, int a,int b){
            int temp = arr[a];
            arr[a] = arr;
            arr = temp;
      }
      
       public static void printArray(int[] arr){
            System.out.print("[" );
            for(int x = 0; x < arr.length; x++){
                   if(x != arr.length - 1)
                        System.out.print(arr[x] + "," );
                   else
                        System.out.println(arr[x] + "]" );
            }
      }
}  

---

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

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