本文共 9244 字，大约阅读时间需要 30 分钟。

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

时间复杂度

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

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

• 时间复杂度为一个算法流程中，常数操作数量的一个指标。从算法流程中总结出常数操作数量的表达式，在表达式中，只要高阶项，如果这部分为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
   
    {
       @Override    public int compare(Integer o1,Integer o2){
           return o1 - o2;    }}
   

桶排序思想下的排序

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

计数排序

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);	}

总结

• 快速排序 ：不求稳定性，只追求速度
• 堆排序 ：追求额外空间复杂度低，不追求稳定
• 归并排序 ：追求稳定性

转载地址：http://omugn.baihongyu.com/