1 package lsg.ap.select;

 import java.util.Random;

 public class SelectSort
 {
     //选择排序
     /**
      *@author: 梁山广
      * 2016年4月11日上午10:04:13
      * @param a:需要尽行排序的数组
      */
     //选择排序
     /*
      *  选择排序和冒泡排序差不多，只是冒泡排序在发现比它小的时候就交换，而选择排序是只
      *  有在确定了最小的数据之后，才会发生交换。选择排序的基本思想：第i趟简单选择排序
      *  是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个
      *  记录进行交换。先临时记录其位置，只有在一趟循环完以后确定了最小的数据，才会发生交换。
      *  问题：为什么最小值记录要用下标而不能直接用数组元素？
      *  答：会导致数据覆盖后丢失
      */
     public static void selectSort(int [] a)
     {
         int n = a.length;
         for(int i=0; i<n-1; i++)
         {
             int min = i;
             for(int j=i+1; j<n; j++)
             {
                 if(a[j] < a[min])
                 {
                     min = j;
                 }
             }
             if(i != min)//当当前位置已经为本轮最小元素时，直接不用交换即可
             {
                 int temp = a[i];
                 a[i] = a[min];
                 a[min] = temp;
             }
         }  

     }
     public static void selectSort2(int [] a)
     {
         int n = a.length;
         for(int i=0; i<n-1; i++)
         {
             int min = a[i];
             for(int j=i+1; j<n; j++)
             {
                 if(a[j] < min)
                 {
                     min = a[j];
                 }
             }
             if(a[i]!= min)//这个本质是为了把最小的元素交换到最前面，
                           //但是实际上当a[i]!=min时会导致a[i]数据的丢失
                          //，出现了重复的元素，因此只能用下标来指示min
                         //但是插入排序的话，两种方法都可以
             {
                 int temp = a[i];
                 a[i] = min;
                 a[min] = temp;
             }
         }  

     }
     /**
      *
      * 输出相应数组的结果
      * @param array
      */
     private static void printArray(int[] array)
     {
        for(int value:array)
        {
            System.out.print(" "+value+" ");

        }
        System.out.println();
     }
     public static void main(String[] args)
     {
         //小数据量的测试
         int[] array=new int[]{8,3,2,1,7,4,6,5};
         //下面是大数据量的测试。这样才能看出不同算法的优劣
         Random random=new Random();
         int[] array2=new int[2000];
         for(int j=0;j<2000;j++)
         {
             array2[j]=random.nextInt(100000);
         }
          System.out.println("排序前数组元素为：");
          printArray(array);
          long dateStart=System.nanoTime();
          selectSort(array);
          long dateEnd=  System.nanoTime();
          long totalTime=dateEnd-dateStart;
          System.out.println("选择排序的时间复杂度为：");
          System.out.println(totalTime+"纳秒");
          System.out.println("排序后数组元素为：");
          printArray(array);
     }

 }