阅读:0       作者:严长生

简单选择排序算法原理及java实现(超详细)

选择排序是一种非常简单的排序算法,就是在序列中依次选择最大(或者最小)的数,并将其放到待排序的数列的起始位置。

简单选择排序的原理

简单选择排序的原理非常简单,即在待排序的数列中寻找最大(或者最小)的一个数,与第 1 个元素进行交换,接着在剩余的待排序的数列中继续找最大(最小)的一个数,与第 2 个元素交换。以此类推,一直到待排序的数列中只有一个元素时为止。

也就是说,简单选择排序可分为两部分,一部分是选择待排序的数列中最小的一个数,另一部分是让这个数与待排序的数列部分的第1个数进行交换,直到待排序的数列只有一个元素,至此整个数列有序。

这个算法非常简单,其排序过程如图 1 所示。


图 1 简单选择排序的排序过程

其中的方框部分为待排序的数列部分,双下画线的元素为待排序的数列中最小的元素,单下画线的元素为待排序的数列的首元素,每一趟让它们进行交换,最终得到有序数列。

简单选择排序的实现

简单选择排序的实现代码如下:
public class SelectSort {
    private int[] array;
    public SelectSort(int[] array) {
        this.array = array;
    }
   
    public void sort() {
        int length = array.length;
        for (int i = 0; i < length; i++) {
            int minIndex = i;
           
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
           
            if (minIndex != i) {
                int temp = array[minIndex];
                array[minIndex] = array[i];
                array[i] = temp;
            }
        }
    }
   
    public void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
}
通过代码,我们发现这个算法其实挺烂的,而且应该有可以优化的方法,这里先卖个关子。测试代码如下:
public class SortTest {
    public static void main(String[] args) {
        testSelectSort();
    }
    /**
     * 简单选择排序
     */
    private static void testSelectSort() {
        int[] array = {5, 9, 1, 9, 5, 3, 7, 6, 1};
        SelectSort selectSort = new SelectSort(array);
        selectSort.sort();
        selectSort.print();
    }
}

选择排序的特点及性能

由于在简单选择排序中,我们一般在原本的待排序的数组上排序并交换,基本上使用的都是常量级的额外空间,所以其空间复杂度是 O(1)

在最好的情况下,每次要找的最大(或者最小)的元素就是待排序的数列的第1个元素,也就是说数列本身有序,这样我们只需要一次遍历且不需要交换,即可实现一趟排序;而在最坏的情况下,每次在数列中要找的元素都不是第 1 个元素,每次需要交换。比较的次数只与数列的长度有关,而在外部要遍历整个数列,也与长度有关,所以这样的双重循环不管在什么情况下,时间复杂度都是 O(n2)

但由于选择排序不需要一个一个地向前移动,而是直接交换,而比较所消耗的 CPU 要比交换所消耗的 CPU 小一些,所以选择排序的时间复杂度相对于冒泡排序会好一些。

在稳定性方面,对于数列 6、6、1 来说,首先需要找到最小的一个元素与第 1 个元素进行交换,这时数列变为 1、6、6,我们发现两个 6 的顺序已经变了,所以选择排序是一个不稳定的排序算法。

简单选择排序的优化

通过选择排序的思想,我们知道选择排序的一个重要步骤是在待排序的数列中寻找最大(或者最小)的一个元素,那么如何寻找这个元素就成为一个可以优化的点。

另外,我们每次都要寻找两个值中一个是最大值,一个是最小值。这时如果需要将数列从小到大排列,就要把最小值与待排序的数列的第1个元素进行交换,把最大值与待排序的数列的最后一个元素进行交换。这样我们一次就能寻找两个元素,使外层循环的时间缩短了一半,性能也提高了很多。而且通过一次遍历就可以直接找出两个最值,并没有其他性能损耗。这种一次找两个值的选择排序的算法实现,留给读者自己去尝试。

选择排序的适用场景

简单选择排序并不很常用,它只是选择排序的一个思想基础,选择排序还有其他方案可以实现。在理解了简单选择排序之后,我们就更容易理解和学习其他方案了。选择排序的用途非常广泛,之后我们继续讲解如何使用它们。