七大排序之选择排序
前言
博主个人社区: 开发与算法学习社区博主个人主页: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,那最大值就错了】
总结
以上就是选择排序的图解和代码,有什么疑问可以私信博主~有帮助的话可以关注博主后续更新。