微信公众号做微网站网站开发设置用户

 排序算法-选择排序法（SelectionSort）

1、说明

选择排序法也是枚举法的应用，就是反复从未排序的数列中取出最小的元素，加入另一个数列中，最后的结果即为已排序的数列。选择排序法可使用两种方式排序，即在所有的数据中，若从小到大排序，则将最大值放入第一个位置；若从小到大排序，则将最大值放入最后一个位置。例如，一开始在所有的数据中挑选一个最小项放在第一个位置（假设是从小到大排序），再从第二项开始挑选一个最小项放在第2个位置，以此重复，直到完成排序位置。

2、算法分析

1. 无论是最坏情况、最好情况还是平均情况都需要找到最大值（或最小值），因此其比较次数为：次，时间复杂度为。
2. 由于选择排序是以最大值或最小值直接与最前方未排序的键值交换，数据排序顺序很有可能被改变，因此它不是稳定排序。
3. 因此只需一个额外的空间，所以空间复杂度为最佳。
4. 比较适用于数据量小或有部分数据已经过排序的情况。

3、C++代码 

#include<iostream>
using namespace std;int main() {int data[6] = { 9,7,5,3,4,6 };cout << "原始数据：" << endl;for (int i = 0; i < 6; i++) {cout << data[i] << "  ";}cout << endl;//第1次排序结果：//3  9  7  5  4  6//第2次排序结果：//3  4  9  7  5  6//第3次排序结果：//3  4  5  9  7  6//第4次排序结果：//3  4  5  6  9  7//第5次排序结果：//3  4  5  6  7  9for (int i = 0; i < 5; i++) {for (int j = i + 1; j < 6; j++) {//data[i] < data[j]	从大到小排序的条件//data[i] > data[j]	从小到大排序的条件if (data[i] > data[j]) {	int temp = 0;temp = data[i];data[i] = data[j];data[j] = temp;}}}cout << "最终数据：" << endl;for (int i = 0; i < 6; i++) {cout << data[i] << "  ";}cout << endl;return 0;
}

输出结果