排序算法之选择排序

概述

选择排序是一种简单直观的排序算法.

它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素, 存放在序列的起始位置，直到全部待排序的数据元素排完. 选择排序是不稳定的排序方法.

选择排序是从序列中选出最大或最小数, 将其放到最前面, 然后继续选择, 故而叫做选择排序, 个人理解.

以升序为例, 选择排序执行步骤如下:

1. 暂定第一个元素为最小元素, 往后遍历, 逐个与最小元素比较, 找到最小元素, 若发现最小者, 与先前的"最小元素"交换位置. 达到更新最小元素的目的.
2. 一趟遍历完成后, 能确保刚刚完成的这一趟遍历中, 最的小元素已经放置在前方了. 然后缩小排序范围, 新一趟排序从数组的第二个元素开始
3. 在新一轮排序中重复第1、2步骤, 直到范围不能缩小为止, 排序完成

形象

其时间空间复杂度如下:

应该不难理解, 直接上代码了.

Java代码实现

代码也很简单, 不做过多解释了, 各位上眼.

/**
 * 选择排序实现数组排序, 从小到大的顺序
 * 
 * @param a
 */
public static void selectSort(int[] a) {
    /* 
     * 1. 选出数组中的最小元素, 与第一个元素交换
     * 2. 将已经进行排序的元素去除, 重复步骤1
     */
    int minIndex = 0;
    // 若数组不存在或没有元素, 直接返回
    if (a == null || a.length == 0) {
        return;
    }
    // 对数组进行遍历, 不需要遍历最后一个元素, 因为后面没有元素进行比较了
    for (int i = 0; i < a.length - 1; i++) {
        minIndex = i;// 记录最小元素下标
        // 遍历当前元素之后的所有数组元素
        for (int j = i + 1; j < a.length; j++) {
            // 寻找其中最小的元素, 记录下标
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }
        // 当发现更小的元素时, 元素互换
        if (minIndex != i) {
            int tmp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = tmp;
        }
    }
}