算法--选择排序

1、概述

选择排序思想：对一组长度为 n 的未排序的数据进行遍历，比较得出最小值和对应的下标，然后将最小值和下标为0的值进行交换，即将最小值放到最前面；然后再从下标为1的位置进行第二轮遍历，比较得出剩余数据中的最小值，并与下标为1的值进行交换；按照这种方式依次遍历，直到完成所有数据的排序。

2、图解示例

观察可得：

1. 定义两个临时变量min和index，分别表示最小值和最小值的下标。并且每轮排序开始时，都将min和index的值重置为当前剩余未排序的起始值，然后依次向后遍历比较。
2. 对数组排序需要进行 length - 1 轮遍历。
3. 每轮遍历中的数据比较都在依次减少。

3、代码

package com.ld.algorithm.sort;

import java.util.Arrays;

/**
 * @author ld
 * @date 2020/8/6 21:30
 *
 * 算法--选择排序
 * 对一组长度为 n 的未排序的数据进行遍历，比较得出最小值和对应的下标，然后将最小值和下标为0的值进行交换，即将最小值放到最前面；
 * 然后再从下标为1的位置进行第二轮遍历，比较得出剩余数据中的最小值，并与下标为1的值进行交换；
 * 按照这种方式依次遍历，直到完成所有数据的排序。
 *
 */
public class SelectSort {

    public static void main(String[] args) {

        //测试数据
        int[] array = {23,1,90,-3,18};

        System.out.println("排序前：" + Arrays.toString(array));

        //进行选择排序
        int[] sortArray = sort(array);

        System.out.println("排序后：" + Arrays.toString(sortArray));
    }

    /**
     * 进行选择排序，以升序的方式排序
     * @param array 待排序的数组
     * @return 返回排序后的数组
     */
    public static int[] sort(int[] array){

        //标识要被交换的下标,初始默认为0
        int minIndex = 0;
        //标识为最小值,初始默认为第一个值
        int min = 0;
        for(int i = 0;i < array.length - 1;i++){
            minIndex = i;
            min = array[i];
            for(int j = i + 1; j < array.length;j++){
                //判断当前值是否小于最小值
                if(array[j] < min){
                    //将当前值赋值给min
                    min = array[j];
                    //记录当前下标
                    minIndex = j;
                }
            }
            //交换值
            if(minIndex != i){
                array[minIndex] = array[i];
                array[i] = min;
            }
        }
        return array;
    }
}