数据结构（九）：简单选择排序

• 通过 n-i 次元素之间的比较，从 n-i+1 个元素中选出值最小的元素，和第 i 个元素交换 （从数组中选出最小值元素与最左元素进行交换位置）

简单选择排序例子

• 举例：

  • 假设数组如下

  5	2	8	4	9	1

  • 第一趟排序：比较 { 5 2 8 4 9 1 }，1 最小，1 和 5 互换位置

  1	2	8	4	9	5

  • 第二趟排序：比较 { 2 8 4 9 5 }，2 最小，已在最后一位，位置不变

  • 第三趟排序：比较 { 8 4 9 5 }，4 最小，4 和 8 互换位置

  1	2	4	8	9	5

  • 第四趟排序：.....

  1	2	4	5	9	8

  • 第五趟排序：.....

  1	2	4	5	8	9

简单选择排序代码

int[] arr = new int[]{1, 3, 6, 4, 7, 8, 5, 10, 9};
// 简单选择排序
for(int i = 0; i < arr.length - 1; i++) {
    int k = i;
    for(int j = k + 1; j < arr.length; j++){
        if(arr[j] < arr[k]){
            k = j;      //记下目前找到的最小值所在的位置
        }
    }
    // 移动最小的元素至最左边
    if(i != k){
        int temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }
}

简单选择排序时间的性能

• 简单选择排序的比较次数与序列的初始排序无关
• 假设待排序的序列有 N 个元素，则比较次数永远都是 N (N - 1) / 2
• 而移动次数与序列的初始排序有关，当序列正序时，移动次数最少，为 0。当序列反序时，移动次数最多，为3N (N - 1) / 2
• 简单排序综合的时间复杂度为 O(n²)，综合来说优于冒泡排序