选择排序

前言

自己动手实现一下各种算法，以后复习也不用到处搜索了

通俗一点

例如从小到大排序，每次假设未排序的首位为最小值，则最小位置为首位。遍历剩下所有未排序，如果发现有值比首位小，标记当前位置为最小位置，继续遍历。发现比最小位置的值还要小，更新此位置为最小位置。一轮循环结束，如果最小位置不为首位，交换两个位置数据。当前循环结束，首位已排序，下次从 +1 位置开始遍历。
如果数组个数为 N，则需要循环 N-1 次。

算法实现JAVA

public class SelectionSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 总共要经过 N-1 轮比较
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;

            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }

            // 将找到的最小值和i位置所在的值进行交换
            if (i != min) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }

        }
        return arr;
    }
}

运行结果

----------------第1次循环后------------------- 3 44 38 5 47 15
----------------第2次循环后------------------- 3 5 38 44 47 15 
----------------第3次循环后------------------- 3 5 15 44 47 38 
----------------第4次循环后------------------- 3 5 15 38 47 44 
----------------第5次循环后------------------- 3 5 15 38 44 47

动画展示

selection