第67课　经典之选择排序

经典之选择排序（数组、选择排序）

选择排序是一种简单但强大的排序算法，它可以帮助我们对一组存储在数组中的数字进行排序。选择排序的工作方式很简单。它在每一轮中找到数组中未排序部分的最小元素，然后将其与未排序部分的第一个元素交换位置。不断重复这个过程，每次都将一个数组元素放到正确的位置，直到整个数组排序完成。

我们的任务是运用选择排序的方法将数组int arr[15]={23,45,12,24,67,16,8,98,54,43,46,45,109,68,86}按照从小到大的顺序排列。

核心思想

不断找到数组中未排序部分的最小元素或最大元素，然后将其与数组中未排序部分的第一个元素交换位置。

可以将要排序的数组看作两个序列：一个是已排列序列，一个是未排列序列。每次从未排列序列中通过依次比较找出最小元素或最大元素，按照顺序放入已排列序列中，当未排列序列的元素全部放入已排序序列中时，排序就完成了。

选择排序的基本操作：

（1）每轮比较找出最大或最小元素。

（2）依次将最大或最小元素排在前面。

选择排序法的推演

来吧，试试对9、5、8、6、3这组数字进行一次选择排序，看看有什么不同。

同样按照从小到大的顺序排列。

1．第一轮开始

（1）第一波，将第一个元素设为最小值min。

（2）第二波比较min（9）和5。

（3）第三波比较min（5）与8。

（4）第四波比较min（5）与6。

（5）第五波比较min（5）与3。

（6）最后将最小值3所在的元素与第一个元素9互换位置。

2．第二轮，比较未排序数字，取出未排序中的最小值

（1）第一波，取未排序第一个元素5设为min。

（2）第二波比较min（5）与8。

（3）第三波比较min（5）与6

（4）第四波比较min（5）与9

（5）这波比较依旧是5最小，所以不用交换位置。

3．第三轮，比较未排序数字，取出未排序中的最小值

（1）第一波，取未排序第一个元素8设为min。

（2）第二波比较min（8）与6。

（3）第三波比较min（6）与9。

（4）最后将未排序最小值6所在的元素与未排序第一个元素8互换位置。

4．第四轮，比较未排序数字，取出未排序中的最小值

（1）第一波，取未排序第一个元素8设为min。

（2）第二波比较min（8）与9。

（3）最后依旧是8最小，所以不用换位置。

（4）只剩最后一个数字了，无须继续比较，排序结束。

敲黑板

关键来啦，需要几轮？需要几波？

一起来总结和思考：

（1）5个数字，每一轮需要找出一个最小值，总共花费4轮。如果有n个数字，确定了n-1个数字的正确排序，也就完成了n个数字的排序。每轮找出一个最小值，全部确定需要n-1轮。

（2）每一轮又进行了多波的比较呢？5个数字一轮比较需要4波。比较波数比剩余需要比较的数字的数量少1。但是不是从头开始，而是从n-轮数开始。例如，第二轮是从第二个元素开始的。

（3）每一轮取出较小的值，依次比较寻找更小的值，以确定本轮的最小值。

程序逻辑

来吧，根据总结和思考选择排序的基本操作，我们编写代码。

假设有n个数字进行排序，组合成数组arr[n]。

（2）每轮需要比剩余需要比较的数字的数量少1波的比较。

但是有一点需要注意，比较不是从数组下标0开始，而是从数组下标i开始，那到什么时候结束呢？也是到最后一个数字的数组下标为n-1时结束。

（3）已进入外层循环，就需要将剩余的第一个元素设为最小值，同时为了便于后续的位置互换，需要记录最小值的位置。

（4）如果遇到更小值，则将更小值替换min，并重新记录位置。

（5）如果最小值不是第一位，则需要将最小值和第一位互换位置，第一位就是i所在的位置。

选择排序

运行程序：

巩固练习

（1）选择排序的工作原理是什么？（）

A．将数组的元素按字母顺序排列

B．多次遍历数组，找到未排序部分的最小或最大元素，并将其移到已排序部分的一端

C．随机重新排列数组的元素

D．将数组的元素反转

（2）如果对一个有100个元素的数组进行选择排序，它将执行多少次比较操作？（）

A．100

B．99

C．4950

D．9900

（3）假设你有一个班级的10位学生成绩（整数），想用选择排序将成绩按从高到低的顺序排序。请编写一个C++程序，对输入的10个成绩使用选择排序进行排序，并输出结果。

样例输入：

样例输出：