实现思想是每步从排序记录中选出排序码最小(最大)的记录,放在已排序记录序列的最后(前);
直接选择排序算法n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
public static void selectionSort(int[] arr) { int min, temp; for (int i = 0; i < arr.length ; i++) { // 初始化最小下标为最小数据数组下标 min = i; for (int j = i + 1; j < arr.length; j++) { // 在未排序元素中继续寻找最小元素,并保存其下标 if (arr[j] < arr[min]) {//如果有小于当前最小值的值 min = j;//将此数值的下标赋值给min } } if (min != i) {// 如果min不等于i,说明找到最小值,进行交换 //数据交换 temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } } }
让我们来一行一行地分析一下代码:
for (int i = 0; i < arr.length ; i++) {
在上面代码是外层循环,在刚开始的时候,先记录下来当前最小值的索引,也就是i的值。
min = i;
每一轮开始的时候,min的值就是起点的索引,也就是未排序数据的起始索引,第一轮为0,第二轮是1,第三轮是2,依次类推,一直到最后一轮。
for (int j = i + 1; j < arr.length; j++) {
开始内层的循环
if (arr[j] < arr[min]) { min = j; }
依次检查未排序的数据,如果遇到的值比索引为min的值小,则将min更新为这个数据的索引。当内层循环完毕时,min就是是当前轮的最小值的索引。
if (min != i) { temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; }
判断min与初始值i比较,如果不一样,说明最小值不是第一个,则将索引为i的值与索引为min的值进行交换。
容易看出,待排序序列为正序,移动次数最小,为 0 次;待排序序列为逆序时,移动次数最多,为 3(n-1) 次。
但无论记录的初始排列如何,关键码的比较次数相同,第 i 趟排序需进行 n-i 次关键码的比较,而简单选择排序需要进行 n-1 趟排序,因此,总的比较次数为 O(n^2)
故而,无论是最优、最差时间复杂度,还是平均时间复杂度,均为 O(n^2)
对于空间复杂度来说,简单选择排序仅需一个存储空间用于记录交换的暂存单元,即空间复杂度为 O(1)
原文链接:https://www.cnblogs.com/codepeng/p/13532933.html