插入排序
一步一步思考，拆分，由浅入深：代码：大O分析：改良版： 验证算法——对数器
插入排序 一步一步思考，拆分，由浅入深：先找出最小值，小循环没啥大问题再进入下一步，再去思考边界问题。
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]
// 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;
}
}
大O分析：
最后算得：
n^2/2 - n/2 + T(常数)
以为就算时间复杂度是在大规模计算的前提下，所以计算时间复杂度记得：
忽略常数项忽略低次项
所以为 O(n^2)
稳定性：不稳定
两个相同的数，排序先后次序可能发生变化。
改良版：
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]
// 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();
}
}
}
