=================
== Time Stream ==
=================
一个小学生

算法之直接选择排序学习

直接选择排序算法重新学习。

选择排序,每一趟从未排序序列中选择出最小元素,将元素放到已排序序列尾部。

选择排序算法有以下几种:

  • 直接选择排序
  • 堆排序

直接选择排序算法

  1. 一次循环,从待排序序列中选择出最小的元素,将元素和已排序序列后面一个元素进行交换
  2. 重复循环直到排序完成。

直接选择排序代码示例

/**
     * 直接选择排序
     * @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版)》