之前学习了冒泡排序法和选择排序法，最近被老师问某个道题用的是什么排序法。自己居然答不出来，才发现自己没有真正弄懂，这两个算法的原理和区别，所以·····

1冒泡排序法

1.1什么是冒泡排序法？

顾名思义，冒泡排序法，就是把要排序的一组数据中的元素当成一个一个气泡,每次比较相邻两个相邻“气泡”的"轻重’，“气泡”较重的往下"沉"，轻的往上”浮“。

1.2原理

从第一个数开始，依次往后进行相邻两个数之间的比较，如果前面的数比后面的数大就交换这两个数的位置，如果前面的数较小或两者一样大，就不作处理。

1.3详细描述

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

1.4动态图片演示

1.5代码演示

1.5.1首先是从大到小

public class BubbleSortMax {
	public static void main(String[] args) {
		int[] array = { 1, 8, 5, 16, 32, 21 };
		int temp;
		System.out.print("原来数组排序为：");
		// for循环输出数组
		for (int i = 0; i< array.length; i++)
			System.out.print(array[i] + ",");
        //换行
		System.out.println();
		// 开始冒泡排序
		// 外层循环控制比较的趟数,一般为数组长度-1
		for (int i = 0; i < array.length - 1; i++) {
			// 内层循环控制每一趟排序多少次，一般为数组长度-外层循环变量-1
			for (int j = 0; j < array.length - i - 1; j++) {
				// 降序--如果前面小于后面则交换
				if (array[j] < array[j + 1]) {
					//引入temp变量作为交换媒介
					temp = array[j + 1];
					array[j + 1] = array[j];
					array[j] = temp;
				}
			}
		}
		System.out.print("由大到小的排序为：");
		// for循环输出数组
		for (int i= 0; i< array.length; i++)
			System.out.print(array[i] + ",");
	}
}

运行结果：

1.5.2从小到大排序

public class BubbleSortMin {
	public static void main(String[] args) {
		int[] array = { 1, 8, 5, 16, 32, 21 };
		int temp;
		System.out.print("原来数组排序为：");
		// for循环输出数组
		for (int i = 0; i < array.length; i++)
			System.out.print(array[i] + ",");
		// 换行
		System.out.println();
		// 开始冒泡排序
		// 外层循环控制比较的趟数,一般为数组长度-1
		for (int i = 0; i < array.length - 1; i++) {
			// 内层循环控制每一趟排序多少次，一般为数组长度-外层循环变量-1
			for (int j = 0; j < array.length - i - 1; j++) {
				// 升序--如果前面大于后面则交换
				if (array[j] > array[j + 1]) {
					// 引入temp变量作为交换媒介
					temp = array[j + 1];
					array[j + 1] = array[j];
					array[j] = temp;
				}
			}
		}
		System.out.print("由小到大的排序为：");
		// for循环输出数组
		for (int i = 0; i < array.length; i++)
			System.out.print(array[i] + ",");
	}
}

运行结果：

1.6对比分析

从上面两个排序我们可以发现，

1.外层控制循环的比较次数，循环次数：数组长度-1
2.内层控制循环排序次数，，循环次数：数组长度-外层循环变量-1
3.要实现一组数据的排序是从大到小还是从小到大，只需要改变下面这一行代码的比较大小符号即可。

if (array[j] > array[j + 1]) {

从小到大===大于号>

从大到小===小于号<

1.7冒泡排序法的主体框架

for (int i = 0; i < 数组长度变量名- 1; i++) {
			// 内层循环控制每一趟排序多少次，一般为数组长度-外层循环变量-1
			for (int j = 0; j <数组长度变量名   - i - 1; j++) {
				// 升序--如果前面大于后面则交换
				if (array[j] 视情况填写大于号和小于号array[j + 1]) {
					// 引入temp变量作为交换媒介
					temp = array[j + 1];
					array[j + 1] = array[j];
					array[j] = temp;
				}
			}
		}

1.8如何快速写出一个冒泡排序法

明白了原理，理解了从小到大和从大到小的规律，再记住冒泡排序法的基本框架，我们只需要确定几个量就可以写出一个冒泡排序法了。
步骤：
1.先确定所需要排序的数据元素个数----->用于确定外层循环的次数，循环次数：数组长度-1
2.确定内层循环次数，循环次数：数组长度-外层循环变量-1
3.根据从大到小还是从小到大的排序确定下面这行代码的符号
4.代入主体框架

if (array[j] 视情况填写大于号和小于号array[j + 1]) {

2.选择排序法

2.1什么是选择排序法？

还是顾名思义，选择排序法就是从需要排序的数据元素中 选出最小或最大的一个元素，把他和第一个位置的元素进行互换。

2.2原理

通过自定义的最小值元素的下标，在内层循环中通过下标进行比较，查找过程中不移动数位置, 如果发现比自定义最小值元素下标还要小的值，则将该值的下标赋值给自定义的最小值元素下标。在一次内层循环结束后，将最小值元素交换至数组左端。

2.3详细描述

将要排序的数组分成两个数组，一个是有序数组一个是无序数组，再定义一个最值下标
假定有序数组是数组的第一个元素，这个最值也假定为数组的第一个数，最值下标从第一个数开始
然后将有序数组中的数和最值下标指向的数进行比较， 如果无序数组中的数大于或小于有序数组中的数，那么将最大值或者最小值的下标更新为无序数组中那个值的下标
然后再将新的最大值或者最小值的下标和有序数组中的数比较，若大于或者小于，那就将它们两的值进行交换。

2.4动态图片演示

2.5代码演示

2.5.1首先是从大到小

public class SelectSortMax {
	public static void main(String[] args) {
		int[] a = { 1, 8, 5, 16, 32, 21 };
		int max;// 最大值下标
		int temp;
		// 外层循环控制循环次数,通常为数组长度-1
		for (int i = 0; i < a.length - 1; i++) {
			max = i;// 假设最大值是a[i],即a[0]
			for (int j = i + 1; j < a.length; j++) {
				if (a[j] > a[max])
					// 如果有比现在制定的最大元素还小的，就更新最大值下标
					max = j;
			}
//          退出内层循环后，判断最大下标是否
//			与原来相等，不等，说明有更大的，进行更新排序
//			if (a[i] != a[min]) {
			if (i != max) {
				// if (a[i] != a[min]) {//也可以更改这个
				temp = a[max];
				a[max] = a[i];
				a[i] = temp;
			}
		}
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + ",");
	}
}

运行结果：

2.5.2从小到大排序

public class SelectSortMin {
	public static void main(String[] args) {
		int[] a = { 1, 8, 5, 16, 32, 21 };
		int min;// 最小值下标
		int temp;
		// 外层循环控制循环次数,通常为数组长度-1
		for (int i = 0; i < a.length - 1; i++) {
			min = i;// 假设最小值是a[i],即a[0]
			for (int j = i + 1; j < a.length; j++) {
				if (a[j] < a[min])
					// 如果有比现在制定的最小元素还小的，就更新最小值下标
					min = j;
			}
//          退出内层循环后，判断最小下标是否
//			与原来相等，不等，说明有更小的，进行更新排序
			if (i != min) {
		//	if (a[i] != a[min]) {// 也可以更改为这个
				temp = a[min];
				a[min] = a[i];
				a[i] = temp;
			}
		}
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + ",");
	}
}

运行结果：

2.6对比分析

1.外层控制循环的比较次数，循环次数：数组长度-1
2.内层控制循环排序次数，循环次数：数组长度
3.要实现一组数据的排序是从大到小还是从小到大，只需要改变下面这一行代码的比较大小符号即可。

	if (a[j] < a[min])
	//或者是if (a[j] > a[max])

从小到大===大于号<

从大到小===小于号>

2.7冒泡排序法的主体框架

int max;// 最大值下标
		int temp;
		// 外层循环控制循环次数,通常为数组长度-1
		for (int i = 0; i < a.length - 1; i++) {
			max = i;// 假设最大值是a[i],即a[0]
			for (int j = i + 1; j < a.length; j++) {
				if (a[j] 视情况填写大于号和小于号 a[max])
					// 如果有比现在制定的最大元素还小的，就更新最大值下标
					max = j;
			}
//          退出内层循环后，判断最大下标是否
//			与原来相等，不等，说明有更大的，进行更新排序
			if (i != max) {
				// if (a[i] != a[min]) {//也可以更改这个
				temp = a[max];
				a[max] = a[i];
				a[i] = temp;
			}
		}

2.8如何快速写出一个冒泡排序法

还是和前面差不多。
1)明白原理，2）理解从小到大和从大到小的规律，3）再记住冒泡排序法的基本框架，
开始步骤：
1.先确定所需要排序的数据元素个数----->用于确定外层循环的次数，循环次数：数组长度
2.确定内层循环次数，循环次数：数组长度
3.根据从大到小还是从小到大的排序确定下面这行代码的符号
if (a[j] < a[min]) //或者是if (a[j] > a[max])

4.代入主体框架

3 最后总结

3.1两种排序算法之间的共同点

1）都有两层循环，外层循环控制比较的轮数，和数组元素的个数有关，内层循环控制需要参与比较的元素个数，和外层循环的轮数有关
2）两种算法进行交换的结构是相同的。（本文采用借助中间变量的方法交换是为了便于读者理解，在实际编程中，往往采用直接交换的写法，而不借助中间变量，来提高效率和简洁化）
3）两种算法虽然效率不一样，但是最终比较的次数是一样的。

如何区分两种算法？------个人技巧，大佬轻喷

1）最好的就是记住主体框架了（理解后就很好记了），当然实在记不住，那下面是一个小方法，

2）在选择排序算法中，会有定义一个记录最大值或者最小最小值下标的变量，只要是看到有一个这样的变量那就是选择排序算法，没有的话，就是冒泡排序法

3）就是我们一般常用的是冒泡排序法（看书和网上的案例都是冒泡居多）。但是如果项目涉及效率提高，性能优化的时候往往会使用选择排序法
为什么？
一是代码长度的问题，二是效率和复杂度问题，这个可以去看一下两个算法的排序换位操作。
冒泡排序算法中每次比较，两层循环都必须完全执行，因此对于任何情况下它的效率都是比较慢的。所以，你懂得。。。

4最后一些小问题解决

好像初中就学过，不过太久远，忘记了。

word横线怎么打
https://jingyan.baidu.com/article/00a07f380d690c82d028dcf9.html

在word文档中怎么设置每段的开头空两格？
https://zhidao.baidu.com/question/560399680.html

在Word中输入后文字下面会出现蓝色的双下划线怎么取消
https://www.kafan.cn/A/gvxexzp8nr.html

图片及部分内容借鉴于https://blog.csdn.net/weixin_40205234/article/details/86699088

在各类算法问题中，排序算法是最基本的一个问题，在项目中经常遇到一些数据按照从小到大排序或者从大到小的顺序进行排列。对于一个排好顺序的序列来讲，在进行查找最大值，最小值，遍历，计算和求解等各种操作时十分方便。由于本人在开发过程中经常遇到，在此系统的总结一下，在扩充自己的知识体系外，也帮助大家更全面的了解一下排序算法，有不足之处希望大家多多指教。

言归正传，总的来说，排序算法包括基本排序算法和多路归并排序。而基本排序算法包括交换排序、选择排序、插入排序和合并排序，其中，交换排序又包括冒泡排序法和快速排序法；选择排序包括选择排序法和堆排序法；插入排序包括插入排序法和Shell排序法。对于一些较大的文件，由于计算机内存有限，往往不能直接将其读入内存进行排序，因此要采用多路归并排序法，将文件划分为几个能够读入内存的小部分，然后分别读入进行排序，经过多次处理便可以完成大文件的排序。

 排序算法的详细介绍（排序对象基本为整数，其他数据类型都类似）

基本排序介绍

 一、交换排序

1、冒泡排序法（BubbleSort）

冒泡排序法的思路是交换排序，通过相邻数据的比较交换来达到排序的目的。冒泡排序法在对N个数据进行排序时，无论数据有无顺序，都需要进行N-1步的中间排序，思路简单直观，但是执行的步骤比较长，效率太低。改进的方法是在每次中间排序之后，比较一下数据是否已经按照顺序排列完成，如果排列完成则退出排序过程，否则继续进行冒泡排序。这样做可以加速算法的执行过程。

冒泡排序法是通过多次比较和交换来实现排序，它的流程如下：

（1）对数组中的各数据，依次比较相邻两个数据的大小；

（2）如果前面的数据小于后面的数据，就交换这两个数据（从大到小排）。经过第一轮的多次比较排序后，便可以把最大的数据排好；

（3）再用同样的方法把剩下的数据进行逐个进行比较，最后便可以按照从大到小的顺序排好数组中各个数据的顺序。

冒泡排序算法的验证代码如下：

//冒泡排序法代码

2、快速排序法（Quick  Sort）

快速排序法和冒泡排序法类似，都是基于交换排序的思想，但是快速排序具有更高的执行效率。快速排序法是通过多次比较和交换来实现的，它的排序流程如下：

（1）首先设定一个分界值，通过该分界值讲数组分成左右两个部分；

（2）将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边；

（3）左边和右边的数据进行独立排序，对于左侧的数组数据，又可以区一个分界值，讲该部分的数据分成左右两个部分，同样在左边放置较小的数据，右边放置较大的数据。

（4）重复上述过程。通过递归将左侧的数据排列好，再通过递归将右侧的数据排列好，当左右两侧各个数据排列完成后，整个数组的排序也就排好了。

快速排序算法的验证代码如下：

//快速排序法代码

二、选择排序

1、选择排序法（Selection Sort）

选择排序法思路比较直观，在每一步中选取最小值重新排列，从而达到排序的目的。选择排序算法通过选择和交换来实现排序，它的基本流程是：

（1）在原始数据中选取最小的一个数据，将他和位于第一个位置的数据进行交换；

（2）从剩下的N-1个数据中选择次小的一个元素，将他和位于第2个位置的数据进行交换；

（3）不断重复，知道最后两个数据交换完成。最后完成对原始数据从小到大的排序。

选择排序算法的验证代码如下：

//选择排序法代码

2、堆排序法（Heap Sort）

堆排序法是基于选择排序的思想，利用堆结构和二叉树的一些性质来完成对数据的排序，应用较广泛。堆排序的关键在于构造堆结构。什么是堆结构，我的理解是堆结构就是一种树结构，准确地讲是一个完全二叉树。在这个树中每个节点对应原始数据的一个记录，并且每个节点满足一下条件：

a:如果按照从小到大排序，则要求非叶节点的数据要大于或者等于他的左、右子结点的数据。

b:如果按照从大到小排序，则要求非叶节点的数据要大于或者等于他的左、右子结点的数据。

堆排序法需要反复经过两个步骤：构造堆结构和堆排序输出。

（1）构造堆结构

构造对结构就是原始的无序数据按照对结构的定义进行调整，需将原始的无序数据放置到一个完全二叉树的各个结点中。

（2）堆排序输出

根结点存放的是最大值或者最小值；对除最后一个结点的其他结点重新执行堆构造过程。

堆排序算法的验证代码如下：

//堆排序法代码

三、插入排序

1、插入排序（Insertion Sort）

插入排序法是通过对未排序的数据逐个插入合适的位置而完成的排序。

插入排序是通过比较和插入来实现排序的算法，它的基本排序流程如下：

（1）首先对数组的前两个数据进行从小到大排序（或者从大到小）；

（2）将第三个数据与排好的两个数据进行比较，将第三个数据插入到合适的位置；

（3）将第四个数据插入到已经排好队的前三个数据中；

（4）不断重复上述过程，直到把最后一个数据插入到合适的位置。

插入排序算法的验证代码如下：

//插入排序法代码

2、Shell排序法

Shell排序算法是处理大量数据其中的一种算法，严格来讲，他是基于插入排序的思想，又称为希尔排序或者缩小增量排序。他的排序流程如下：

（1）将有N个元素的数组分成N/2个数据来进行排序，第一个数据和第N/2+1个数据为一对，依此类推；

（2）一次循环使每一个序列对排好顺序；

（3）变为N/4个序列，再次排序；

（4）不断重复上述过程，知道序列变为最后一个为止。

Shell排序算法的验证代码如下：

//Shell排序法代码

四、合并排序

合并排序法就是将多个有序的数据表合并成一个有序的数据表。如果参与合并的只有两个有序表，简称为二路合并。合并排序 的基本思路是：（1）将含有N个结点的待排序数据序列看成有N个长度为1的有序子表组成，并且将他们两两合并，得到长度为2的若干有序子表；（2）对这些有序子表再进行两两合并，得到长度为4的若干有序子表；（3）不断的重复上述过程，知道最后的子表长度为N。

合并序算法的验证代码如下：

//合并排序法代码

多路归并排序（后续）

以上是个人对排序算法的总结，有不足之处还望大家多多指出，希望这篇文章能够帮助到大家，完整的测试代码太长，挂到博客中会导致篇幅太长，如有需要，大家可私下留言，留下邮箱，我看到会打包发送过去！谢谢！

十大经典排序算法

• 十大经典排序算法-冒泡排序算法详解
• 十大经典排序算法-选择排序算法详解
• 十大经典排序算法-插入排序算法详解
• 十大经典排序算法-希尔排序算法详解
• 十大经典排序算法-快速排序算法详解
• 十大经典排序算法-归并排序算法详解
• 十大经典排序算法-堆排序算法详解
• 十大经典排序算法-计数排序算法详解
• 十大经典排序算法-桶排序算法详解
• 十大经典排序算法-基数排序算法详解

一、什么是归并排序

1.概念

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，合并成一个大的分组，逐层进行，最终所有的元素都是有序的

2.算法原理

这是一个无序数列：4、5、8、1、7、2、6、3，我们要将它按从小到大排序。按照归并排序的思想，我们要把序列逐层进行拆分

序列逐层拆分如下

然后从下往上逐层合并，首先对第一层序列1（只包含元素4）和序列2（只包含元素5）进行合并

创建一个大序列，序列长度为两个小序列长度之和，p1、p2指针分别指向两个小序列的第一个元素，p指向大序列的第一个元素

比较p1、p2指向的元素，4小于5，将4填入p指向的元素，p、p1往右移一位

此时，序列1已经没有元素，将序列2的元素依次填入大序列中

序列8和1，序列7和2，序列6和3，用同样的方式填入新的序列

接着，以4、5为序列1，1、8为序列2，继续进行合并

创建一个序列长度为4的大序列，p1指向序列1的第一个元素4，p2指向序列2的第一个元素1，p指向大序列的第一个元素

4和1比较，4大于1，1填入p指向的元素，p、p2往右移一位

4和8比较，4小于8，4填入p指向的元素，p、p1往右移一位

5和8比较，5小于8，5填入p指向的元素，p、p1往右移一位

自此，序列1已经没有元素，将序列2的元素依次填入大序列中

序列2、7和序列3、6以同样的方式合并成新的序列

最后，将序列1、4、5、8和序列2、3、6、7以同样的方式继续合并成新的序列

至此所有的元素都是有序的

3.算法实现

function sort(arr, startIndex = 0, endIndex = arr.length - 1) {
    // 递归结束条件：startIndex大于等于endIndex的时候
    if (startIndex >= endIndex) {
        return;
    }

    // 折半递归
    let midIndex = parseInt((startIndex + endIndex) / 2);
    sort(arr, startIndex, midIndex);
    sort(arr, midIndex + 1, endIndex);
    // 将两个有序的小数组，合并成一个大数组
    merge(arr, startIndex, midIndex, endIndex);
}

function merge(arr, startIndex, midIndex, endIndex) {
    // 新建一个大数组
    let tempArr = [];
    let p1 = startIndex;
    let p2 = midIndex + 1;
    let p = 0;

    // 比较两个有序小数组的元素，依次放入大数组中
    while (p1 <= midIndex && p2 <= endIndex) {
        if (arr[p1] <= arr[p2]) {
            tempArr[p++] = arr[p1++];
        } else {
            tempArr[p++] = arr[p2++];
        }
    }

    // 右侧小数组已排序完毕，左侧小数组还有剩余，将左侧小数组元素依次放入大数组尾部
    while (p1 <= midIndex) {
        tempArr[p++] = arr[p1++];
    }
    // 左侧小数组已排序完毕，右侧小数组还有剩余，将右侧小数组元素依次放入大数组尾部
    while (p2 <= endIndex) {
        tempArr[p++] = arr[p2++];
    }

    for (let i = 0; i < tempArr.length; i++) {
        arr[i + startIndex] = tempArr[i];
    }
}

let arr = [4, 5, 8, 1, 7, 2, 6, 3];
sort(arr);
console.log(arr);

二、归并排序算法特点

1.时间复杂度

归并排序算法每次将序列折半分组，共需要logn轮，因此归并排序算法的时间复杂度是O(nlogn)

2.空间复杂度

归并排序算法排序过程中需要额外的一个序列去存储排序后的结果，所占空间是n，因此空间复杂度为O(n)

3.稳定性

归并排序算法在排序过程中，相同元素的前后顺序并没有改变，所以归并排序是一种稳定排序算法