算法之直接选择排序学习
直接选择排序算法重新学习。
选择排序,每一趟从未排序序列中选择出最小元素,将元素放到已排序序列尾部。
选择排序算法有以下几种:
- 直接选择排序
- 堆排序
直接选择排序算法
- 一次循环,从待排序序列中选择出最小的元素,将元素和已排序序列后面一个元素进行交换
- 重复循环直到排序完成。
直接选择排序代码示例
/**
* 直接选择排序
* @param source 待排序序列
*/
public void selectionSort(Integer[] source) {
// 每次循环,选择一个最小元素
for (int i = 0; i < source.length - 1; i++) {
// 待排序第一个元素当做是最小值
int min = i;
// 从待排序第二个元素开始往后找比min小的元素
for (int j = i + 1; j < source.length; j++) {
// 找到了比min小的元素后,赋值给min
if (source[j] < source[min]) {
min = j;
}
}
// 一次循环后,将待排序第一个元素和min进行交换
if (min != i) {
Integer temp = source[i];
source[i] = source[min];
source[min] = temp;
}
}
}
public static void main(String[] args) {
Integer[] array = new Integer[] {38, 55, 65, 97, 27, 76, 27, 13, 19};
System.out.println("before: " + Arrays.asList(array));
new SelectionSort().selectionSort(array);
System.out.println("after: " + Arrays.asList(array));
}
直接选择排序算法分析
时间复杂度
- 时间复杂度为$O(n^2)$
空间复杂度
算法中使用一个temp变量占用一个存储单元,空间复杂度为O(1)
算法的稳定性
在直接选择排序算法中,相等的元素比较后,会改变它们原有次序,因此直接选择排序算法是不稳定的。
适用场景
- 数据比较少的时候,可以使用直接选择排序
缺点
- 直接选择排序选择最小值的效率比较低,需要遍历未排序的子序列,只有比较完所有元素才能找到最小值。
- 每次循环将最小值放到前面之后,剩余元素仍旧需要再次遍历比较,重复比较。
参考内容
- 《数据结构(Java版)》