一、前言
简单选择排序是一种选择排序。
选择排序：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。
二、算法思想
简单排序很简单，它的大致处理流程为：
- 从待排序序列中，找到关键字最小的元素；
- 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
- 从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。
动态效果示意图：
举例说明，处理过程示意图如下所示：
如图所示，每趟排序中，将当前第 i 小的元素放在位置 i 上。
1、代码
C++：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #include <iostream> #include <vector> using namespace std; // 简单选择排序 vector<int> SelectSort(vector<int> list){ // 需要遍历获得最小值的次数 // 要注意一点，当要排序 N 个数，已经经过 N-1 次遍历后，已经是有序数列 vector<int> result = list; for (int i = 0; i < result.size(); i++){ // 用来保存最小值得索引 int index = i; // 用来保存最小值得索引 for (int j = i + 1; j < result.size(); j++){ if (result[index] > result[j]){ index = j; } } if (index == i){ continue; } // 将找到的第i个小的数值放在第i个位置上 swap(result[i], result[index]); cout << "第" << i + 1<< "趟:\t"; for (int i = 0; i < result.size(); i++){ cout << result[i] << " "; } cout << endl; } return result; } void main(){ int arr[] = { 6, 4, 8, 9, 2, 3, 1 }; vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0])); cout << "排序前" << endl; for (int i = 0; i < test.size(); i++){ cout << test[i] << " "; } cout << endl; vector<int> result; result = SelectSort(test); cout << "排序后" << endl; for (int i = 0; i < result.size(); i++){ cout << result[i] << " "; } cout << endl; system("pause"); } |
运行结果：
Python：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | # -*- coding:utf-8 -*- def SelectSort(input_list): ''' 函数说明:简单选择排序（升序） Author: www.cuijiahua.com Parameters: input_list - 待排序列表 Returns: sorted_list - 升序排序好的列表 ''' if len(input_list) == 0: return [] sorted_list = input_list length = len(sorted_list) for i in range(length): min_index = i for j in range(i + 1, length): if sorted_list[min_index] > sorted_list[j]: min_index = j if min_index == i: continue temp = sorted_list[i] sorted_list[i] = sorted_list[min_index] sorted_list[min_index] = temp return sorted_list if __name__ == '__main__': input_list = [6, 4, 8, 9, 2, 3, 1] print('排序前:', input_list) sorted_list = SelectSort(input_list) print('排序后:', sorted_list) |
运行结果同上。
三、算法分析
1、简单算法排序性能
其中，N2为N^2。
2、时间复杂度
简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则比较次数总是N (N - 1) / 2。
而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0.
当序列反序时，移动次数最多，为3N (N - 1) / 2。
所以，综合以上，简单排序的时间复杂度为 O(N^2)。
3、空间复杂度
简单选择排序需要占用 1 个临时空间，用于保存最小值得索引。
本站整理自：
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
2018年1月23日 下午2:54 沙发
temp = sorted_list[i]
sorted_list[i] = sorted_list[min_index]
sorted_list[min_index] = temp
我把这段代码封装了一下
def sort_swap(a,b):
tmp = a
a = b
b = tmp
，为什么结果就不对了？？
2018年1月23日 下午3:03 1层
@明明是我先的 调用sort_swap之后，你看数据交换了吗？得改变sort_list列表的值啊。
2018年1月23日 下午3:18 2层
@Jack Cui 是的呢我之前是这样的 sort_swap(sort_list[min_index],sort_list[i])，
改成sort_list[min_index],sort_list[i] = sort_swap(sort_list[min_index],sort_list[i])就可以了
额，想复杂了，算了
2018年1月23日 下午3:26 3层
@明明是我先的 多折腾是好事~
2018年11月16日 上午11:25 板凳
你好，你这里写到的“而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0.”，我认为选择排序运行时间不受输入序列的影响，即便是序列正序，移动次数还是需要自己和自己进行一次移动操作，从而不论序列是怎样的，移动次数都为N
2018年11月16日 上午11:28 1层
@夹饼豆浆 有关的，如果真序，只需要比对，但无需移动。这个移动的意思是交换两个元素的位置。
2018年11月16日 上午11:36 2层
@Jack Cui 正序的情况下，内部循环结束后，不是仍然要进行一次交换的操作吗？
2018年11月16日 下午12:03 3层
@夹饼豆浆 哦哦，是代码有问题，应该加个if判断，过会儿修改下。感谢。
2018年11月16日 下午12:19 3层
@夹饼豆浆 已更正。
2019年1月5日 下午4:23 地板
师兄,我这里是选择这样子弄，用break会直接退出循环~
if min_index == i:
continue
sorted_list[i],sorted_list[min_index]=sorted_list[min_index],sorted_list[i]
2019年1月5日 下午5:53 1层
@chris_33 不过你这是continue吧。python支持这么赋值。
2019年1月5日 下午6:58 2层
@Jack Cui 我是用的continue来的😂表达失误
2019年1月5日 下午7:01 3层
@chris_33 continu没有跳出循环啊。只是跳出来当前循环。
2019年1月6日 下午8:59 4层
@Jack Cui 你换下数组，用[50, 123, 543, 187, 49, 30, 0, 2, 11, 100]，就会知道错在哪里了，我可能表达不太准确了
2019年1月6日 下午9:04 1层
@chris_33 哦哦，get已更正，感谢。
2019年1月6日 下午9:07 2层
@Jack Cui 互相学习~
2019年4月14日 下午10:22 4楼
稳定性为什么是不稳定呢？每次找到最小值，相同的取前面一个，相对位置没有发生改变啊
2019年4月15日 上午9:59 1层
@youyounow 按照找最小值，与无序区首部交换的思想则不稳定：
排序前：
2,4,4*,3
排序后：
2,3,4*,4