抉择排序
过程：
arr[0～N-1]范畴上，找到最小值所在的地位，而后把最小值替换到0地位。
arr[1～N-1]范畴上，找到最小值所在的地位，而后把最小值替换到1地位。
arr[2～N-1]范畴上，找到最小值所在的地位，而后把最小值替换到2地位。
…
arr[N-1～N-1]范畴上，找到最小值地位，而后把最小值替换到N-1地位。
估算：
很显著，如果arr长度为N，每一步常数操作的数量，如等差数列个别
所以，总的常数操作数量 = a(N^2) + bN + c (a、b、c都是常数)
所以抉择排序的工夫复杂度为O(N^2)。
public static void selectionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 0 ~ N-1 // 1~n-1 // 2 for (int i = 0; i < arr.length - 1; i++) { // i ~ N-1 // 最小值在哪个地位上 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; } swap(arr, i, minIndex); }}public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;}冒泡排序
过程：
在arr[0～N-1]范畴上：
arr[0]和arr[1]，谁大谁来到1地位；arr[1]和arr[2]，谁大谁来到2地位…arr[N-2]和arr[N-1]，谁大谁来到N-1地位
在arr[0～N-2]范畴上，反复下面的过程，但最初一步是arr[N-3]和arr[N-2]，谁大谁来到N-2地位
在arr[0～N-3]范畴上，反复下面的过程，但最初一步是arr[N-4]和arr[N-3]，谁大谁来到N-3地位
…
最初在arr[0～1]范畴上，反复下面的过程，但最初一步是arr[0]和arr[1]，谁大谁来到1地位
估算：
很显著，如果arr长度为N，每一步常数操作的数量，仍然如等差数列个别
所以，总的常数操作数量 = a(N^2) + bN + c (a、b、c都是常数)
所以冒泡排序的工夫复杂度为O(N^2)。
public static void bubbleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 0 ~ N-1 // 0 ~ N-2 // 0 ~ N-3 for (int e = arr.length - 1; e > 0; e--) { // 0 ~ e for (int i = 0; i < e; i++) { if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); } } }}// 替换arr的i和j地位上的值public static void swap(int[] arr, int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j];}插入排序
过程
很显著，在最差状况下，如果arr长度为N，插入排序的每一步常数操作的数量，还是如等差数列个别
估算
所以，总的常数操作数量 = a(N^2) + bN + c (a、b、c都是常数)
所以插入排序排序的工夫复杂度为O(N^2)。
public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 0~0 有序的 // 0~i 想有序 for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序 for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j + 1); } }}// i和j是一个地位的话，会出错public static void swap(int[] arr, int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j];}二分法
- 在一个有序数组中，找某个数是否存在
- 在一个有序数组中，找>=某个数最左侧的地位
- 在一个有序数组中，找<=某个数最右侧的地位
- 部分最值问题 (不肯定有序)
- 次要找到一个排他性的规范
public static boolean exist(int[] sortedArr, int num) { if (sortedArr == null || sortedArr.length == 0) { return false; } int L = 0; int R = sortedArr.length - 1; int mid = 0; // L..R while (L < R) { // mid = (L+R) / 2; // L 10亿 R 18亿 // mid = L + (R - L) / 2 // N / 2 N >> 1 mid = L + ((R - L) >> 1); // mid = (L + R) / 2 if (sortedArr[mid] == num) { return true; } else if (sortedArr[mid] > num) { R = mid - 1; } else { L = mid + 1; } } return sortedArr[L] == num;}