基础排序算法-------选择排序

实现过程：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
然后从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

特点：

选择排序是一种比较容易理解和实现的简单的排序方法，有以下两个特点：
1.运行时间和输入无关:例如：一个有序数组或元素值都相等的数组和一个同等规模的随机数组的排序时间是一样的。
2.数据的移动量是最小的:每次交换都会改变两个元素的值，因此整个排序过程进行了N次交换。

时间复杂度：O(N^2)

任何情况下都为O(N^2)：对于长度为N的数组，选择排序需要大概 N^2/2 次比较和 N 次交换

空间复杂度：O(1)

稳定性：不稳定 ，无法保证相同值元素的先后顺序不改变

代码实现：

    public static void selectionSort(int[] arr) {
        int len = arr.length - 1;
        //每次遍历找到剩下元素中最小的那个元素
        for (int i = 0; i < len; ++i) {
            //min存储最小值的索引
            int min = i;
            for (int j = i + 1; j <= len; ++j) {
                //遇到更小的元素，更新min的值
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            //交换元素位置
            swap(arr, min, i);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int mid = arr[i];
        arr[i] = arr[j];
        arr[j] = mid;
    }

双向选择排序(思路拓展，效率基本没有优化)

在基础选择排序的基础上，进行一次遍历的同时找到无序区间中最大和最小的两个元素，分别交换到无序区间两头

代码实现：

    public static void selectionSortBP(int[] arr) {
        int len = arr.length - 1;
        //left指向无序区间第一个元素
        int left = 0;
        //right指向无序区间最后一个元素
        int right = len;
        //当left==right时，说明无序区间就剩一个元素，这个数组已经有序
        while (left <= right) {
            //存储最小元素索引
            int min = left;
            //存储最大元素索引
            int max = left;
            //每次遍历找无序区间中最大和最小的那两个元素
            for (int i = left + 1; i <= right; ++i) {
                //当前元素更小，更新min
                if (arr[i] < arr[min]) {
                    min = i;
                }
                //当前元素更大，更新max
                if (arr[i] > arr[max]) {
                    max = i;
                }
            }
            //此时min一定对应最小元素，将该元素交换值无序区间第一位
            swap(arr, min, left);
            //如果left==max，说明刚刚的遍历并没有找到更大的元素
            //而被交换到min位置的元素就是当前区间最大的元素
            if (left == max) {
                //先更新max
                max = min;
            }
            //此时max指向最大元素位置
            swap(arr, max, right);
            //缩小无序区间
            left++;
            right--;
        }
    }

10万个数据的无序数组排序耗时：

双向选择排序听着感觉效率会更高一些，实际上有时候效率反而更差