插入排序
一步一步思考，拆分，由浅入深：
- 先找出最小值，小循环没啥大问题再进入下一步，再去思考边界问题。
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; } }
大O分析：
最后算得：
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(); } } }
