先找出最小值,小循环没啥大问题再进入下一步,再去思考边界问题。
int minPos = 0;
// 一步一步思考,先获取最小值
for (int i = 0; i < arr.length; i++) {
minPos = arr[i] < arr[minPos] ? i : minPos;
}
进行大循环
int[] arr = {2, 8, 4, 5, 7, 6, 3, 1, 9};
for (int j = 0; j < arr.length - 1; j++) {
int minPos = j;
// 小循环——找出最小值的下标,并让minpos指向它
for (int i = j + 1; i < arr.length; i++) {
minPos = arr[i] < arr[minPos] ? i : minPos;
}
System.out.println("minPos:" + minPos);
// 最小值放到本次循环的第一位
swap(arr, j, minPos);
}
// 选择排序-最简单但最没用
// 平均时间复杂度: n^2
// 空间复杂度: 1
// 稳定性: 不稳定
public class SelectionSort {
public static void main(String[] args) {
int[] arr = {2, 8, 4, 5, 7, 6, 3, 1, 9};
for (int j = 0; j < arr.length - 1; j++) {
int minPos = j;
// 一步一步思考,先获取最小值
for (int i = j + 1; i < arr.length; i++) {
// if(arr[i]<arr[minPos]) {
// minPos=i;
// }
// 简化
minPos = arr[i] < arr[minPos] ? i : minPos;
}
System.out.println("这是第" + j + "次循环后的数组:");
PrintArr(arr);
System.out.println("minPos:" + minPos);
// 最小值放到第一位
swap(arr, j, minPos);
}
}
// 打印一维数组
public static void PrintArr(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
// 数组元素交换位置
public static void swap(int[] arr, int i, int minPos) {
int temp = arr[i];
arr[i] = arr[minPos];
arr[minPos] = temp;
}
}
最后算得:
n^2/2 - n/2 + T(常数)
以为就算时间复杂度是在大规模计算的前提下,所以计算时间复杂度记得:
所以为 O(n^2)
稳定性:不稳定
两个相同的数,排序先后次序可能发生变化。
/**
[选择排序 改良版]:
使用了两个指针,一个min 一个max在原本的基础上减少了一半循环
[测试用例]:
int[] arr = {2, 8, 4, 5, 7, 6, 3, 9, 1};
测试过程:
for:0 8
end:0 1
for:0 1
end:0 1
for:0 1
end:0 1
for:0 1
end:0 1
for:0 1
end:0 1
for:0 1
end:0 1
for:0 1
end:0 7
[第0次]:1 8 4 5 7 6 3 2 9
for:1 7
end:1 7
for:1 7
end:1 7
for:1 7
end:1 7
for:1 7
end:1 7
for:1 7
end:1 7
[第1次]:1 2 4 5 7 6 3 8 9
for:2 6
end:2 3
for:2 3
end:2 4
for:2 4
end:2 4
[第2次]:1 2 3 5 4 6 7 8 9
for:3 5
end:4 5
[第3次]:1 2 3 4 5 6 7 8 9
*/
public class SelectionSort {
public static void main(String[] args) {
int[] arr = {2, 8, 4, 5, 7, 6, 3, 9, 1};
for (int i = 0; i < arr.length / 2; i++) {
int minpos = i;
int maxpos = arr.length - i - 1;
if (arr[minpos] > arr[maxpos]) {
swap(arr, minpos, maxpos);
}
for (int j = i + 1; j < arr.length - i - 1; j++) {
System.out.println("for:" + minpos + " " + maxpos);
// 因为min和max在循环中是取不到的,所有要 先 比较二者大小
// 比如第二圈循环
// minpos=1 maxpos=7
// arr[minpos]=8 arr[maxpos]=2
// 如果没有这个判断,就会在下面两个if中让minpos和minpos=2 对应的值为4,
// 而在接下来的循环中因为不在出现8和2
// 导致排序出现问题。
// if (arr[j]<arr[minpos]) {
// minpos=j;
// }
// 简化:
minpos = arr[j] < arr[minpos] ? j : minpos;
// if(arr[j]>arr[maxpos]) {
// maxpos = j;
// }
// 简化:
maxpos = arr[j] > arr[maxpos] ? j : maxpos;
System.out.println("end:" + minpos + " " + maxpos);
}
swap(arr, i, minpos);
swap(arr, arr.length - i - 1, maxpos);
System.out.print("[第" + i + "次]:");
printArr(arr);
System.out.println();
}
}
static void printArr(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
static void swap(int[] arr, int i, int minPos) {
int temp = arr[i];
arr[i] = arr[minPos];
arr[minPos] = temp;
}
}
如何验算你的算法是否正确?
public class DateChecker {
// 初始化一个10000长度的数组
static int[] generateRandomArray() {
Random random = new Random();
int[]arr= new int[10000];
for (int i = 0; i < arr.length; i++) {
arr[i]=random.nextInt(10000);
}
return arr;
}
// 检查函数
static void check() {
int [] arr = generateRandomArray();
int [] arr2 = new int[arr.length];
System.arraycopy(arr, 0, arr2, 0, arr.length);
Arrays.sort(arr);
SelectSort(arr2);
boolean same = true;
for (int i = 0; i < arr2.length; i++) {
if (arr[i]!=arr2[i]) {
System.out.println(arr[i]+" "+arr2[i]);
same=false;
}
}
System.out.println(same==true?"right":"wrong");
}
// 选择排序
static void SelectSort(int[] arr) {
for (int i = 0; i < arr.length / 2; i++) {
int minpos = i;
int maxpos = arr.length - i - 1;
if (arr[minpos] > arr[maxpos]) {
swap(arr, minpos, maxpos);
}
for (int j = i + 1; j < arr.length - i - 1; j++) {
minpos = arr[j] < arr[minpos] ? j : minpos;
maxpos = arr[j] > arr[maxpos] ? j : maxpos;
}
swap(arr, i, minpos);
swap(arr, arr.length - i - 1, maxpos);
}
}
// 打印数组
static void printArr(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
// 互换值
static void swap(int[] arr, int i, int minPos) {
int temp = arr[i];
arr[i] = arr[minPos];
arr[minPos] = temp;
}
// 主函数
public static void main(String[] args) {
for (int i = 0; i < 1000; i++) {
check();
}
}
}