经典的排序算法——选择排序

选择排序（Selection Sort）。它是一种简单直观的排序方法，工作原理如下：

1. 首先，在未排序序列中找到最小（或最大）元素。
2. 将找到的最小（或最大）元素与未排序序列的第一个元素交换位置。
3. 之后，从剩余未排序的元素中继续寻找最小（或最大）元素，并将其与已排序序列末尾的下一个元素交换。
4. 重复上述步骤，每次都是从未排序部分找出当前剩余元素中的最小（或最大）者，并放到已排序序列的末尾。
5. 这个过程会持续进行，直到所有元素都排列到正确的位置上。

以下是C++实现选择排序的示例代码：

#include<iostream>
using namespace std;

void selectionSort(int arr[], int n) {
	for (int i = 0; i < n - 1; i++) { // 外层循环控制需要遍历多少轮来完成排序
		int minIndex = i; // 假设当前最小值在第一个未排序的位置
		// 找到剩余未排序部分中的最小值及其索引
		for (int j = i + 1; j < n; j++) {
			if (arr[j] < arr[minIndex]) {
				minIndex = j; // 更新最小值的索引
			}
		}
		// 如果找到了更小的值，则交换它和当前位置i的值
		if (minIndex != i) {
			swap(arr[i], arr[minIndex]);
		}
	}
}
// 测试函数
void printArray(int arr[], int size) {
	for (int i = 0; i < size; i++)
		cout << arr[i] << " ";
	cout << endl;
}

int main() {
	int arr[] = { 64, 25, 12, 22, 11 };
	int n = sizeof(arr) / sizeof(arr[0]);
	selectionSort(arr, n);
	cout << "Sorted array: \n";
	printArray(arr, n);
	return 0;
}

选择排序的时间复杂度为O(n2)，其中n为待排序数组的长度。由于无论输入数组是否有序，它都会进行n-1轮比较，每轮都需要进行n-i次比较以确定最小值，因此其效率相对较低，尤其是在处理大数据集时。然而，该算法具有原地排序的优点，即不需要额外的空间来存储数据。