介绍

选择排序和冒泡排序的算法其实都比较好理解,都是从大到小(从小到大)操作的排序,冒泡排序的区别:冒泡排序通过依次交换相邻两个顺序不合法的元素位置,从而将当前最小(大)元素放到合适的位置;而选择排序每遍历一次都记住了当前最小(大)元素的位置,最后仅需一次交换操作即可将其放到合适的位置。

时间复杂度:

  • 最好情况:O(n^2)
  • 平均情况:O(n^2)
  • 最坏情况:O(n^2)

稳定性:不稳定

额外的空间:O(1)

过程

  1. 在序列中找到最小(大)元素,放到起始位置作为已排序序列;
  2. 从剩余未排序元素中继续寻找最小(大)元素,放到已排序序列的末尾;
  3. 以此类推,直到所有元素均排序完毕;

图示:

宏观过程:

Java实现

/*
 * SelectionSort.java:选择排序
 */

import java.util.Arrays;

public class SelectionSort {
    public static void main(String[] args) {
        int[] a = new int[]{9, 2, 5, 6, 7, 2, 4, 5};
        System.out.println(Arrays.toString(sort(a)));
    }

    private static int[] sort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            int min = i;
            //从i开始遍历数组找到最小值索引
            for (int j = i; j < a.length; j++){
                if (a[j] < a[min]) {
                    min = j;//记录索引
                }
            }
            //交换最小值,该操作很有可能把稳定性打乱,所以选择排序是不稳定的排序算法
            if (min != i) {
                int temp = a[i];
                a[i] = a[min];
                a[min] = temp;
            }
        }
        return a;
    }
}
最后修改:2021 年 04 月 15 日
如果觉得我的文章对你有用,请随意赞赏