02 选择排序

算法描述

选择排序是一种简单直观的排序算法，它也是一种交换排序算法，和冒泡排序有一定的相似度，可以认为选择排序是冒泡排序的一种改进。

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

思路：每次从范围内寻找最大值的下标，然后替换到最后边去，与冒泡排序的区别是只交换一次。冒泡则是每此比较都替换。

import java.util.*;

public class SelectionSort {

    public int[] selectionSort(int[] A, int n) {
        sort(A, n);
        return A;
    }

    private void sort(int[] nums, int n) {
        for (int i = 0; i < n - 1; i++) {
            int indexOfMax = 0;
            for (int j = 1; j < n - i; j++) {
                if (nums[j] > nums[indexOfMax]) {
                    indexOfMax = j;
                }
            }
            if (indexOfMax != n - i - 1) {
                swap(nums, indexOfMax, n - i - 1);
            }
        }       
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}

稳定性

用数组实现的选择排序是不稳定的，用链表实现的选择排序是稳定的。
不过，一般提到排序算法时，大家往往会默认是数组实现，所以选择排序是不稳定的。

适用场景

选择排序实现也比较简单，并且由于在各种情况下复杂度波动小，因此一般是优于冒泡排序的。在所有的完全交换排序中，选择排序也是比较不错的一种算法。但是，由于固有的O(n2)复杂度，选择排序在海量数据面前显得力不从心。因此，它适用于简单数据排序。