选择排序算法原理与实现

概述

选择排序（Selection Sort）是一种基础的排序算法，其核心思路是：在每一轮遍历中，从剩余未排序元素中选出最小（或最大）值，并将其放置在已排序序列的末端。

对于排序算法的实现，遵循由局部到整体的思路，先排序好一趟或一个元素，再排列多趟或全部元素。

一、选择排序的工作原理

以排序升序数组为例，工作原理如下：

• 初始化：假设当前数组中，前部分是已经排好序的，后部分是未排序的。
• 寻找最小（或最大）值：遍历未排序的部分，找出其中的最小值（或最大值）。
• 交换位置：将找到的最小值与当前未排序部分的第一个元素交换。
• 重复：缩小未排序部分的范围，重复以上步骤，直到整个数组排好序。

以上述数组为例，假设有一个待排列的数组为：[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]。

• 第一轮排序：当前未排序部分 [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]，最小的值是 2。将 2 和未排序部分的第一个元素 3 交换，数组变为 [2, 44, 38, 5, 47, 15, 36, 26, 27, 3, 46, 4, 19, 50, 48]。
• 第二轮排序：当前未排序部分 [44, 38, 5, 47, 15, 36, 26, 27, 3, 46, 4, 19, 50, 48]，最小值是 3。将 3 和未排序部分的第一个元素 44 交换，数组变为 [2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]。
• 第三轮排序：当前未排序部分 [38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]，最小值是 4。将 4 和未排序部分的第一个元素 38 交换，数组变为 [2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]。
• 第四轮排序：当前未排序部分 [5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]，最小值是 5（它已经排好序，所以不需要交换）。数组仍然是 [2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]。
• 第五轮排序：当前未排序部分 [47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]，最小值是 15。将 15 和未排序部分的第一个元素 47 交换，数组变为 [2, 3, 4, 5, 15, 47, 36, 26, 27, 44, 46, 38, 19, 50, 48]。
• 第六轮排序：当前未排序部分 [47, 36, 26, 27, 44, 46, 38, 19, 50, 48]，最小值是 19。将 19 和第一个元素 47 交换，数组变为 [2, 3, 4, 5, 15, 19, 36, 26, 27, 44, 46, 38, 47, 50, 48]。
• 第七轮排序：当前未排序部分 [36, 26, 27, 44, 46, 38, 47, 50, 48]，最小值是 26。将 26 和第一个元素 36 交换，数组变为 [2, 3, 4, 5, 15, 19, 26, 36, 27, 44, 46, 38, 47, 50, 48]。
• 第八轮排序：当前未排序部分 [36, 27, 44, 46, 38, 47, 50, 48]，最小值是 27。将 27 和第一个元素 36 交换，数组变为 [2, 3, 4, 5, 15, 19, 26, 27, 36, 44, 46, 38, 47, 50, 48]。
• 第九轮排序：当前未排序部分 [36, 44, 46, 38, 47, 50, 48]，最小值是 36（它已经排好序，所以不需要交换）。数组仍然是 [2, 3, 4, 5, 15, 19, 26, 27, 36, 44, 46, 38, 47, 50, 48]。
• 第十轮排序：当前未排序部分 [44, 46, 38, 47, 50, 48]，最小值是 38。将 38 和第一个元素 44 交换，数组变为 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 44, 47, 50, 48]。