直接选择排序（Straight Selection Sort）
选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放入已排序数列的最后，直到全部记录排序完毕。
直接选择排序是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 即在每一步中选取最小值来重新排列，从而达到排序的目的。（选择+交换）
目录
直接选择排序（Straight Selection Sort）
1、算法描述
基本思想：n个记录的数列的直接选择排序可经过n-1趟直接选择排序得到有序结果。
-
初始状态：无序区为 a[1..n]，有序区为空。
-
第 1 趟排序：在无序区 a[1..n]中从左向右遍历，遇到比第 0 个位置小的值 a[k]，将它与无序区的第 0 个位置 a[0]交换。直到比较到最后一个元素。使 a[1..i]和 a[2..n]分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区。
-
第 i 趟排序：第 i 趟排序开始时，当前有序区和无序区分别为 a[1..i-1]和 a[i..n][1≤i≤n-1]。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第 i 个记录 R[i]交换，使 R[1..i]和 R[i+1..n]分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区。
-
这样，n 个记录的数列的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。
简单选择排序的基本思想：选择 + 交换。
- 从待排序序列中，找到关键字最小的元素；
- 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
- 从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。
因此我们可以发现，简单选择排序也是通过两层循环实现。
- 第一层循环：依次遍历序列当中的每一个元素
- 第二层循环：将遍历得到的当前元素依次与余下的元素进行比较，符合最小元素的条件，则交换。
2、算法分析
2.1、复杂度分析
无论数列初始状态怎样，在第 i 趟排序中选出最小关键字的记录，需做 n-i 次比较，因此，总的比较次数为： n(n-1)/2=O(n^2)。
2.1.1、时间复杂度
- 最好情况O(n^2)
- 最坏情况O(n^2)
- 平均情况O(n^2)：平均来说直接选择排序算法的时间复杂度为O(n^2）
因而，直接选择排序不适合对于数据量比较大的排序应用。
2.1.2、空间复杂度
直接选择排序是一个就地排序，空间复杂度为S(n)=O(1)
2.2、算法稳定性
直接选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序（简排和堆排）是一个不稳定的排序算法。
3、算法实现
-
void straightselectionsort(vector<int>&a)
-
{
-
for (
int i =
0; i < a.size(); i++)
-
{
-
//找出无序队列的最小值
-
for (
int j = i +
1; j < a.size(); j++)
-
{
-
if (a[j] < a[i])
-
{
-
swap(a[i], a[j]);
-
}
-
}
-
}
-
}
4、算法示例
-
#include "stdafx.h"
-
#include <vector>
-
#include <iostream>
-
#include <stack>
-
#include<time.h>
-
using
namespace
std;
-
void straightselectionsort(vector<int>&a)
-
{
-
for (
int i =
0; i < a.size(); i++)
-
{
-
//找出无序队列的最小值
-
for (
int j = i +
1; j < a.size(); j++)
-
{
-
if (a[j] < a[i])
-
{
-
//输出
-
cout <<
'\n' <<
"交换的位置是: " <<
'\t' << i <<
" <-----> " << j <<
'\t' <<
"交换的值是: " << a[i] <<
" <-----> " << a[j] <<
'\n';
-
swap(a[i], a[j]);
-
for (
int i =
0; i < a.size(); i++)
-
{
-
cout << a[i] <<
'\t';
-
}
-
cout <<
'\n';
-
}
-
}
-
}
-
}
-
-
int main()
-
{
-
vector<
int>a;
-
cout <<
'\n' <<
"原顺序: " <<
'\n';
-
a.push_back(
7); a.push_back(
8); a.push_back(
7);
-
a.push_back(
6); a.push_back(
5); a.push_back(
6);
-
a.push_back(
7); a.push_back(
8); a.push_back(
9);
-
for (
int i =
0; i < a.size(); i++)
-
{
-
cout << a[i] <<
'\t';
-
}
-
cout <<
'\n' <<
'\n';
-
cout <<
'\n' <<
"排序过程: " <<
'\n';
-
straightselectionsort(a);
-
cout <<
'\n' <<
"希尔排序: " <<
'\n';
-
for (
int i =
0; i < a.size(); i++)
-
{
-
cout << a[i] <<
'\t';
-
}
-
cout <<
'\n';
-
return
0;
-
}
5、注意
转载：https://blog.csdn.net/qq_35683407/article/details/105926789