简单选择排序算法（Java实现）

简单选择排序的基本思想是，假设待排序的元素序列有 n 个：

• 第一趟排序经过 n-1 次比较，从 n 个元素序列中选择关键字最小的元素，并将其放在元素序列的最前面，即第一个位置；
• 第二趟排序经过 n-2 次比较，从剩余的 n-1 个元素中选择关键字最小的元素，并将其放在第二个位置。

以此类推，直到没有待比较的元素，简单选择排序算法结束。

给定一组元素序列，其元素的关键字为(56,22,67,32,59,12,89,26)，简单选择排序的过程如下图所示：


简单选择排序的算法描述如下：

public void SimpleSelectSort()
// 简单选择排序
{
    // 将第 i 个元素与后面的 [i + 1…n] 个元素进行比较，将值最小的元素放在第 i 个位置
    for (int i = 0; i < length - 1; i++) {
        int j = i;
        for (int k = i + 1; k < length; k++) // 值最小的元素的序号为 j
        {
            if (data[k] < data[j])
                j = k;
        }
        if (j != i) // 若序号 i 不等于 j，则需要将序号 i 和序号 j 的元素交换
        {
            int t = data[i];
            data[i] = data[j];
            data[j] = t;
        }
    }
}

简单选择排序在最好的情况下，其元素序列已经是非递减有序序列，不需要移动元素。在最坏的情况下，其元素序列是递减排列的，在每一趟排序的过程中都需要移动元素，因此需要移动元素的次数为 3(n-1)。

简单选择排序的比较次数与元素的关键字排列无关，在任何情况下，都需要比较 n(n-1)/2 次。

综合以上考虑，简单选择排序的时间复杂度为 O(n^2)。简单选择排序的空间复杂度为 O(1)。简单选择排序是一种不稳定的排序算法。