算法分析：什么是选择排序

2011年，C语言老师给我们讲选择排序。

....

我一直很忙，很忙。但是却不知道在忙些什么？

似乎甚至几年的时间都没有接触选择排序。

2019年春节，一次偶然的某一个晚上，再一次看了一次选择排序的过程。

什么是选择排序呢？

选择排序是通过在无序区域内查找最小（或者最大）的元素。并且把这个元素放在数列的起始位置。那么这个元素已经是构成一个有序区域。接下来只要把剩下的无序区域内的元素继续找出最小（或者最大）的元素。同样放置在有序区域的尾巴...依次类推，直到所有的元素全部进入有序区域内。

我想通过一组数据来阐述选择排序的过程。

• 第一轮排序开始。此时所有元素处于无序区域。在无序区域中找出最小的[元素1] 。并且把[元素1] 与无序区域内的第一个元素交换。[元素1] 即被加入到有序区域。

• 第二轮排序开始。在无序区域所有元素中找出最小的[元素2]，并且把[元素2]与无序区域内的第一个元素交换。[元素2]即被加入到有序区域。

• 第三轮排序开始。在无序区域所有元素中找出最小的[元素3]，由于[元素3]就是无序区域的第一个元素，因此不交换。[元素3]加入到有序区域。

   ....

以此类推，重复以上的过程，直到第7轮排序结束之后，此时在有序区域内的元素有8个，元素总个数有7个，最后一个自然成为有序区域的元素。

• 每经过一轮排序，有序区域内的元素数量增加1个。
• 如果待排序的元素个数为N。需要经历N-1轮排序。

最后我们使用Java代码来展示上述的算法。

private static void sort() {

        Integer[] data = {6,3,2,1,8,9,7,5};


        for(int i=0; i<data.length-1; i++) {

            int k = i;

            for(int j=k; j<data.length; j++) {
                if(data[j] < data[k]) {
                    k = j;
                }
            }

            if(i != k) {
                int x = data[i];
                data[i] = data[k];
                data[k] = x;
            }

        }

    }

 

从上述代码和流程图中。大致步骤如下：

• 大循环控制轮数，循环的轮数等于元素的个数-1。
• 每一轮，找出无序区域的最小元素，并且把这个最小元素和无序区域的第一个元素交换。