选择排序法(Selection Sort)是一种简单直观的排序算法。它的工作原理是这样的:
1. 初始状态:假设有n个元素的数组,未排序的序列为R[1..n]。
2. 第一轮:首先在未排序的序列中找到最小(或最大)的元素,存放到排序序列的起始位置,即把未排序序列的第一个元素与第一个元素交换。
3. 第二轮:再在剩余未排序的序列中继续寻找最小(或最大)元素,然后放到已排序序列的末尾。此时,已排序序列和未排序序列的界限已经缩小了1。
4. 重复过程:重复步骤2和步骤3,直到所有元素都排序完毕。
具体步骤如下:
从未排序的序列中找到最小(或最大)的元素。
将这个元素与未排序序列的第一个元素交换。
将未排序序列缩小1,即从第二个元素开始到第n个元素。
重复以上步骤,直到整个序列排序完成。
选择排序的时间复杂度是O(n2),因为它需要遍历整个数组来找到最小(或最大)元素,并且这个操作需要重复n-1次。尽管它的效率不高,但选择排序算法简单易懂,适合小规模数据的排序。
下面是一个选择排序的简单示例:
假设有数组 `arr = [64, 25, 12, 22, 11]`,下面是选择排序的过程:
1. 第一轮:找到最小值11,与第一个元素交换,`arr = [11, 25, 12, 22, 64]`。
2. 第二轮:找到最小值12,与第二个元素交换,`arr = [11, 12, 25, 22, 64]`。
3. 第三轮:找到最小值22,与第三个元素交换,`arr = [11, 12, 22, 25, 64]`。
4. 第四轮:找到最小值25,与第四个元素交换,`arr = [11, 12, 22, 25, 64]`。
5. 第五轮:数组已经排序完成,不需要再进行交换。
最终排序后的数组为 `[11, 12, 22, 25, 64]`。