选择排序

选择排序

与冒泡类似，时间复杂度也是相同，但其中关键点在于记住索引。

• 场景0：现有数组([2,5,3,1,4]),求这个数组的从小到大排序后数组表现。
• 解决思路：依次确保第n个位置所在元素是前n个元素中最大的即可。
  • 2 < 5, 最大值为5，索引值为1。
  • 5 > 3, 5 > 1, 5 > 4。最大值还是5，索引值为1
  • 更换5 与 4的位置，此时数组为([2,4,3,1,5])
  • 继续比较，依次类推

目的是记住索引，记住最大或者最小值的索引,交换位置后。下一轮比较将直接跳过上一轮所更换的最大或者最小值位置。

Demo

package Sort;

import java.util.Arrays;

/**
 * 实现选择排序
 *
 * @author Ldity
 * @date: 2020/8/10 21点08分
 */
public class SelectSort {
    public static int[] arr = {123,34,132,21,23,1324,52,2123,23415,-1};

    /**
     * 获取两个值中的最小值的索引值
     *
     * @param arr - 待输入的数组
     * @param i 一个数的索引值i
     * @param j 一个属的索引值j
     * @return 返回最小值的索引
     */
    public static int minIndex(int[] arr, int i, int j){
        if( arr[i] < arr[j]){
            return i;
        }else return j;
    }

    /**
     * 交换数组中的两个值
     *
     * @param arr - 目的数组
     * @param i 其中一个数的索引值i
     * @param j 其中一个数的索引值j
     */
    public static void exchange(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 实现选择排序
     *
     * @param arr - 待排序的数组
     */
    public static void selectSort(int[] arr){
        int n = arr.length;
        // 遍历i个元素
        for(int i = 0; i < n; i++){
            int min = i;
            //记录一次过程的最小值，然后返回
            for(int j = i + 1; j < n; j++){
                min = minIndex(arr, min, j);
            }
            exchange(arr, i, min);
        }
    }
    public static void main(String[] args){
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}