在学习排序算法的过程中做的笔记以及总结，都是手写，有错误的话请大家包容一下并指出来，一起进步。

时间复杂度

是粗描算法流程和数据量之间的一个关系。

常数时间的操作(和数据量无关的操作)，一个操作如果和样本的数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。

时间复杂度为一个算法流程中，常数操作数量的一个指标。从算法流程中总结出常数操作数量的表达式，在表达式中，只要高阶项，如果这部分为f(N)，那么时间复杂度为O(f(N))。

评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是"常数项时间"。

对数器

用来测试自己写的排序算法是否正确。

public static void comparator(int[] arr) { Arrays.sort(arr); } public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()); } return arr; } public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } return true; } public static void printArrays(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } public static void main(String[] args) { int testTime = 50000; int maxSize = 100; int maxValue = 100000; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); radixSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; printArrays(arr1); printArrays(arr2); break; } } System.out.println(succeed ? "通过" : "未通过测试用例"); int[] arr = generateRandomArray(maxSize, maxValue); printArrays(arr); radixSort(arr); printArrays(arr); } }

选择排序，冒泡排序，插入排序

public class xuanze { //选择排序 public static void sort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length - 1; i++) { int index = i; for (int j = i + 1; j < arr.length; j++) { index = arr[j] < arr[index] ? j : index; } swap(arr, i, index); } } //冒泡排序 public void ssort2(int[] arr1) { if (arr1 == null || arr1.length < 2) { return; } for (int i = arr1.length - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (arr1[j] > arr1[j + 1]) { swap(arr1, j, j + 1); } } } } //插入排序 public void sort3(int[] arr2) { if (arr2 == null || arr2.length < 2) { return; } for (int i = 1; i < arr2.length; i++) { for (int j = i - 1; j > 0 && arr2[j] > arr2[j + 1]; j--) { swap(arr2, j, j + 1); } } } //异或运算实现数字交换 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]; } } //时间复杂度都为O(n²)

二分法

在一个有序数组中，找某个数是否存在；

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; while (L < R) { mid = L + ((R - L) >> 1); if (sortedArr[mid] == num) { return true; } else if (sortedArr[mid] > num) { R = mid - 1; } else { L = mid + 1; } } return sortedArr[L] == num; }

在一个有序数组中，找>=某个数最左侧的位置；

// 在arr上，找满足>=value的最左位置 public static int nearestIndex(int[] arr, int value) { int L = 0; int R = arr.length - 1; int index = -1; while (L < R) { int mid = L + ((R - L) >> 1); if (arr[mid] >= value) { index = mid; R = mid - 1; } else { L = mid + 1; } } return index; }

局部最小值问题；

public static int Awesome(int[] arr) { if (arr == null || arr.length == 0) { return -1; } if (arr[0] < arr[1] || arr.length == 1) { return arr[0]; } if (arr[arr.length - 1] < arr[arr.length - 2]) { return arr[arr.length - 1]; } int L = 1; int R = arr.length - 2; while (L < R) { int mid = L + ((R - L) >> 1); if (arr[mid] > arr[mid + 1]) { L = mid + 1; } else if (arr[mid] > arr[mid - 1]) { R = mid - 1; } else { return arr[mid]; } } return arr[R]; }

递归

某一种递归的时间复杂度计算方式

master公式

$$T(N)=a\ast T(N/b)+O(N^d)$$

$$1.log{b}^a<d=>O(N^d)$$

$$2.log{b}^a>d=>O(N^{log{b}^a})$$

$$3.log{b}^a=d=>O(N^d\ast logN)$$

时间复杂度O(N * log N)的排序

归并排序

public static void mergesort(int[] arr) { if (arr == null || arr.length < 2) { return; } process(arr, 0, arr.length - 1); } public static void process(int[] arr, int L, int R) { if (L == R) { return; } int mid = L + ((R - L) >> 1); process(arr, L, mid); process(arr, mid + 1, R); merge(arr, L, mid, R); } public static void merge(int[] arr, int L, int M, int R) { int[] help = new int[R - L + 1]; int p1 = L; int p2 = M + 1; int i = 0; while (p1 <= M && p2 <= R) { help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; } while (p1 <= M) { help[i++] = arr[p1++]; } while (p2 <= R) { help[i++] = arr[p2++]; } for (int j = 0; j < help.length; j++) { arr[L + j] = help[j]; } }

堆排序

public static void sort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length; i++) { heapinsert(arr, i); } // for (int i = arr.length - 1; i >= 0; i--) { // heapify(arr, i, arr.length); // } int heapSize = arr.length; swap(arr, 0, --heapSize); while (heapSize > 0) { heapify(arr, 0, heapSize); swap(arr, 0, --heapSize); } } public static void heapinsert(int[] arr, int index) { while (arr[(index - 1) / 2] < arr[index]) { swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; } } public static void heapify(int[] arr, int index, int heapSize) { int left = index * 2 + 1; while (left < heapSize) { int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left; largest = arr[index] > arr[largest] ? index : largest; if (largest == index) { break; } swap(arr, largest, index); index = largest; left = index * 2 + 1; } } public static void swap(int[] arr, int i, int j) { if(i==j) return; arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; }

快速排序

public static void process(int[] arr, int L, int R) { if (L == R) return; if (L < R) { swap(arr, L + (int) (Math.random() * (R - L + 1)), R); int[] p = patition(arr, L, R); process(arr, L, p[0] - 1); process(arr, p[1] + 1, R); } } public static int[] patition(int[] arr, int L, int R) { int less = L - 1; int more = R; while (L < more) { if (arr[L] < arr[R]) { swap(arr, ++less, L++); } else if (arr[L] > arr[R]) { swap(arr, --more, L); } else { L++; } } swap(arr, more, R); return new int[] { less + 1, more }; } public static void swap(int[] arr, int i, int j) { if (i == j) { return;cou } arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; }

比较器

//对于任意比较器，首先只需要定两个对象：o1和o2 //返回值有统一的规范 //返回值负数时，认为o1应该排在o2前面； //返回值正数时，认为o2应该排在o1前面； //返回0的时候，不变 public static void AComp implements Comparator<Integer>{ @Override public int compare(Integer o1,Integer o2){ return o1 - o2; } }

桶排序思想下的排序

桶排序思想下的排序都是不基于比较的排序。应用范围有限，需要样本的数据状况满足桶的划分。

计数排序

public static void countsort(int[] arr) { if (arr == null || arr.length < 2) { return; } int max = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { max = Math.max(arr[i], max); } int[] compare = new int[max + 1]; for (int i = 0; i < arr.length; i++) { compare[arr[i]]++; } int c = 0; for (int i = 0; i < compare.length; i++) { while (compare[i]-- > 0) { arr[c++] = i; } } }

桶排序

public static void radixSort(int[] arr) { if (arr == null || arr.length < 2) { return; } radixsort(arr, 0, arr.length - 1, maxbits(arr)); } public static int maxbits(int[] arr) { int max = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { max = Math.max(max, arr[i]); } int res = 0; while (max != 0) { res++; max /= 10; } return res; } public static void radixsort(int[] arr, int L, int R, int digit) { final int radix = 10; int i = 0; int j = 0; int[] bucket = new int[R - L + 1]; for (int d = 1; d <= digit; d++) { int[] count = new int[radix]; for (i = L; i <= R; i++) { j = getDigit(arr[i], d); count[j]++; } for (i = 1; i < radix; i++) { count[i] = count[i - 1] + count[i]; } for (i = R; i >= L; i--) { j = getDigit(arr[i], d); bucket[count[j] - 1] = arr[i]; count[j]--; } for (i = L, j = 0; i <= R; i++, j++) { arr[i] = bucket[j]; } } } public static int getDigit(int x, int d) { return (x / ((int) Math.pow(10, d - 1)) % 10); }

总结

时间复杂度额外空间复杂度稳定选择排序O(N²)O(1)×冒泡排序O(N²)O(1)√插入排序O(N²)O(1)√归并排序O(N * log N)O(N)√堆排序O(N * log N)O(1)×快速排序O(N * log N)O(log N)×桶排序O(N)O(N)√ 快速排序 ：不求稳定性，只追求速度堆排序 ：追求额外空间复杂度低，不追求稳定归并排序 ：追求稳定性