选择排序

思想(理解)

遍历数组,找到最小的元素,把它放在数组的第一个位置(即与之交换);再从剩下的元素中找到最小的元素,把它放在数组的第二个位置……依此类推,直到整个数组排序完毕。

代码实现

按照思想,一步一步即可写出。(这是最简单的排序算法)
下面以部分代码一步一步实现,把nums数组排序。

a.在数组中,找到最小的元素:

    // min用于标记最小元素的下标
    int min = 0;
    for(int j = 0;j < nums.length;j++){
        // 发现有更小的元素
        if(nums[j] < nums[min]){
            min = j;// 把它记为最小
        }
    }

b.把找到的最小元素min放在数组的第一个位置:

    int t = nums[0];
    nums[0] = nums[min];
    nums[min] = t;

上面的是排序一次的情况,一共需要进行N次(即nums.length次)才能把整个数组排序完成。
所以加上这句
for(int i = 0;i < nums.length;i++)

对于每个元素都进行这样的遍历,同时注意一下细节,修改修改,即得整个选择排序的代码。

    for(int i = 0;i < nums.length;i++){
        int min = i;
        // 这里遍历的起点是除了已排序的元素外"剩下的元素"
        for(int j = i;j < nums.length;j++){
	    // 找最小元素
            if(nums[j] < nums[min]){
                min = j;
            }
        }
	// 交换
        int t = nums[i];
        nums[i] = nums[min];
        nums[min] = t;
    }

具体步骤

int[] nums = new int[]{
    4, 8, 1, 6, 5, 7
};

以排序上面数组为例,用表格展示全过程:
image.png

其中,i表示当前遍历到的元素,min表示指向的最小元素。
其中*表示已经排序的元素。
这里是用excel表格做的,不太好看,可以手动画画,虽然有、烦,但是可以清晰地知道它是怎么运行的。

效率

我们可以试着把代码提交到leecode上面,发现测试通过,如下图。

1598278786537

ummmmm发现它的效率似乎不怎样,我们可以结合代码&排序的过程一同分析一下。

对于交换次数来说,每次排序都是找到一个“最小”元素,然后放在对应的位置上,要想排序整个数组,则这个过程需要进行nums.length次,即N次。

对于比较次数来说,我们可以从数学的角度、或者图形化的角度来说。

元素总数有N个,
当排序第一个元素的时候,是不是从剩下的N-1里面比较出最小的元素,然后放到数组的第一个位置上?
当排序第二个元素的时候,是不是从剩下的N-2里面比较出最小的元素,然后放到数组的第二个位置上?
……

因此,总的比较次数为:
$(N-1)+(N-2)+(N-3)+...+2+1=N(N-1)/2$

即$N^2/2$。
(同时这里也可以再次看到,每轮交换一次,就是上面的“放元素”的动作,总共需要交换N次)


还有一种方法就是画出一次比较的过程,观察它的变化。 比如上面的图片,可以看到对角线及其以上的元素,都是要比较(找出最小元素的),也可以从图中观察出来比较次数为$N^2/2$。

小特点

可以从代码中发现,无论是一个乱序数组,还是一个已排序数组,它排序完成的时间都是一样长的!上一轮扫描不能为下一轮提供任何信息,运行时间与输入无关
但是,它的交换次数是最少的(移动数据次数最少),其交换次数为$N$次,与数组的长度是线性关系。对于其它算法,至少都是$NlgN$或$N^2$。