排序算法概述

排序算法的用途是对数据集合按照一定规则进行排序，排序算法可以分为两类：
比较类排序：通过比较元素之间的大小，决定相对次序，时间复杂度与数据规模强相关。
非比较类排序：不通过比较元素大小决定次序，时间复杂度和数据规模不强相关，算法复杂度与数据特征有关系。

常用的排序算法如下：

算法	时间复杂度	最好时间复杂度	最差时间复杂度	空间复杂度	稳定性
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O (1)$	稳定
快速排序	$O (n l o n g n)$	$O (n l o n g n)$	$O(n^2)$	$O (n l o n g n)$	不稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O (1)$	不稳定
插入排序	$O(n^2)$	$O(n^2)$	$O (n)$	$O (1)$	稳定
归并排序	$O (n l o n g n)$	$O (n l o n g n)$	$O (n l o n g n)$	$O (n l o n g n)$	稳定
堆排序	$O (n l o n g n)$	$O (n l o n g n)$	$O (n l o n g n)$	$O (1)$	不稳定
桶排序	$O (n + k)$	$O(n^2)$	$O (n)$	$O (n + k)$	稳定
基数排序	$O (n ? k)$	$O (n ? k)$	$O (n ? k)$	$O (n + k)$	稳定
计数排序	$O (n + k)$	$O (n + k)$	$O (n + k)$	$O (n + k)$	稳定
希尔排序	$O (n)$	$O(n^2)$	$O (n)$	$O (1)$	不稳定

常用的排序算法

冒泡排序

从前往后撸一遍，每次把最大的数放在最后，这样最后一个数的位置就确定了。下一次继续从前往后撸到倒数第二个数，确定倒数第二个数。依次进行下去，直到所有的数据都被移动正确的位置。

	private static void bubbleSort(int[] arr) {
		for (int i = arr.length - 1; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				if(arr[j]>arr[j+1]) {
					swap(arr, j, j+1);
				}
			}
		}
	}
	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

举例：5、1、9、8、7
第一次循环结果：1、5、8、7、9
第二次循环结果：1、5、7、8、9
第三次循环结果：1、5、7、8、9
第四次循环结果：1、5、7、8、9
第五次循环结果：1、5、7、8、9

快速排序

快速排实际上是利用递归的思想，将数组分成大小两个部分，在大、小两个区间保证有序，进而保证整体有序。

	// 保证数组arr l-->r区间有序
	public static void quickSort(int[] arr, int l, int r) {
		if (l < r) {
		    // 利用随机数进行优化（下把为r的数为最小值），
			swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
			int[] p = partition(arr, l, r);
			quickSort(arr, l, p[0] - 1);
			quickSort(arr, p[1] + 1, r);
		}
	}
    // 将arr数组l-->r区间分为大小两个部分（以下标r作为基准），返回两个元素的数组优化元素相等时的排序
	public static int[] partition(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) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

举例：5、1、9、8、7（暂时不考虑随机数）
第一次排序：1、5、8、7、9（用5将数据分为两个区域{1}、{8，7，9}）
第二次排序：1、5、7、8、9（小于5的区域{1}不需要排序，大于5的区域{8，7，9}用第一个数8作为基准继续排序）

选择排序

选择排序，从头到尾依次遍历，找到最小的值，放在前面，每次确定一个数字的位置。

	private static void selectSort(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			// 记录i-->length-1最小值的下标
			int index = i;
			for(int j = i + 1; j < arr.length; j++) {
				if (arr[index] > arr[j]) {
					index = j;
				}
			}
			// 最小值与i交换
			swap(arr, index, i);
		}
	}
	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

举例：5、1、9、8、7
第一次排序：1、5、9、8、7
第二次排序：1、5、9、8、7
第三次排序：1、5、7、8、9
第四次排序：1、5、7、8、9
第五次排序：1、5、7、8、9

插入排序

已下标 $i$ 的数为基准，假设 $0 ? > i ? 1$ 有序，将下标 $i$ 的数插入到合适的位置保存 $0 ? > i$ 有序。遍历一轮保证全部有序。

	private static void insertSort(int[] arr) {
		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);
			}
		}
	}
	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

举例：5、1、9、8、7
第一次排序：1、5、9、8、7
第二次排序：1、5、9、8、7
第三次排序：1、5、8、9、7
第四次排序：1、5、7、8、9

归并排序

归并排序采用分治的思想，将数组分为两个区间，对区间内进行排序，然后使用一个辅助数组对两个区间进行合并。

	public static void mergeSort(int[] arr, int l, int r) {
		if (l == r) {
			return;
		}
		int mid = l + ((r - l) >> 1);
		mergeSort(arr, l, mid);
		mergeSort(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 i = 0;
		int p1 = l;
		int p2 = m + 1;
		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 (i = 0; i < help.length; i++) {
			arr[l + i] = help[i];
		}
	}