选择排序图解
七大排序之选择排序
前言
博主个人社区：开发与算法学习社区
博主个人主页：Killing Vibe的博客
欢迎大家加入，一起交流学习~~
一、直接选择排序
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
1.1 算法图解
每次从无序区间选择一个最大或者最小值的一个元素，放在无序区间的最后或者最前，直到待排序的所有元素排序完毕。
代码如下 ：
public static void selectionSort(int[] arr) {
// 最开始无序区间[i...n)
// 有序区间[]
// 最外层的for循环指的循环走的趟数，每走一趟外层循环，就有一个最小值放在了正确的位置
for (int i = 0; i < arr.length - 1; i++) {
// min指的是最小元素的索引下标
int min = i;
// 内层循环在查找当前无序区间的最小值索引
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// j对应的元素比当前最小值还小
min = j;
}
}
// min这个变量一定保存了当前无序区间的最小值索引
// 有序区间[0..i) + 1
// 无序区间[i..n) - 1
swap(arr,i,min);
}
}
1.2 算法稳定性
拿 9，2，5(a)，7，5(b)，4，3，6 为例子：
【其中a，b用来标记经过排序后是否改变前后顺序，来检测稳定性】
for（int i = 0 ；i<arr.length ; i++） 【外层循环】
最开始时，待排序的数组（无序区间）为：[i…n)
已排序的数组(有序区间) [ ] => 区间中没有任何元素
==外层每一次排序：==
- 有序区间 [0…i） +1
- 无序区间 [i…n) -1
选择无序区间的最小值，放在了无序区间的最开始位置
-
进行第一次排序：序列变成：2，9，5(a), 7, 5(b), 4, 3, 6
-
进行第二次排序：序列变成：2，3，5(a)，7，5(b)，4，9，6
-
进行第三次排序：序列变成：2，3，4，7，5(b)，5(a)，9，6
此时5（a）和5（b）的先后顺序就改变了。
选择排序在是排序过程中无法保证相同的元素的先后顺序的。
所以选择排序不是一个稳定性的算法。
二、双向选择排序
之前选择排序一次只能选择一个最小值或者最大值，一次只选一个元素放在正确位置。
我现在一次选两个。
每次从无序区间中选出最小值和最大值，存放在无序区间的最开始和最后面位置，重复上述过程~~
代码如下：
public static void selectionSortOP(int[] arr) {
int low = 0;
int high = arr.length - 1;
// low == high => 无序区间只剩下最后一个元素，其实整个数组已经有序了。
while (low < high) {
int min = low;
int max = low;
for (int i = low + 1; i <= high; i++) {
if (arr[i] < arr[min]) {
min = i;
}
if (arr[i] > arr[max]) {
max = i;
}
}
// 此时min对应了最小值索引，交换到无序区间的最前面
swap(arr,min,low);
// 边界条件 low == max
if (max == low) {
max = min;
}
swap(arr,max,high);
low ++;
high --;
}
}
==注意事项：==
注意代码中的边界条件：
// 边界条件 low == max
if (max == low) {
max = min;
}
解释：
拿一串数字举例：
正常经过一次过程可以放两个元素到正确位置：
但是在这个交换过程中：
若恰好max的索引就是low的索引，如图，最大值本来是9，但是经过交换，9到了2原本的位置，此时需要把max索引指针更新为2的位置，也就是min的位置。【不然max还是指向开头的2，那最大值就错了】
总结
以上就是选择排序的图解和代码，有什么疑问可以私信博主~有帮助的话可以关注博主后续更新。
- 点赞
- 收藏
- 关注作者
评论（0）