排序算法 - 算法 | Lin's Blog = 凛

[[toc]]

# -1、时间复杂度

时间复杂度排行

# 0、算法概述

# 0.1 算法分类

十种常见排序算法可以分为两大类：

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O (nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

排序算法

# 0.2 算法复杂度

算法复杂度

# 0.3 相关概念

稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面。
不稳定：如果 a 原本在 b 的前面，而 a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当 n 变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模 n 的函数。

# 0.4 算法速度大概比较

以十万条数据排序所花费的时间进行比较

冒泡排序：14s
选择排序：4s
插入排序：3s (二十万条)
希尔排序: 10s (四千万条)
快速排序：4s (四千万条)
归并排序：6s (四千万条)
基数排序：3s (四千万条)

# 1、冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

# 1.1 算法描述

比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤 1~3，直到排序完成。

# 1.2 动图演示

冒泡排序

# 1.3 代码实现

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

# 2、选择排序（Selection Sort）

选择排序 (Selection-sort) 是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

# 2.1 算法描述

n 个记录的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。具体算法描述如下：

初始状态：无序区为 R [1..n]，有序区为空；
第 i 趟排序 (i=1,2,3…n-1) 开始时，当前有序区和无序区分别为 R [1..i-1] 和 R (i..n）。该趟排序从当前无序区中 - 选出关键字最小的记录 R [k]，将它与无序区的第 1 个记录 R 交换，使 R [1..i] 和 R [i+1..n) 分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区；
n-1 趟结束，数组有序化了。

# 2.2 动图演示

选择排序

# 2.3 代码实现

	/**
	* 1. 第一个 for 循环，len-1 是因为五个数，只需要四趟就成功排序
	* 2. 首先默认第一个元素为最小，进行比较
	* 3.int j = i + 1 是因为选择第一个数与后面的数进行比较，所以 + 1，i+1 是因为前面 i 个已经为最小了
	* 4.j < len 是为了和数组所有数进行比较
	* 5. 内层 for 循环结束后，找到最小数值下标，进行交换
	*/
	public static void selectionSort1(int[] arr) {
	int len = arr.length;
	for (int i = 0; i < len - 1; i++) {
	int minIndex = i;
	for (int j = i + 1; j < len; j++) {
	if (arr[minIndex] > arr[j]) {
	minIndex = j;
	}
	}
	int temp = arr[i];
	arr[i] = arr[minIndex];
	arr[minIndex] = temp;
	}
	}

# 3、插入排序（Insertion Sort）

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

# 3.1 算法描述

一般来说，插入排序都采用 in-place 在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤 2~5。

# 3.2 动图演示

插入排序

# 3.3 代码实现

	/**
	* 1. 从 1 开始循环，是因为插入排序的特点导致的，默认第一个元素为有序的，从第二个开始比较
	* 2. 由于是从 1 开始循环，因此为 i < arr.length，不需要多减 1
	* 3.current 为要插入的数据
	* 4.arr [preIndex + 1] = current; preIndex+1 是因为 while 循环结束后，preIndex 为要插入的下标的前一个
	*/
	public static void insertionSort(int[] arr) {
	for (int i = 1; i < arr.length; i++) {
	int preIndex = i - 1;
	int current = arr[i];
	while (preIndex >= 0 && arr[preIndex] > current) {
	arr[preIndex + 1] = arr[preIndex];
	preIndex--;
	}
	arr[preIndex + 1] = current;

	}
	}

# 4、希尔排序（Shell Sort）

希尔排序是插入排序的改进版，由 Shell 发明。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

# 4.1 算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

# 4.2 动图演示

希尔排序

# 4.3 代码实现

(三层 for 循环加一个 if 判断，交换法，速度太慢)

	/**
	* 1. 第一个 for 循环，希尔排序的步长
	* 2. 后面两个 for 循环相当于一个简单版的插入排序，左边元素有序，右边比较大小，找到合适的位置进行插入
	* 3. 第三个 for 循环，从数组的第一个元素开始，把按步长分开的数组进行排序
	* 4. 注意区分和冒泡的区别，冒泡交换的时候前面数字并不确定是否有序，而希尔交换的时候 arr [j] 前面的数组是确定有序的
	* @param arr
	*/
	public static void shellSort(int[] arr) {
	for (int step = arr.length / 2; step > 0; step /= 2) {
	for (int i = step; i < arr.length; i++) {
	for (int j = i - step; j >= 0; j -= step) {
	// 进行了简单插入排序，因为每次 arr [j] 之前的元素已经有序，然后比较大小，进行插入
	if (arr[j] > arr[j + step]) {
	// 判断大小，采用交换法进行简单插入排序
	int temp = arr[j];
	arr[j] = arr[j + step];
	arr[j + step] = temp;
	}
	}
	}
	}
	}

(真正的希尔排序，两个 for 一个 while，移位法，里面是真正的简单插入排序)

	public static void shellSort(int[] arr) {
	for (int gap = arr.length / 2; gap > 0; gap /= 2) {
	for (int i = gap; i < arr.length; i++) {
	int j = i;// 要插入的值的下标
	int current = arr[j];
	while (j - gap >= 0 && current < arr[j - gap]) {
	arr[j] = arr[j - gap];
	j -= gap;
	}
	arr[j] = current;
	}
	}
	}

# 4.4 分析

注意区分和冒泡的区别，冒泡交换的时候前面数字并不确定是否有序，而希尔交换的时候 arr [j] 前面的数组是确定有序的，但是由于采用交换法，时间花费较多，比普通的插入排序还要多
交换法时间速度很慢，甚至比简单插入排序还要慢很多
因此使用第二个代码实现，真正的希尔排序
速度是真的快，震惊了，八十万条数据一秒排序，碾压上面的几个排序！！(○´･д･)ﾉ

# 5、快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

# 5.1 算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

# 5.2 动图演示

快速排序

# 5.3 代码实现

	public class QuickSort {
	public static void quickSort(int[] arr, int L, int R) {
	if (L < R) {
	//swap (arr, L + (int) (Math.random () * (R - L + 1)), R); // 快排 3.0, 不加这句话时间复杂度为 O (n*n), 加了为 O (nlogn)
	int p = partition(arr, L, R);// 返回的是下标值
	quickSort(arr, L, p - 1); // 下标左边
	quickSort(arr, p + 1, R);// 下标右边
	}
	}

	private static int partition(int[] arr, int L, int R) { // 返回的数组表示划分区等于划分指的左右边界 [5,5]
	// 取最后一个元素作为中心元素 (去最后一个元素作为基准)
	int pivot = arr[R];
	int pointer = L; // 初始化第一个指针，指向第一个元素
	for (int i = L; i < R; i++) {
	if (arr[i] <= pivot) {
	// 将比中心元素小的元素和指针指向的元素交换位置
	// 如果第一个元素比中心元素小，这里就是自己和自己交换位置，指针和索引都向下一位移动
	// 如果元素比中心元素大，索引向下移动，指针指向这个较大的元素，直到找到比中心元素小的元素，并交换位置，指针向下移动
	swap(arr, i, pointer);
	pointer++;
	}
	}
	swap(arr, pointer, R);// 此方法操作的是下标
	return pointer;// 返回的是中心元素的下标
	}

	private static void swap(int[] arr, int i, int j) {
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
	}
	}

# 6、归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

# 6.1 算法描述

把长度为 n 的输入序列分成两个长度为 n/2 的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

# 6.2 动图演示

归并排序

# 6.3 代码实现

	private static void mergeSort(int[] arr, int left, int right, int[] temp) {
	if (left < right) {
	int mid = left + (right - left) / 2;
	mergeSort(arr, left, mid, temp);// 左边归并排序，使得左子序列有序
	mergeSort(arr, mid + 1, right, temp);// 右边归并排序，使得右子序列有序
	merge(arr, left, mid, right, temp);// 将两个有序子数组合并操作
	}
	}

	private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
	int i = left;// 左序列指针
	int j = mid + 1;// 右序列指针
	int t = 0;// 临时数组指针
	while (i <= mid && j <= right) {
	if (arr[i] <= arr[j]) {
	temp[t++] = arr[i++];
	} else {
	temp[t++] = arr[j++];
	}
	}
	while (i <= mid) {// 将左边剩余元素填充进 temp 中
	temp[t++] = arr[i++];
	}
	while (j <= right) {// 将右序列剩余元素填充进 temp 中
	temp[t++] = arr[j++];
	}
	t = 0;
	// 将 temp 中的元素全部拷贝到原数组中
	while (left <= right) {
	arr[left++] = temp[t++];
	}
	}

# 7、基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

# 7.1 算法描述

取得数组中的最大数，并取得位数；
arr 为原始数组，从最低位开始取每个位组成 radix 数组；
对 radix 进行计数排序（利用计数排序适用于小范围数的特点）；

# 7.2 动图演示

基数排序

# 7.3 代码实现

	public static void radixSort(int[] arr) {
	//1. 得到数组中最大值
	int max = arr[0];
	for (int i = 0; i < arr.length; i++) {
	if (arr[i] > max) {
	max = arr[i];
	}
	}
	//2. 得到最大值的位数
	int maxLength = (max + "").length();
	//3. 定义桶和表示桶中元素个数
	int[][] bucket = new int[10][arr.length];
	int[] bucketCounts = new int[bucket.length];
	// 一共需要进行 maxlength 轮
	for (int k = 1, n = 1; k <= maxLength; k++, n *= 10) {
	// 进行桶排序
	for (int i = 0; i < arr.length; i++) {
	int bucketIndex = arr[i] / n % 10;
	// 放入该桶中
	bucket[bucketIndex][bucketCounts[bucketIndex]] = arr[i];
	// 标识该桶元素多了一个
	bucketCounts[bucketIndex]++;
	}
	// 将桶中元素获取出来，放到原数组中
	int index = 0;
	for (int i = 0; i < bucket.length; i++) {
	if (bucketCounts[i] == 0) {
	// 该桶无有效元素，跳过不获取
	continue;
	}
	// 获取桶中有效的个数
	for (int j = 0; j < bucketCounts[i]; j++) {
	arr[index++] = bucket[i][j];
	}
	// 取完后，重置该桶的元素个数为 0 ，下一次才不会错乱数据
	bucketCounts[i] = 0;
	}
	}
	}

数据结构