排序算法之简单选择排序(Selection Sort)

排序算法之简单选择排序(Selection Sort)

Scroll Down

基本思想

简单选择排序(Selection Sort)是一种简单直观的排序算法,它的工作原理:首先在未排序元素中找到最小(大)元素,存放到排序序列的起始位置,然后再从剩余未排序元素中记录寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

算法描述

n个记录的简单选择排序可经过(n-1)趟简单选择排序得到有序结果。具体算法描述如下:
1.初始状态:无序区为R[1....n],有序区为空;
2.第i趟排序(i=1,2,3..n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R[i..n]。该趟排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
3.(n-1)趟结束,数组有序化了。

动图演示

简单选择排序

public static int[] selectionSort(int[] array) {
        if (array.length == 0)
             return array;
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[minIndex]) //找到最小的数
                    minIndex = j; //将最小数的索引保存
            }
            int temp = array[minIndex]; //将最小数和无序区的第一个数交换
            array[minIndex] = array[i];
            array[i] = temp;
        }
        return array;
    }

时间复杂度

简单选择排序平均时间复杂度为O(n2),最好时间复杂度为O(n2),最坏时间复杂度为O(n2)。
最好情况:如果待排序元素本来是正序的,则移动元素次数为 0,但需要进行 n * (n - 1) / 2 次比较。
最坏情况:如果待排序元素中第一个元素最大,其余元素从小到大排列,则仍然需要进行 n * (n - 1) / 2 次比较,且每趟排序都需要移动 3 次元素,即移动元素的次数为3 * (n - 1)次。
需要注意的是,简单选择排序过程中需要进行的比较次数与初始状态下待排序元素的排列情况无关。

空间复杂度

简单选择排序使用了常数空间,空间复杂度为O(1)

稳定性

简单选择排序不稳定,比如序列 2、4、2、1,我们知道第一趟排序第 1 个元素 2 会和 1 交换,那么原序列中 2 个 2 的相对前后顺序就被破坏了,所以简单选择排序不是一个稳定的排序算法。

作者:Steven1997
链接:https://www.jianshu.com/p/47170b1ced23
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。