2021-10-09

• 选择排序
• • • 1、什么是选择排序：
    • 2、选择排序的代码示例
    • 3、时间复杂度分析及稳定性
    • 4、改进后的选择排序
    • 5、进一步优化
    • 6、验证

选择排序（Selection sort）是一种简单直观的排序算法。 它的工作原理是：第一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小，然后放到已排序后的序列的末尾。 以此类推，直到全部待排序的数据元素的个数为零。 选择排序是不稳定的排序方法。

public class Selection {
    public static void main(String[] args) {
        //定义一个int类型的数组
        int[] array = {1,5,9,7,6,3,4,8,2};
        //遍历数组
        for(int i = 0;i 
3、时间复杂度分析及稳定性 
时间复杂度 ：O（n^2）
 最好最坏情况下：O（n^2）
 空间复杂度：O（1）
 
稳定性：不稳
 
4、改进后的选择排序 
原理：经过一轮排序，不仅找到一个最小值，同时也找到最大值，减少排序一半的次数
 
public class Selection {
    public static void main(String[] args) {
        //定义一个整数类型的数组
        int[] array = {1,5,9,7,6,3,4,8,2};

        //遍历数组
        for(int i = 0;iarray[j] ? j : minPos;
                maxPos = array[maxPos] 
5、进一步优化 
在上述优化的基础 之上可以进一步优化，方法是一次性提取两个数与所设置的最小值（或者最大值来进行比较）。
 
6、验证 
因为排序次数少或者原始数据较少可能会产生偶然性，应该编写程序验证选择排序算法的正确性。
 
package Sort;

import java.util.Arrays;
import java.util.Random;

public class Selection {
    public static void main(String[] args) {
        check();

    }


    //验证排序算法的正确性
    static void check(){
        int[] arr = generateRandomArray();
        //复制一个数组，一个用Java自带的Array.sort()方法，另外一个用自己写的选择排序
        int[] arr2 = new int[arr.length];
        //系统带的排序算法
        System.arraycopy(arr,0,arr2,0,arr.length);
        boolean same = true;
        for(int i = 0;iarray[j] ? j : minPos;
                    maxPos = array[maxPos]