C++选择排序算法PTA（含实现原理和代码注释）
需积分: 1 102 浏览量
2023-12-11
09:49:12
上传
评论
收藏 97KB PDF 举报
选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是，首先在未排序序列中找到最小
（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元
素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
以下是使用 C++ 实现选择排序的示例代码，代码中包含注释以帮助理解：
这段代码首先定义了一个 selectionSort 函数，该函数接受一个整数数组和其长度作为参数。函数中的第
一个循环用于确定最后一个需要选择的元素的索引。然后在每次循环中，我们假设当前索引的元素是最小
的，并从该索引之后开始查找可能更小的元素。如果我们找到一个更小的元素，我们就更新假设的最小元素
的索引。在每次迭代的末尾，如果最小元素的索引不是当前索引，我们就交换这两个元素的位置。这个过程
会继续，直到我们遍历了整个数组，此时数组应该已经排序完成。
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
// 循环 n-1 次，因为 n-1 是我们需要选择的最后一个元素的索引
for (int i = 0; i < n - 1; i++) {
// 假设索引 i 的元素是最小的
int minIndex = i;
// 然后从 i+1 开始查找最小元素的位置
for (int j = i + 1; j < n; j++) {
// 如果找到比假设的最小元素更小的元素，则更新最小元素的位置
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 如果最小元素的位置不是 i，则交换位置
if (minIndex != i) {
swap(arr[i], arr[minIndex]);
}
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
资源评论
