排序算法-选择排序

我们都知道排序算法最好的时间复杂度为O(nlog n)，但是很多的排序方法时间复杂度为O(n^2)。
那我们为什么要学习O(n^2) 的排序算法呢，直接学最好的不就行了。但是复杂度为O(n^2)的算法是最直观，最容易理解的。先解决，再优化的思想是一种非常重要的解决问题的手段。所以我们需要学习简单的算法，然后逐步求精实现高效率的算法。

选择排序：
先从数组中找到最小的元素，放在第一个位置，然后再从第二个往后找，找到最小的元素，放在第二个位置，继续从第三个位置开始找，找到最小的元素，放在第三个位置...

    // 选择排序法
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // 先假定i为当前趟排序中最小的元素的下标
            int minIndex = i;

            // 找到未排序数组中最小元素的下标并更新minIndex
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 与i所在的元素交换
            int swaper = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = swaper;
        }
    }