排序算法—选择排序

选择排序

选择排序每一次可以确定一个 最小（或最大）值，这样的话我需要几个就选择几个就好。
我们先看看什么是选择排序

选择排序的基本思想是:每一趟（如第i趟）在后面n-i+1 (i= 1,2,…", n- 1)个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完，待排序元素只剩下1个，就不用再选了。

我下面举个简单的例子，就以我们题目中的示例为例：
nums=[4,5,1,6,2,7,3,8]

• 第一趟排序我们先确定第一个最小值（i=0）：min初始值为nums[i]=nums[0]=4,然后在下标i+1~length-1范围内（1 ~7）查找比min还要小的最小值，最后发现下标为2时，min最小，我们让num[i]与nums[2]交换，第一次的结果为：[1,5,4,6,2,7,3,8]
• 第二趟排序（i=1），min初始值为nums[i]=nums[1]=5，在下标i+1~length-1范围内找（2 ~7），发现下标为4时，min取得最小值，交换nums[i]与nums[4]，第二趟排序结果为:[1,2,4,6,5,7,3,8]
• 第三趟排序（i=2），注意我们的i是数组下标，从 0开始，别搞糊涂了，min初始值为nums[i]=nums[2]=4,在下标为i+1~length-1即(3,7)范围内找最小值，发现下标为6时取得最小值，交换nums[i]与nums[6]，第三趟排序结果：[1,2,3,6,5,7,4,8]

---

• 空间效率：仅使用常数个辅助单元，故空间效率为0(1)
• 时间效率：在 排序过程中移动的 *** 作特别少，最好的情况为0，即已经是排序好的，但是元素间的比较次数与序列的初始状态无关，始终是n(n-1)次，因此 时间复杂度始终是o(n^2)
• 稳定性：在第i趟找到最小元素后，和第i个元素交换，可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变。例如，表L= {2,2,1}，经过一趟排序后L= {1,2,2}，最终排序序列也是L={1,2,2}，显然，2与2的相对次序已发生变化。因此，简单选择排序是一种不稳定的排序方法。

同理下面的过程我就不再赘述
代码实现如下：

    public void selectSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[min] > nums[j]) min = j;
            }
            if (min != i) {
                int t = nums[i];
                nums[i] = nums[min];
                nums[min] = t;
            }
        }
    }