选择排序
选择排序(Select Sort) 是直观的排序,通过确定一个 Key 最大或最小值,再从带排序的的数中找出最大或最小的交换到对应位置。再选择次之。双重循环时间复杂度为 O(n^2)
算法描述:
在一个长度为 N 的无序数组中,第一次遍历 n-1 个数找到最小的和第一个数交换。
第二次从下一个数开始遍历 n-2 个数,找到最小的数和第二个数交换。
重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换,排序完成。
动图效果示意图:
java代码实现
public static int[] selectSort(int[] arr) {
for (int i=0;i<arr.length-1;i++){
int minidx=i;
for (int j=i+1;j<arr.length;j++){
if (arr[minidx]>arr[j]){
minidx=j;
}
}
if (minidx!=i){
int temp=arr[i];
arr[i]=arr[minidx];
arr[minidx]=temp;
}
}
return arr;
}