本文共 5026 字，大约阅读时间需要 16 分钟。

今日内容

• 选择排序

选择排序（Selection Sort）

• 原理：从0索引开始，依次和后面元素比较，小的往前放，第一次完毕，最小值出现在了最小索引处。
• 步骤：
  1.在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
  2.从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
  3.重复第二步，直到所有元素均排序完毕。
• 动图演示：
  
• 代码如下：

//基本程序public class SelectionSort {
       public static void main(int []arr) {
               //第一轮：从0索引处开始            int index = 0;            for (int i = 0 + 1; i < arr.length; i++) {
                   if (arr[index] > arr[i]) {
                       int t = arr[index];                    arr[index] = arr[i];                    arr[i] = t;                }            }            System.out.println(Arrays.toString(arr));            //第二轮：从1索引处开始            index = 1;            for (int i = 0 + index + 1; i < arr.length; i++) {
                   if (arr[index] > arr[i]) {
                       int t = arr[index];                    arr[index] = arr[i];                    arr[i] = t;                }            }            System.out.println(Arrays.toString(arr));            //第三轮：从2索引处开始            index = 2;            for (int i = 0 + index + 1; i < arr.length; i++) {
                   if (arr[index] > arr[i]) {
                       int t = arr[index];                    arr[index] = arr[i];                    arr[i] = t;                }            }            System.out.println(Arrays.toString(arr));            //第4轮：从3索引处开始            index = 3;            for (int i = 0 + index + 1; i < arr.length; i++) {
                   if (arr[index] > arr[i]) {
                       int t = arr[index];                    arr[index] = arr[i];                    arr[i] = t;                }            }            System.out.println(Arrays.toString(arr));        }    }

代码优化1：

public class SelectionSort {
           public static void main(String[] args) {
               int arr[]={
   23,12,43,22,13,45,67};            for (int index = 0; index < arr.length-1; index++) {
                   for (int i = 1 + index ; i < arr.length; i++) {
                       if(arr[index]>arr[i]){
                           int temp=arr[index];                        arr[index]=arr[i];                        arr[i]=temp;                    }                }            }            System.out.println(Arrays.toString(arr));        }    }

代码优化2：

public class SelectionSort {
        public static void main(String[] args){
           int arr[]={
   23,12,43,22,13,45,67};        selectSort(arr);        System.out.println(Arrays.toString(arr));    }     public static void selectSort(int[] arr){
            int min = 0;         int minIndex = 0;          for(int i=0; i< arr.length-1; i++){
                           min = arr[i]; //假定最小值            minIndex = i; //假定最小值的索引             for(int j=i+1; j
   
     arr[j]){
    //说明min不是假定的最小值 arr[j]比 min还小                    min = arr[j]; //重置min，让min重返最小值，找到该轮的最小值                    minIndex = j; //重置minIndex，找到该轮的最小值索引                }            }             //将最小值 放在 arr[0]，即交换            //如第一轮下来 i=0时，min = 1, minIndex = 3            if(minIndex != i){
    //这里是优化的代码，如果minIndex没有发生改变，就不执行里面得的代码                arr[minIndex] = arr[i]; //把 第i轮循环开始的，第一个元素 放到下标 minIndex 最小值那个位置上(第一轮 arr[3] = arr[0], 将111放在1那个位置)                arr[i] = min; //第一轮的时候，此时min = 1 是最小值，arr[0] = 1, 把第一个元素设置成最小值            }             System.out.println("第" + (i+1) +"轮候后：");            System.out.println(Arrays.toString(arr));        }    }  }
   

• 时间复杂度与空间复杂度的计算

• 代码1：

public class SelectionSort {
           public static void main(String []args) {
               //测试时间顺序            int arr[]=new int[10000];            Random r = new Random();            //给数组元素赋值            for(int i = 0;i
   
    arr[i]){
                           int temp=arr[index];                        arr[index]=arr[i];                        arr[i]=temp;                    }                    count++;                }            }            System.out.println(count);        }    }
   

• 可以清楚的看到在测试数据量同为10000时，双层for循环所需的次数为49995000次以及所耗时间为156ms（相比较冒泡排序要快很多）。
• 代码2：

class SelectionSort {
           public static void main(String []args) {
               //测试时间顺序            int arr[]=new int[10000];            Random r = new Random();            //给数组元素赋值            for(int i = 0;i
   
     arr[j]){
                               //说明min不是假定的最小值 arr[j]比 min还小                            min = arr[j]; //重置min，让min重返最小值，找到该轮的最小值                            minIndex = j; //重置minIndex，找到该轮的最小值索引                        }                    }                    //将最小值 放在 arr[0]，即交换                    //如第一轮下来 i=0时，min = 1, minIndex = 3                    if(minIndex != i){
    //这里是优化的代码，如果minIndex没有发生改变，就不执行里面得的代码                        arr[minIndex] = arr[i]; //把 第i轮循环开始的，第一个元素 放到下标 minIndex 最小值那个位置上                        arr[i] = min; //第一轮的时候，此时min = 1 是最小值，arr[0] = 1, 把第一个元素设置成最小值                    }                    count++;                }            System.out.println(count);            }        }
   

• 可以清楚的看到在测试数据量同为10000时，优化后的代码所需的次数为9999次以及所耗时间为64ms（相比较前一个排序要快很多而且所占空间也小很多）。

转载地址：http://fmfyf.baihongyu.com/