八种排序算法可以按照如图分类
前置知识
1. 算法稳定性
在一个序列中，能保证两个相等的数，经过排序之后，其在序列的前后位置顺序不变（A1 = A2，排序前 A1 在 A2 前面，排序后 A1 还在 A2 前面）
2. 时间复杂度
时间复杂度是用于衡量一个算法的运算时间的一个描述，常用大 O 来表示
假设一个场景：在一个长度为 n 的数组 Array 查找某一特定元素 k，采用遍历的算法来查找。这种算法在不同情况下，时间复杂度也是不一样的。所以，为了描述算法在不同情况下的时间复杂度，我们引入了最好、最坏、平均时间复杂度
考虑以下场景：
- k 在数组的第一个位置，那么时间复杂度为 O(1)
- k 在数组的最后一个位置，那么时间复杂度为 O(n)
- k 不在数组当中，需要遍历完数组才能知道，那么时间复杂度为 O(n)
由以上情况可知，最好时间复杂度就是最理想的情况，也就是 O(1)，最坏时间复杂度就是最糟糕的情况，也就是 O(n)
其实最好与最坏都是极端情况，发生的概率并不大。为了能更好的的表示平均情况下的时间复杂度，引入了平均时间复杂度。还是上述的算法，我们知道 k 在数组中出现的情况有 n + 1 种，在数组中有 n 种，不在数组中有 1 种。每种情况要遍历的次数都不一样，我们把这种情况需要遍历的次数累加，然后除以所有情况数，就能得到遍历次数的评价数，即平均时间复杂度为：((1+2+3+…+n) + n) / (n + 1) = n(n+3) / 2(n+1)，由此可以得到公式：平均情况时间复杂度 = 每种情况遍历次数累加和 / 所有情况数量
对于大 O 时间复杂度表示法，常量、低阶、系数可以忽略，所以平均时间复杂度是 O(n)
3. 空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个度量，常见的空间复杂度有 O(1)、O(n)、O(n^2)
交换排序
所谓交换，就是序列中任意两个元素进行比较，根据比较结果来交换各自在序列中的位置，以此达到排序的目的。
1. 冒泡排序
冒泡排序是一种简单的交换排序算法，以升序排序为例，其核心思想是：
- 从第一个元素开始，比较相邻的两个元素。如果第一个比第二个大，则进行交换。
- 轮到下一组相邻元素，执行同样的比较操作，再找下一组，直到没有相邻元素可比较为止，此时最后的元素应是最大的数。
- 除了每次排序得到的最后一个元素，对剩余元素重复以上步骤，直到没有任何一对元素需要比较为止。
用 Java 实现的冒泡排序如下
2. 冒泡排序优化
现在有个问题，假如待排序数组是 2、1、3、4、5 这样的情况，按照上述代码实现，第一次循环即可得出正确结果。但循环并不会停止，而是继续执行，直到结束为止。显然，之后的循环遍历是没有必要的。
为了解决这个问题，我们可以设置一个标志位，用来表示当前次循环是否有交换，如果没有，则说明当前数组已经完全排序。
算法还可以再优化，比如 3、4、2、1、6、7、8 这个数组，第一次循环后，变为 3、2、1、4、6、7、8 的顺序，我们发现，1 之后的 4 、6、7、8 已经有序了，第二次循环就没必要对后面这段再遍历比较。
假设一次循环后数组第 i 个元素后所有元素已经有序，优化目标就是下次循环不再花费时间遍历已经有序的部分。关键在于如何定位 i 这个分界点，其实并不难，可以想象，由于 i 之前的元素是无序的，所以一定有交换发生，而 i 之后的元素已经有序，不会发生交换，最后发生交换的地点，就是我们要找的分界点。
3. 快速排序
快速排序的思想很简单，就是先把待排序的数组拆成左右两个区间，左边都比中间的基准数小，右边都比基准数大。接着左右两边各自再做同样的操作，完成后再拆分再继续，一直到各区间只有一个数为止。
举个例子，现在我要排序 4、9、5、1、2、6 这个数组。一般取首位的 4 为基准数，第一次排序的结果是：
2、1、4、5、9、6
可能有人觉得奇怪，2 和 1 交换下位置也能满足条件，为什么 2 在首位？这其实由实际的代码实现来决定，并不影响之后的操作。以 4 为分界点，对 2、1、4 和 5、9、6 各自排序，得到：
1、2、4、5、9、6
不用管左边的 1、2、4 了ÿjava基础 选择排序实例教学0c;将 5、9、6 拆成 5 和 9、6，再排序，至此结果为：
1、2、4、5、6、9
为什么把快排划到交换排序的范畴呢？因为元素的移动也是靠交换位置来实现的。算法的实现需要用到递归（拆分区间之后再对每个区间作同样的操作）
用 Java 实现的快速排序如下
插入排序
插入排序是一种简单的排序方法，其基本思想是将一个记录插入到已经排好序的有序表中，使得**入数的序列同样是有序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程。
1. 直接插入排序
直接插入排序就是插入排序的粗暴实现。对于一个序列，选定一个下标，认为在这个下标之前的元素都是有序的。将下标所在的元素插入到其之前的序列中。接着再选取这个下标的后一个元素，继续重复操作。直到最后一个元素完成插入为止。我们一般从序列的第二个元素开始操作。
用 Java 实现的算法如下：
2. 希尔排序
某些情况下直接插入排序的效率极低。比如一个已经有序的升序数组，这时再插入一个比最小值还要小的数，也就意味着**入的数要和数组所有元素比较一次。我们需要对直接插入排序进行改进。
怎么改进呢？前面提过，插入排序对已经排好序的数组操作时，效率很高。因此我们可以试着先将数组变为一个相对有序的数组，然后再做插入排序。
希尔排序能实现这个目的。希尔排序把序列按下标的一定增量（步长）分组，对每组分别使用插入排序。随着增量（步长）减少，一直到一，算法结束，整个序列变为有序。因此希尔排序又称缩小增量排序。
一般来说，初次取序列的一半为增量，以后每次减半，直到增量为一。
用 Java 实现的算法如下：
选择排序
选择排序是一种简单直观的排序算法，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
1. 简单选择排序
选择排序思想的暴力实现，每一趟从未排序的区间找到一个最小元素，并放到第一位，直到全部区间有序为止。
用 Java 实现的算法如下：
2. 堆排序
我们知道，对于任何一个数组都可以看成一颗完全二叉树。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
像上图的大顶堆，映射为数组，就是 [50, 45, 40, 20, 25, 35, 30, 10, 15]。可以发现第一个下标的元素就是最大值，将其与末尾元素交换，则末尾元素就是最大值。所以堆排序的思想可以归纳为以下两步：
- 根据初始数组构造堆
- 每次交换第一个和最后一个元素，然后将除最后一个元素以外的其他元素重新调整为大顶堆
重复以上两个步骤，直到没有元素可操作，就完成排序了。
我们需要把一个普通数组转换为大顶堆，调整的起始点是最后一个非叶子结点，然后从左至右，从下至上，继续调整其他非叶子结点，直到根结点为止。
归并排序
归并排序是建立在归并操作上的一种有效，稳定的排序算法。该算法采用分治法的思想，是一个非常典型的应用。归并排序的思路如下：
- 将 n 个元素分成两个各含 n/2 个元素的子序列
- 借助递归，两个子序列分别继续进行第一步操作，直到不可再分为止
- 此时每一层递归都有两个子序列，再将其合并，作为一个有序的子序列返回上一层，再继续合并，全部完成之后得到的就是一个有序的序列
关键在于两个子序列应该如何合并。假设两个子序列各自都是有序的，那么合并步骤就是：
- 创建一个用于存放结果的临时数组，其长度是两个子序列合并后的长度
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入临时数组，并移动指针到下一位置
- 重复步骤 3 直到某一指针达到序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
用 Java 实现的归并排序如下：
基数排序
基数排序的原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。为此需要将所有待比较的数值统一为同样的数位长度，数位不足的数在高位补零。
使用 Java 实现的基数排序：
八种排序算法的总结
其他算法
1. 剪枝算法
剪枝算法属于算法优化范畴，通过剪枝策略，提前减少不必要的搜索路径。在搜索算法的优化中，剪枝算法通过某种预判去掉一些不需要的搜索范围，相当于剪去了搜索树中的某些“枝条”，故称剪枝。剪枝优化的核心是设计的剪枝预判，即哪些“枝条”被剪掉后可以缩小搜索范围，提高搜索效率而又不影响整体搜索的准确性
2. 回溯算法
回溯算法是一种最优选择搜索算法，按选优条件向前搜索，以达到目标。如果在探索到某一步时，发现原先的选择并不是最优选择或达不到目标，就进一步重新选择，这种走不通就退回再走的方法叫作回溯法，而满足回溯条件的某个状态的点叫作回溯点
3. 最短路径算法
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/h6javajc/20592.html