C++实现选择性排序(SelectionSort)
选择性排序(Selection Sort)是计算机科学中一种简单直观的排序算法。它的工作原理是:首先在未排序的数列中找到最小(大)的元素,然后将其存放到数列的起始位置,接着再从剩余的未排序元素中继续寻找最小(大)的元素,然后放到已排序序列的末尾。以此类推,直到所有元素均被排序完毕。
具体的实现步骤如下:
- 在未排序的数列中找到最小元素。
- 将其存放到数列的起始位置。
- 从剩余未排序的元素中继续寻找最小元素。
- 将其存放到已排序序列的末尾。
- 以此类推,直到所有元素均被排序完毕。
以下是C++代码实现以及相关注释:
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
int i, j, min_idx;
// 依次遍历数组元素
for (i = 0; i < n - 1; i++) {
// 找到未排序区域中最小元素的下标
min_idx = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// 将未排序区域中最小元素放到已排序序列的末尾
swap(arr[min_idx], arr[i]);
}
}
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;
}
在本示例中,我们定义了一个名为 selectionSort()
的排序算法函数来进行选择排序,并将完整的未排序数组作为函数实参传递,以及数组中的元素数目 n
。
使用两个循环来实现选择排序的算法。通过第一个循环遍历数组中的每个未排序元素,通过第二个循环遍历未排序区域中的元素,并找到最小元素的下标。然后将未排序区域中的最小元素放到已排序序列的末尾,以达到排序的目的。
以下是示例,更具体地展示了本算法的工作原理:
示例1:
假设输入的未排序数组为 {64, 25, 12, 22, 11}。在第一次循环之后,我们可以通过找到最小的元素(11)并将其放置在数组的开头位置时得到以下结果:
11 25 12 22 64
示例2:
在第二次循环后,我们可以找到最小元素(12)并将其放置在索引 1 的位置,以下是本次循环的结果:
11 12 25 22 64
继续执行以上步骤,直到所有元素都被排序完成,得到如下排序后的数组:
11 12 22 25 64
希望这个C++实现选择性排序(SelectionSort)的教程对你有所帮助。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C++实现选择性排序(SelectionSort) - Python技术站