排序

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

时间复杂度为一个算法流程中，常数操作数量的指标。常用O（big O）来表示。具体来说，在常数操作数量的表达式中只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分记为f(n)，那么时间复杂度为O( f(n) )。

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

各种排序算法：

  1. 冒泡排序：两两比较，将最大或者最小的值放在数组的最后，并在下一次比较中不再比较，直到排好序。 
public static void bubbleSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int e = arr.length - 1; e > 0; e--) {
			for (int i = 0; i < e; i++) {
				if (arr[i] > arr[i + 1]) {
					swap(arr, i, i + 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];
	}
  1. 插入排序：类似整理扑克牌，默认第一个位置已经排好序，后一个对前一个比较，若是小于则交换位置，再和前一个比较，直到不能交换位置，进行下一次排序。 
public static void insertionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 1; i < arr.length; i++) {
			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
				swap(arr, j, j + 1);
			}
		}
	}
  1. 选择排序：定义一个存放最小值的变量，遍历数组，取出最小的值的下标，与第一位交换，同时不再参与遍历，依次取出最小值排序。 
public static void selectionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 0; i < arr.length - 1; i++) {
			int minIndex = i;
			for (int j = i + 1; j < arr.length; j++) {
				minIndex = arr[j] < arr[minIndex] ? j : minIndex;
			}
			swap(arr, i, minIndex);
		}
	}