算法 - 选择排序

什么是选择排序

选择排序是一种排序算法，时间复杂度简单可以记为O(n x n)，算法灵巧但速度不是很快

大体思路：遍历数组，每次取出遍历数组中最小值放到结果数组中，同时数组缩容去除遍历数组中最小值，继续遍历

即，取最小值放结果数组中 -> 缩容去最小 -> 重复第一步

选择排序的步骤

给定数组

创建一个与原数组等长的结果数组

使用两个变量分别记录数组中的最小值与最小值坐标

取原数组中第一个值与其他元素比较，如果被比较值小于当前最小值则替换最小值为当前值，反之继续遍历

遍历完成返回当前数组最小值的下标，将原数组中的最小值放到结果数组的第一位，第一次遍历得到2

接下来需要去除给定数组中的最小值，缩小数组，第二次遍历得到3

每次遍历缩小后的数组，找出最小值放到结果数组中，再次缩小上次缩小过的数组，直到将结果数组填满

最后得到结果数组

Java实现

package com.github.hellxz.grokkingalgorithms.selectionsort;

/**
 * 选择排序
 */
public class SelectionSort {

    public static int[] selectionSort(int[] arr) {
        //创建结果数组
        int[] solution = new int[arr.length];
        for (int i = 0; i < solution.length; i++) {
            //获得当前arr最小值下标
            int smallestIndex = findSmallestIndex(arr);
            //将当前arr最小值放到结果数组
            solution[i] = arr[smallestIndex];
            //arr缩容，去除最小值
            arr = newArrayWithoutLastSmallest(arr, smallestIndex);
        }
        return solution;
    }

    /**
     * 返回去掉给定值的新数组
     */
    private static int[] newArrayWithoutLastSmallest(int[] arr, int lastSmallestIndex) {
        int[] newArr = new int[arr.length - 1];
        for (int i = 0; i < arr.length; i++) {
            if (i < lastSmallestIndex) {
                newArr[i] = arr[i];
            } else if(i > lastSmallestIndex) {
                newArr[i-1] = arr[i];
            }
        }
        return newArr;
    }

    /**
     * 查找给定数组最小值下标
     */
    private static int findSmallestIndex(int[] arr) {
        int smallest = arr[0];
        int smallestIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            if (smallest > arr[i]) {
                smallest = arr[i];
                smallestIndex = i;
            }
        }
        return smallestIndex;
    }

    public static void main(String[] args) {
        int[] arr = {8, 6, 7, 5, 3, 2, 4};
        int[] sortedArr = selectionSort(arr);
        for (int i = 0; i < sortedArr.length; i++) {
            System.out.print(sortedArr[i]);
        }
    }
}