选择排序

　　选择排序一般分为简单选择排序和堆排序

　　简单选择排序

• 基本思想

　　    简单选择排序的第i趟是从elem[i]~elem[i-1]中选择第i小的元素，并将此元素放到elem[i]处，也就是说，简单选择排序是从为排序的序列中选择最小的关键字，接着是次小的，以此类推。

• 复杂度分析

　　    最外层for循环共循环n次，内层for循环共循环n-i次，可知总比较的次数为n(n+1)/2=O(n²)，可知时间复杂度为O(n²)

• 代码实现

public int[] sort3(int[] array) {
        // 简单选择排序
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            int tmp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = tmp;
        }
        return array;
    }

　　堆排序

• 基本思想
• 复杂度分析

　　最坏情况下时间复杂度为O(nlogn)，相对快速排序在最坏情况下的时间复杂度为O(n²)，这是最大的优势，而且只占用一个用于交换记录的临时存储空间，比快速排序用栈更节约存储空间