算法基础

选择排序(ASC):

第一轮: 第一个数与后面每个数比较, 较小值交换至第一个位置;(第一个数字为最小值)第二轮: 第二个数与后面每个数比较, 较小值交换至第二个位置;(第二个数字为次小值) …后续同理(每次循环在[m, n]区间内获取最小值, 放置m处) public static void selectionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 0 ~ N-1 // 1 ~ N-1 // ... // N-2 ~ N-1 for (int i = 0; i < arr.length -1; i++){ // i ~ N-2 for (int j = i + 1; j <= arr.length -1; j++) { // i+1 ~ N-1 if (arr[j] < arr[i]){ swap(arr, i, j); } } } } public static void swap(int[] arr, int i, int j) { //额外空间 tmp int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void selectionSort2(int[] arr) { if (arr == null || arr.length < 2) { return; } // 0 ~ N-1 // 1 ~ N-1 // ... for (int i = 0; i < arr.length - 1; i++) { // 下标 i ~ N-2 // 记录最小值在哪个位置上(减少交换次数) i～n-1 // 常数项时间优于第一种, 细节处理的更好 int minIndex = i; for (int j = i + 1; j < arr.length; j++) { // 下标 i ~ N-1 上找最小值的下标 minIndex = arr[j] < arr[minIndex] ? j : minIndex; } swap2(arr, i, minIndex); } } public static void swap2(int[] arr, int i, int j) { //下标一样, 不需要交换, 否则亦或自己则值变成了0 if (i == j) return; //无额外空间 arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; }

冒泡排序(ASC):

第一轮: 第一个数与第二个数比较, 较小值交换至第一个位置; 第二个数与第三个数比较, 较小值交换至第二个位置…第n-1与第n个数比较, 较小值交换至第n-1位置;(第n个数字为最大值)第二轮: 第一个数与第二个数比较, 较小值交换至第一个位置; 第二个数与第三个数比较, 较小值交换至第二个位置…第n-2与第n-1个数比较, 较小值交换至第n-2位置;(第n-1个数字为次最大值) …后续同理(每次循环在[1, n-m]区间内获取最大值, 放置n-m处) public static void bubbleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 0 ~ N-1 // 0 ~ N-2 // 0 ~ N-3 //... // 0 ~ 1 for (int i = arr.length - 1; i > 0; i--) { // 下标 0 ~ N - 2 - i for (int j = 0; j < i; j++) { // 下标 0 ~ i - 1 if (arr[j] > arr[j + 1]){ swap(arr, j, j + 1); } } } } public static void swap(int[] arr, int i, int j) { //下标一样, 不需要交换, 否则亦或自己则值变成了0 if (i == j) return; //无额外空间 arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; }

插入排序(ASC):

第一轮: 第一个数,与前一个数(null)相比有序不处理( 类似斗地主,每抽一张牌按顺序方式插入原先牌库 )第二轮: 第二个数与第一个数比较, 第二个数较小则交换至第一个位置,否则结束此轮,第三轮: 第三个数与第二个数比较, 第三个数较小则交换至第二个位置,否则结束此轮; 若没结束,则第二个数与第一个数比较, 第二个数较小则交换至第一个位置,否则结束此轮; …后续同理(每次循环加入一个数n-m, 与有序区间[1, n-m-1]进行排序合并后, 当前数据[1, n-m]中的最大值, 放置n-m处) public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { // 下标 1 ~ N-1 for (int j = i; j > 0; j--) { // 下标为i的数去和 0 ~ i-1 if (arr[j] < arr[j - 1]){ swap(arr, j, j - 1); } else { break; } } } } public static void swap(int[] arr, int i, int j) { //下标一样, 不需要交换, 否则亦或自己则值变成了0 if (i == j) return; //无额外空间 arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; }