选择排序
# 简单版代码
def select_sort_simple(li):
li_new = []
for i in range(len(li)):
min_val = min(li)
li_new.append(min_val)
li.remove(min_val)
return li_new
li = [3, 2, 4, 1, 7, 8, 87, 76]
print(select_sort_simple(li))
// [1, 2, 3, 4, 7, 8, 76, 87]
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
不推荐使用
致命缺点:
- 生产了 2 个列表,需要更大的内存,数据量大了就炸裂
- 复杂度:
- 这里可不是
On
的复杂度,因为这里还使用了min
和remove
方法,两个方法都会去遍历一次列表,所以min
本身就是On
,remove
也是On
- 随意最终复杂度是:
On²
- 这里可不是
# 比较好的代码
[3, 2, 4, 1, 7, 8, 87, 76]
1
我们首先还是遍历,获取第一个最小的数和第一个位置进行交换 ,交换后,从第二个往后的是无序的,从无序 里继续找再继续换位置。
def select_sort(li):
for i in range(len(li) - 1):
# 记录最小值的位置
# 假定最小值的位置就是第一个,后面进行比较进行交换
min_loc = i
# 偷一次懒,下面没必要从i开始,从i+1开始,自己和自己没必要比
for j in range(i + 1, len(li)):
if li[j] < li[min_loc]:
# 得到新的最小值的下标
min_loc = j
li[i], li[min_loc] = li[min_loc], li[i]
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 复杂度
On²
1
# Go 语言实现的选择排序
package main
import (
"fmt"
)
func main() {
a := []int{3, 2, 4, 1, 7, 8, 87, 76}
for i := 0; i < len(a) - 1; i++ {
min := i
for j := i + 1; j < len(a); j++ {
if (a[j] < a[min]) {
min = j
}
}
// 交换位置
arr[i], arr[min] = arr[min], arr[i]
}
fmt.Println(a)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# C 语言实现选择排序
//
// Created by virus on 2022/5/23.
//
#include "stdio.h"
int main() {
int arr[] = {1, 2, 3, 10, 9, 12, 2100, 12, 4};
// 得到数组的长度
int length = sizeof(arr) / sizeof(arr[0]);
// printf("%d\n", length);
for (int i = 0; i < length - 1; i++) {
int min = i;
for (int j = i + 1; j < length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
for (int i = 0; i < length; ++i) {
printf("%d\t", arr[i]);
}
}
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
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
编辑 (opens new window)
上次更新: 2022/05/23, 23:43:21