选择排序（Selection Sort）

  我们这里说的选择排序，特指简单选择排序。这个选择排序也是一种相对简单直观的基础排序算法，选择选择，每一次都做简单选择，每一次都选出最大或最小。

基本思想

  选择排序的核心思想就是：在遍历的过程中，每次都选数据样本中最小的数据，放在首位。看起来简单纯朴吧，从第一个元素开始，每次都取剩余数据元素的最小个，我们小时候摆积木的玩的时候，都已经掌握的算法，质朴归真，哈哈哈。

算法描述

1：从待排序数据元素中，找到最小元素，放置序列首位（与首位交换）；
2：从第一位元素开始，循环1行为，直至数据遍历结束，排序完成。

动图演示

代码实现

import java.util.Arrays;

/** 
* @author    :Veiking
* @version    :2020年10月10日
* 说明        :选择排序算法
*/
public class SelectionSort {
    /**
     * 选择排序
     * @param arrays
     * @return
     */
    public static int[] sort(int[] arrays) {
        int min;
        int temp;
        // 从第一个元素开始，每一轮都会选出最小的元素下标，结下对剩余的重复操作，直至处理完毕
        for(int i = 0; i < arrays.length; i++) {
            min = i;
            // 每次都找出最小的下标，赋予min
            for(int j=i; jarrays[j]) {
                    min = j;
                }
            }
            // 当min不等于i时，则交换，最小的元素即被放置在最前
            if (i!=min) {
                temp=arrays[i];
                arrays[i]=arrays[min];
                arrays[min]=temp;
            }
            //System.out.println("第"+i+"次排序操作结果："+Arrays.toString(arrays));
        }
        return arrays;
    }

    // 执行
    public static void main(String[] args) {
        int[] input = new int[]{3, 7, 2, 6, 1, 5, 4};
        System.out.println("样本初始样本数据："+Arrays.toString(input));
        int[] output = SelectionSort.sort(input);
        System.out.println("选择排序结果数据："+Arrays.toString(output));
    }
}

算法分析

  选择排序算法的基本性能，归纳如下图：

1、 时间复杂度

  我们可以看到，选择排序算法的规则本身，就是一个一个来，众里挑一；并且每一趟在完全遍历完之前，是不能确定是否最大或者最小，于是乎，一个艰难的结论：选择排序的比较次数，与待排数据样本的初始序列没有任何关系。
  所以，选择排序的时间复杂度，无论待排数据是否有序，都要比较n×^(n-1)/₂次，故好坏平均的时间复杂度都认为是O(n²)。

2、 空间复杂度

  看代码可以了解到，这个选择排序，只需要两个临时变量，并不需要其他的额外计算存储空间，故空间复杂度为O(1)。

2、稳定性

  喧杂排序的核心是每次都选最小，放置在最前头，但是每一次选中之后都要和首位的交换，这时候如果有元素与首位元素等值，这个换一下，谁前谁后就不好说了，所以选择排序是不稳定的算法。