"基础算法 第2章 数据排序(C++版)-2020-01-17.pdf"
本文档详细介绍了数据排序的基础知识,特别是选择排序算法的原理和实现。选择排序是一种简单直观的排序算法,它的基本思想是在未排序的序列中找到最小(或最大)的元素,放到序列的起始位置,然后再从剩余未排序的元素中继续寻找最小(或最大)的元素,然后放到已排序序列的末尾,以此类推,直到所有元素均排序完毕。
选择排序的过程可以分为以下几步:
1. 初始化:读入待排序的数据并存储在一个数组中。
2. 遍历:对于数组中的每个位置 i (从0到n-1),执行以下操作:
- 在未排序的部分(即从位置 i+1 到 n)中找到最小(或最大)的元素。
- 将找到的最小(或最大)元素与位置 i 的元素交换,确保当前位置 i 存放的是未排序部分的最小(或最大)元素。
3. 继续遍历,直到所有的元素都被放置在正确的位置上。
例如,在给定的示例中,初始数组为 [49, 38, 65, 97, 76, 13, 27, 49, 61, 32, 74, 9],经过7次遍历和交换后,数组变为 [13, 27, 38, 49, 49, 56, 61, 65, 74, 76, 97, 99],完成了从小到大的排序。
为了实现选择排序,我们可以编写如下的C++代码:
```cpp
#include<iostream>
using namespace std;
const int MAXN = 10001;
int main() {
int n, k, i, j;
float temp, a[MAXN];
cin >> n;
for (i = 0; i < n; i++)
cin >> a[i]; // 输入n个数
for (i = 0; i < n; i++) { // i 控制当前序列中最小值存放的数据位置
k = i;
for (j = i + 1; j < n; j++) { // 在当前无序区 a[i..n] 中选最小的元素 a[k]
if (a[j] < a[k])
k = j;
}
if (k != i) // 交换找到的最小元素
swap(a[i], a[k]);
}
// 输出排序后的数组
for (i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}
```
这个程序首先读取用户输入的整数 n 和 n 个数字,然后使用两层循环实现选择排序。外层循环 i 负责控制当前序列中最小值的存放位置,内层循环 j 则负责在剩余的无序部分中寻找最小元素。如果找到的最小元素位置不是 i,那么就交换这两个元素,确保 i 位置始终存放当前未排序部分的最小元素。最终,程序会输出排序后的数组。
选择排序的时间复杂度为 O(n^2),在所有数据已经有序的情况下,仍然会进行 n(n-1)/2 次比较,因此效率相对较低。尽管如此,由于其简单和易于理解,选择排序在小型数据集或者特定场景下仍有一定的应用价值。在实际开发中,对于大数据量的排序,通常会选择更高效的排序算法,如快速排序、归并排序或堆排序等。