Java之选择排序详解
前言
前面写了冒泡排序、插入排序,这里在写一下一样作为简单排序的选择排序。选择排序就是在一次遍历过程中找到最小元素的位置(下标),然后把改元素放到数组的首要位置。
一、 选择排序思想
选择排序的思想也很简单:
- 从待排序序列中,找到关键字最小的元素;起始假定第一个元素为最小
- 如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换;
- 从余下的 N - 1 个元素中,找出关键字最小的元素,重复1,2步,直到排序结束。
二 、 选择排序原理动画
三、 选择排序空间复查度、辅助空间、稳定性
- 选择排序的算法时间平均复杂度为O(n²)。
- 选择排序空间复杂度为 O(1)。
- 选择排序为不稳定排序。
四、 选择排序Java实现
import java.util.Arrays;
import java.util.Objects;
public class ChooseSort {
/***
* 交换数组索引1和索引2的值
* @param arr 数组
* @param index1 索引1
* @param index2 索引2
*/
public static void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
/***
* 选择排序
* @param ints
*/
public static void chooseSort(int[] ints) {
Objects.requireNonNull(ints);
for (int i = 0; i < ints.length - 1; i++) {
// 记录最小值的下表(索引)
int minValueIndex = i;
for (int j = i + 1; j < ints.length; j++) {
// 如果最小值
if (ints[minValueIndex] > ints[j]) {
minValueIndex = j;
}
}
// 交换
swap(ints, minValueIndex, i);
}
}
public static void main(String[] args) {
int[] ints = new int[]{29, 88, 33, 20, 57, 76};
chooseSort(ints);
Arrays.stream(ints).forEach(System.out::println);
}
}
结果:
20
29
33
57
76
88
五、总结
总的来说,选择排序的重点在每次循环过程中找到最小元素(项)的位置(下标),然后和当前循环中首位置坐交换。只要把握着这个点一般是不会错的。
但是在外层选中的终止条件一定不要写成 "int i = 0; i < ints.length - 1; i++" , 这要会出现数据下标越界。
转载请注明:流年似水 » Java之选择排序详解