排序之选择排序（C# C++）
目录
1 选择排序
2 排序原理
3 排序步骤
4 代码示例
4-1 C#代码示例
4-2 C++代码示例
1 选择排序
选择排序（Selection Sort）是一种简单直观的排序算法，它的基本思想是每一轮从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
2 排序原理
选择排序的核心原理是通过不断地选择最小（或最大）元素并将其放置到合适的位置，逐步构建有序序列。具体来说，它会将数组分为已排序部分和未排序部分，初始时已排序部分为空，未排序部分为整个数组。每一轮排序会从未排序部分中找出最小（或最大）的元素，然后将其与未排序部分的第一个元素交换位置，这样就使得已排序部分的长度增加 1，未排序部分的长度减少 1，重复这个过程直到未排序部分为空。
3 排序步骤
下面以升序排序为例说明选择排序的步骤：
- 初始状态：给定一个包含
n个元素的数组arr，初始时整个数组都是未排序部分。 - 第一轮选择：
- 从数组的第一个元素开始，遍历整个数组，找出最小的元素。
- 记录最小元素的索引。
- 将最小元素与数组的第一个元素交换位置。此时，数组的第一个元素已经排好序，已排序部分包含 1 个元素，未排序部分包含
n - 1个元素。
- 第二轮选择：
- 从数组的第二个元素开始，遍历剩余的未排序部分，找出最小的元素。
- 记录最小元素的索引。
- 将最小元素与数组的第二个元素交换位置。此时，数组的前两个元素已经排好序，已排序部分包含 2 个元素，未排序部分包含
n - 2个元素。
- 重复选择过程：重复上述步骤，直到未排序部分只剩下一个元素。此时，整个数组就已经排好序。
4 代码示例
4-1 C#代码示例
using System;
namespace ConsoleApplication1
{
internal class Program
{
private static void SelectionSort(int[] arr)
{
if (arr == null || arr.Length < 2) return;
for (int i = 0; i < arr.Length - 1; i++)
{
int minIndex = i;
for (int j = i + 1; j < arr.Length; j++)
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
Swap(arr,i,minIndex);
}
}
private static void Swap(int[] arr, int i, int j)
{
if (i!= j)
{
arr[i] ^= arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] ^= arr[j];
}
}
public static void Main(string[] args)
{
int[] arr = { 2, 5, 7, 9, 3, 1, 4, 6, 8 };
SelectionSort(arr);
foreach (var value in arr)
Console.WriteLine(value);
}
}
}运行结果：
4-2 C++代码示例
#include <iostream>
#include <vector>
// 交换向量中两个位置元素的函数
void Swap(std::vector<int>& arr, int i, int j) {
if (i != j) {
arr[i] ^= arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] ^= arr[j];
}
}
// 选择排序函数
std::vector<int> SelectionSort(std::vector<int> arr) {
if (arr.size() < 2) {
return arr;
}
for (size_t i = 0; i < arr.size() - 1; ++i) {
size_t minIndex = i;
for (size_t j = i + 1; j < arr.size(); ++j) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
Swap(arr, static_cast<int>(i), static_cast<int>(minIndex));
}
return arr;
}
int main() {
std::vector<int> arr = { 2, 5, 7, 9, 3, 1, 4, 6, 8 };
arr = SelectionSort(arr);
for (int value : arr) {
std::cout << value << std::endl;
}
return 0;
}运行结果：
