算法之路__2、选择排序
程序员文章站
2022-05-12 21:33:46
...
一、解释
选择排序法事实上 是对 定位比较交换法(也就是冒泡排序法) 的一种改进。
基本思想:第1趟,在待排序记录r[1]~r[n]中选出最小的记录,将它与r[1]交换;第2趟,在待排序记录r[2]~r[n]中选出最小的记录,将它与r[2]交换;以此类推,第i趟在待排序记录r[i]~r[n]中选出最小的记录,将它与r[i]交换,使有序序列不断增长直到全部排序完毕。
从以上的 算法思想中可以看出,选择排序是选待排记录中最小的一个放在左侧, 而上一篇博文中写到的冒泡是从待排记录中选择最大的放在右侧。
示例:
初始序列:{49 27 65 97 76 12 38}
第1趟:12与49交换:12{27 65 97 76 49 38}
第2趟:27不动 :12 27{65 97 76 49 38}
第3趟:65与38交换:12 27 38{97 76 49 65}
第4趟:97与49交换:12 27 38 49{76 97 65}
第5趟:76与65交换:12 27 38 49 65{97 76}
第6趟:97与76交换:12 27 38 49 65 76 97 完成
二、代码
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//确定待排区域
for (int i = 0; i < arr.length - 1; i++) {
//指针变量minIndex 表示最小元素下标 以当前位置开始
int minIndex = i;
//从当前位置的下一个开始遍历
//比minIndex位置元素小则 将小位置元素下标设置为minIndex
for (int j = i + 1; j < arr.length; j++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
//将当前位置元素与最小位置元素交换
int tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
上一篇: VIBE|项目踩坑全记录
下一篇: 微信小程序实现圆角矩形按钮