数据结构与算法——选择排序

首先在未排序序列中找到最小/大元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小/大元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法要点

1. 假设第一个元素为最小/大的元素，然后于后续的元素依次比较，遇到比这个更小/大的元素则记录键与值，等到全部比较完成后，就拿到了未排序序列中的最大/小元素，然后与第一个元素交换位置。
2. 执行上述动作，从前向后依次确认最小/大的位置，直到最后一个元素

• 时间复杂度为O(n^2)，与冒泡排序相比，排序时间较为稳定，偏差不会很大。

动画演示

代码示例

package Sort;

public class Sort {
    /**
     * 选择排序(从小到大排序)
     *
     * @param data int[] 数据
     *
     * @return int[]
     **/
    public int[] selectionSort(int[] data)
    {
        int firstIndex;
        int selectionIndex;
        int temp;
        for (int i = 0; i < data.length; i++) {
            firstIndex = i;
            selectionIndex = firstIndex;
            for (int j = i + 1; j < data.length; j++) {
                if (data[j] < data[selectionIndex]) {
                    selectionIndex = j;
                }
            }
            if (firstIndex != selectionIndex) {
                temp = data[firstIndex];
                data[firstIndex] = data[selectionIndex];
                data[selectionIndex] = temp;
            }
        }

        return data;
    }
}