Java 算法之选择排序

算法介绍

选择类排序的主要动作是“选择”，简单选择排序采用最简单的选择方式，从头至尾顺序扫描序列，找出最小的一个关键字，和第一个关键字交换，接着从剩下的关键字中继续这种选择和交换，最终使序列有序。

选择排序算法常规代码

public static void selectSort(int R[], int n){
    int i, j, k;
    int temp;
    // 这个循环是算法的关键，它从无序序列中挑出一个最小的关键字
    for(i = 0; i < n; ++i){
        k = i;
        for(j = i + 1; j < n; ++j)
            if(R[k] > R[j])
                k = j;
        // 下面三句完成最小关键字与无序序列第一个关键字的交换
        temp = R[i];
        R[i] = R[k];
        R[k] = temp;
    }
}

选择排序算法速记代码

public static void selectSort(int[] arr){
    for(int x = 0; x < arr.length - 1; x++){
        for(int y = x + 1; y < arr.length; y++){
            if(arr[x] > arr[y]){
                int temp = arr[x];
                arr[x] = arr[y];
                arr[y] = temp;
            }
        }
    }
}

选择排序算法常规代码性能分析

1. 时间复杂度分析

   通过本算法代码可以看出，两层循环的执行次数和初始序列没有关系，外层循环执行 n 次，内层循环执行 n - 1 次，将最内层循环中的比较操作视为关键操作，其执行次数为 (n - 1 + 1)(n - 1) / 2 = n(n - 1) /2，即时间复杂度为 O(n²)。

2. 空间复杂度分析

   算法所需的辅助存储空间不随待排序列规模的变化而变化，是个常量，因此空间复杂度为 O(1)。