选择排序

选择排序

一.算法原理

每一次从代排序的数据元素中选出最小(或最大)的一个元素,存放在序列起始位置,直到全部代排数据元素排完.

比如序列[6 4 5 2 1]先选出最小元素1排到起始位,依次从代排序列选出2,4,5,6.

二java简单实现

public static void selectSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int temp,k;
        for (int i=0; i<arr.length-1; i++) {
            k = i;
            for (int j=i+1; j<arr.length; j++) {
                if (arr[j] > arr[k]) {
                    k = j;
                }
            }
            if (i != k) {
                temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }
        }
    }

三.时间复杂度

与序列初始排序无关,分析代码可知比较操作为n(n-1)/2(内部for循环部分),而赋值操作与初始排序有关,正序时为0,反序时为3 n(n-1)/2 (3比较操作);
所以,选择排序最差平均都是O(n^2)

四.稳定性

选择排序是一个不稳定的排序算法.
如序列[5,5,3]第一次排序就将3与第一个5进行交换.