八大排序算法--简单选择排序

1、算法思想

简单选择排序是一种选择排序

选择排序:每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。

简单排序的大致处理流程为:

  • 从待排序序列中,找到关键字最小的元素;
  • 如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换;
  • 从余下的 N - 1 个元素中,找出关键字最小的元素,重复(1)、(2)步,直到排序结束。

如图所示,每趟排序中,将当前 i 小的元素放在位置 i 上。

2、代码

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
# -*- coding:utf-8 -*-

def SelectSort(input_list):
'''
函数说明:简单选择排序(升序)
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)

3、算法分析

3-1、性能分析

其中,N2为$N^2$。

3-2、时间复杂度

简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素,则比较次数总是N (N - 1) / 2

而移动次数与序列的初始排序有关。当序列正序时,移动次数最少,为 0.

当序列反序时,移动次数最多,为3N (N - 1) / 2。

所以,综合以上,简单排序的时间复杂度为 O($N^2$)

-------------The End-------------
谢谢大锅请我喝杯阔乐~