90.选择排序(理论分析)

一.选择排序

冒泡排序每相邻的俩个元素之间都会比较交换一次，效率比较慢。这对这个问题所改进的算法叫做选择排序。

二．选择排序的实现思路

首先在一组未排序的数据中假定一个最大或者最小元素，一般是第0个元素。然后在从剩余未排序的元素中寻找最大或最小元素的下标，然后将这个数与第n个数交换。如果第n个数是最大的，就不需要交换。

三.举例

假设现在有一组数据：3，9，1，5，2，要求使用选择排序进行从大到小排序。
步骤：
第一轮循环，先假定第0个元素3为最大元素。并记录下标0。然后逐次比较第0个元素和第一个，第二个，第三个，第四个，也就是元素9，1，5，2的大小。很明显第1个元素9是最大的，记录元素9的下标为1。然后交换俩个数的位置，也就是元素3和元素9的位置。
第一轮循环比较完成后：
9，3，1，5，2

第二轮比较，因为第一次排序选择的是将首元素作为最大值，最终经过互换位置，首元素排序完成，第二次排序就不需要排序首元素。
假定第1个元素3为最大元素。并记录下标1，然后逐次和第二个，第三个，第四个，也就是1，5，2的大小。很明显第三个元素5是最大的，记录元素5的下标3，然后交换俩个数的位置，也就是元素3和元素5的位置。
第二轮循环比较完成后：
9，5，1，3，2

第三轮比较，因为第一次和第二次排序已经把第0和第1个元素排序完成。所以第三次不用排序第0和第1个元素。

假定第2个元素1为最大元素。然后逐次比较第三个，第四个也就是3和2的大小，很明显元素3是最大的，记录元素3的下标3，然后交换俩个数的位置，也就是元素1和3的位置。
第三轮循环完成后：
9，5，3，1，2

第四轮比较，因为前三轮比较已经排序好了第0，1，2个元素，所以第四次排序不用排序这几个元素。
假定第3个元素1是最大元素，然后比较第三个和第四个也就是1和2的大小，和明显元素2是最大的，记录元素2的下标4，然后交换俩个数的位置，也就是元素1和2的位置。
第四轮循环完成后：
9，5，3，2，1

四.视频教程

90.选择算法（理论分析）_哔哩哔哩_bilibili