选择排序


选择排序

核心思想:将数据分为 “未排序区间” 和 “已排序区间”,每次在“未排序区间”找到最小的元素,追加到已排序区间的末尾。

如下图所示:

初始数组 「4,5,2,1,3」;

初始,未排序区间大小为 0, 从 0 开始,遍历数组,找到最小元素,放在 0 的位置。

第二次,从下标 1 开始,找最小的元素,放到 1 的位置。

…..

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class 选择排序 {

public static void main(String[] args) {
int[] arr = {5, 1, 11, 2, 0, 6, 9, 4};
sort(arr);
System.out.println(Arrays.toString(arr));
}

public static void sort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int index = i;
for (int j = i; j < arr.length; j++) {
if (arr[index] > arr[j]) {
index = j;
}
}
int tmp = arr[index];
arr[index] = arr[i];
arr[i] = tmp;
}
}
}

排序三问

1 是原地排序吗

选择选择,顾名思义,就是每次选择最小的,然后追加到“已排序区间” 的末尾。没有使用其他的恐惧,所以,是原地排序算法。

2 是稳定的排序吗

假设现在有一组数据 {2,3,2,4,5,1,0,7};

我们先将 0 和 1 放到了正确的位置,注意,第一个 2 的位置 和 第二个 2 的位置就变了,所以,就不稳定了。

正因为如此,选择排序,相对于冒泡和插入,显得不那么厉害了。

3 种时间复杂度是多少?

最好时间复杂度,如果本身就是有序的,时间复杂度是 线性 On。

最坏时间复杂度,如果是满逆序的,时间 复杂度是指数级的,On^2.

平均时间复杂度,如果数据有序度为 满有序度/2, 时间复杂度是多少呢?我们看上面,可以知道,选择排序,每次都会找到一个最小的值,这次遍历可以认为是 On,n 次 On,就是 On^ , 因此,他的时间复杂度是 On^2.

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×