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;
}
}
}
}
选择排序算法常规代码性能分析
-
时间复杂度分析
通过本算法代码可以看出，两层循环的执行次数和初始序列没有关系，外层循环执行 n 次，内层循环执行 n - 1 次，将最内层循环中的比较操作视为关键操作，其执行次数为 (n - 1 + 1)(n - 1) / 2 = n(n - 1) /2，即时间复杂度为 O(n²)。
-
空间复杂度分析
算法所需的辅助存储空间不随待排序列规模的变化而变化，是个常量，因此空间复杂度为 O(1)。
