选择排序

选择排序算法思想

选择排序的算法思想是假设有一个长度为N的数组，在[0...N-1]的范围上，从i=0开始，遍历整个数组，记录最小值下标。一趟结束后和起始位置交换，然后从i=1开始直到i=N-1结束

选择排序算法实现

public static void main(String[] args) {
        int[] arr = {-2, 1, 33, 4, 5, 0, 0, -1, 45, 908, 3};
        int[] sortList = selectSort(arr);
       for (int i : sortList) {
            System.out.print(i + "  ");
        }
        int[] sortListSample = selectSortSample(arr);
        for (int i : sortListSample) {
            System.out.print(i + "  ");
        }
    }
   /**
     * 简单实现
     *
     * @param arr
     * @return
     */
    private static int[] selectSortSample(int[] arr) {
        if (arr.length < 0) {
            return null;
        }
        int N = arr.length;
        int j, i;
        for (i = 0; i < N; i++) {
            for (j = i + 1; j < N; j++) {
                //在这个位置会有很多次的交换，但是这些应该都是不必要，
                // 我们只需要把最小的角标标识出来移动一次就OK了
                if (arr[j] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
    /**
     * 比较排序
     *
     * @param arr
     * @return
     */
    private static int[] selectSort(int[] arr) {
        if (arr.length < 0) {
            return null;
        }
        int N = arr.length;
        int j, i;
        for (i = 0; i < N; i++) {
            // 标记最小的角标
            int min = i;
            for (j = i + 1; j < N; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            // switch 把最小的元素和当前的元素交换
            /** 注意是arr[i]和arr[min]交换**/
            if (i != min) {
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
        return arr;
    }

算法复杂度

1.平均时间复杂度：O(N^2)
2.最坏时间复杂度：O(N^2) 出现情况：任何情况下
3.最好时间复杂度：O(N^2) 出现情况：任何情况下
4.空间复杂度：O(1) 不需要额外空间

算法稳定性

1. 是不稳定的算法，因为在移动的时候不能保证相同元素的前后顺序

想看更多完整版请点击：(选择排序)[http://git.oschina.net/xiaoyuxi/algorithm/blob/master/src/main/java/com/al/study/record/sort/InsertSort.java]