- 性能对照表
- 冒泡排序
- 动画排序过程
- 执行流程
- 未优化前的代码
- 冒泡排序优化 - 01
- 冒泡排序优化 - 02
- 选择排序
- 动画排序过程
- 执行流程
- 代码实现
- 插入排序
- 动画排序过程
- 概述
- 执行流程
- 代码实现
- 插入排序优化 - 01
- 插入排序优化 - 02
- 希尔排序
- 动画排序过程
- 执行流程
- 代码实现
- 总结
- 归并排序
- 动画排序过程
- 执行流程
- 实现代码
- 总结
- 快速排序
- 动画排序过程
- 执行流程
- 代码实现
- 堆排序
- 桶排序
- 动画排序过程
- 概述
- 执行流程
- 代码实现
- 总结
- 借鉴的优秀博文
| 排序算法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | 取决于增量序列 | O(n) | O(n^2) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~O(n) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 桶排序 | O(n+k) | O(n+k) | O(n+k) | O(n+m) | 稳定 |
基本原理:
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较，让较小的数往下沉，较大的往上冒。即：每当两相邻的数比较后发现他们的排序与排序要求相反时，就将他们互换。
优缺点:
优点：稳定
缺点：慢，每次只能移动两个相邻的数据；
package 排序算法;
public class 冒泡排序 {
public static void main(String[] args) {
int[] arr = {12,2,0,-1,45,0,12,45,78,45};
System.out.println("排序前：");
for(int i: arr){
System.out.print(i+" ");
}
sort(arr);
System.out.println();
System.out.println("排序后：");
for(int i: arr){
System.out.print(i+" ");
}
}
public static void sort(int[] arr) {
for (int end=arr.length-1; end>0; end--) {
for (int begin=1; begin<=end; begin++) {
if (arr[begin] < arr[begin-1]) {
int temp = arr[begin-1];
arr[begin-1] = arr[begin];
arr[begin] = temp;
}
}
}
}
}
解释：
- 首先看内层for循环，begin表示每一轮比较的初始下标（我习惯于用后一个跟前一个比较，因此我初始值设为1而不是0，我判断的代码是if (arr[begin] < arr[begin-1])，刚开始比较的话就是 if (arr[1] < arr[0]) ）
- 当不满足begin<=end的条件就结束循环，这里end表示的是每一轮比较的最后下标（因此这里我用的是小于等于而不是小于），因为这个最后下标会随着每一轮比较的结束，越来越小，因此这个end就对应最外层for循环的循环变量
- 最外层for循环，我的end初始值是arr.length-1，表示第一轮循环的最后下标是arr.length-1，end–，直到end为1的时候（终结条件end>0）结束所有比较！！！！
演示效果：
思考：未优化前的代码，每轮比较，如果在比较前的代码已经有序，我们仍然需要循环且比较，这种循环并比较是没有意义的，因为数组已经有序了。
思路：我们可以加一个Boolean类型的标志flag来监控每一轮比较是否发生交换，初始值为true，如果发生交换就将flag设为false，最后判断如果flag为true（没有发生任何交换，说明已经有序）就break退出整个外层循环。结束！！！！
public static void sort1(int[] arr) {
for (int end=arr.length-1; end>0; end--) {
Boolean flag = true; // 加一个Boolean类型的标志来监控，每一轮比较是否发生交换
for (int begin=1; begin<=end; begin++) {
if (arr[begin] < arr[begin-1]) {
int temp = arr[begin-1];
arr[begin-1] = arr[begin];
arr[begin] = temp;
flag = false; // 如果发生交换就将flag设为false
}
}
if (flag) break; // 如果flag为true，说明这一轮并未发生任何交换，也就意味着数组已经有序
}
}
冒泡排序优化 - 02
前言：上述那个优化，触发的概率很小，只有当每轮比较所有的数据已经完全有序之后才会触发生效。
我再提供一个触发概率比较大的优化。。。
思考：每轮比较，如果序列尾部已经局部有序，按照以前的代码，end值还是end–，需要逐步-1，其实这是没必要的，因为尾部已经局部有序了，应该让end直接变成尾部无序最后一个下标（也就是尾部局部有序序列的第一个下标的前一个下标）
思路：我们可以记录最后一次交换的位置，减少比较的次数
public static void sort2(int[] arr) {
for (int end=arr.length-1; end>0; end--) {
int sortedIndex = 1; // sortedIndex用来记录最后交换的下标，它的初始值是在数组完全有序的时候用的，用来结束最终循环
for (int begin=1; begin<=end; begin++) {
if (arr[begin] < arr[begin-1]) {
int temp = arr[begin-1];
arr[begin-1] = arr[begin];
arr[begin] = temp;
sortedIndex = begin; // 将交换后的下标赋值给sortedIndex
}
}
end = sortedIndex; // 将sortedIndex（最终交换的下标）赋值给end
}
}
选择排序
动画排序过程
执行流程
基本原理:
第一趟：从第1个记录开始，将后面n-1个记录进行比较，找到（选择）其中最小的记录和第一个记录进行交换；
第二趟：从第2个记录开始，将后面n-2个记录进行比较，找到（选择）其中最小的记录和第2个记录进行交换；
…
第i趟：从第i个记录开始，将后面n-i个记录进行比较，找到（选择）其中最小的记录和第i个记录进行交换；
以此类推，经过n-1趟比较，将n-1个记录排到位，剩下一个最大记录直接排在最后；
代码实现public class 选择排序 {
public static void main(String[] args) {
int[] arr = {12,2,0,-1,45,0,12,45,78,45};
System.out.println("排序前：");
for(int i: arr){
System.out.print(i+" ");
}
sort(arr);
System.out.println();
System.out.println("排序后：");
for(int i: arr){
System.out.print(i+" ");
}
}
public static void sort(int[] arr) {
int l = arr.length;
// begin表示最前面的、最终要交换的下标。每比较一轮,说明已经找到一个最小的，然后再从下一个开始再来一轮新的比较，即begin+1
for (int begin=0; begin
解释：
- begin表示最前面的、最终要交换的下标。每比较一轮,说明已经找到一个最小的，然后再从下一个开始再来一轮新的比较，即begin+1
- minIndex用来记录这一轮比较中，数值最小的，它的下标
- next表示要跟最小值（arr[minIndex]）比较的值的下标
- 如果下一个值比最小值还小，就用这个值的下标重新赋值给minIndex
- 这一轮比较结束后，并找到最小值的下标后，就用这个最小值与最前面的值进行交换
演示效果：
插入排序
动画排序过程
概述
插入排序非常类似于打扑克牌并为其排序。拿到手里的牌就是已排序好的，还未起的牌就是待排序的牌。
执行流程
- 在执行过程中，插入排序会将序列分为2部分； 头部是已经排序好的，尾部是待排序的；
- 从头开始扫描每一个元素；每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序；
代码实现
package 排序算法;
public class 插入排序 {
public static void main(String[] args) {
int[] arr = {0,9,8,6,5,7,3,1,2,4,0,10,11,12,13,15};
System.out.println("排序前：");
for(int i: arr){
System.out.print(i+" ");
}
sort1(arr);
System.out.println();
System.out.println("排序后：");
for(int i: arr){
System.out.print(i+" ");
}
}
public static void sort(int[] arr) {
// begin表示当前要插入的元素（类比打扑克，相当于刚起的的牌），因为这张牌要跟前一个比较，因此begin从1开始
for (int begin=1; begin=0 && arr[cur]
演示效果：
插入排序优化 - 01
我们会发现前面那个代码需要大量的交换，需要三行代码。我们可以避免这种交换，转变成如果前面的值比后面的值大，就让前面的值直接向后移动即可，前提是我们需要提前备份要插入的值。
public static void sort1(int[] arr) {
for (int begin=1; begin=0 && value
插入排序优化 - 02
如上代码我们会发现，当我们在找某个值要插入的合适位置时，我们需要当前值跟前面的值一个一个的进行比较，如果数据比较多，这种比较效率是比较低的。因为数组前部分是有序队列，而我们这里是想要找到某个合适的位置，这里我们可以考虑用二分查找法去查找这个位置，便可以大大提高我们的查找效率。
想要了解二分查找去看一下这片文章 【二分查找法】
怎么找到这个合适的值呢？
其实就是要找到有序队列中，第一个大于插入数据的值的位置，这个位置就是我们要插入的位置
查找代码：
public static int firstBig(int[] arr, int v) {
if (arr==null || arr.length<0) return -1; // 如果数组为空则直接返回-1，表示搜索失败
int begin = 0; // begin初始值设为0
int end = arr.length; // 左闭右开[begin,end)
while (begin < end) {
int min = (begin+end) >> 1;
if (v=min) { // 因为我们要找的是第一个大于v的值，因此这个 '='必须与'>'关联到一块儿
begin = min+1;
}
}
return begin; // 等begin=end的时候，就是我们要找的下标
}
插入排序优化代码：
public static void sort2(int[] arr) {
for (int begin=1; begin=i) {
arr[mv+1] = arr[mv];
mv--;
}
arr[i] = value;
}
}
public static int firstBig(int[] arr, int index) {
int v = arr[index];
if (arr==null || arr.length<0) return -1; // 如果数组为空则直接返回-1，表示搜索失败
int begin = 0; // begin初始值设为0
int end = index; // 左闭右开[begin,end)
while (begin < end) {
int min = (begin+end) >> 1;
if (v=min) { // 因为我们要找的是第一个大于v的值，因此这个 '='必须与'>'关联到一块儿
begin = min+1;
}
}
return begin; // 等begin=end的时候，就是我们要找的下标
}
希尔排序
动画排序过程
执行流程
希尔排序是插入排序的改进版本，弥补了插入排序在某些情况下的缺点。
例如，当长度为100的数组，前面有序区域的数组长度为80，此时我们用第81个数去跟前面有序区域的所有元素比较大小，但恰巧第81个数又是这100个数里最小的，它本应该在索引为1的位置，如图所示
本例中第81个数据的值为1，那么前面有序区域里的80个元素都要往后移动一个位置，这种情况就非常影响排序性能。
因此，我们就要想办法尽可能早点让小的值靠前，让大的值靠后，这样就能避免上述情况了，这就是希尔排序要解决的问题。
希尔排序也叫做缩小增量排序，它通过先设置一个增量n（增量的求法是自己定义的，你的希尔排序的时间复杂度跟你自定义的增量规则有关，这里我们定义一个简单的增量规则n=n/2），大小为数组长度的一半，将间隔为n的元素视作一个组，然后对每个组内部的元素进行从小到大进行插入排序；然后再将增量n缩小一半，再次进行分组插入排序，直到增量n为1，因为增量为1的时候，所有的元素都为同一个组了
为了方便大家理解，我用一个例子来展示一个完整的希尔排序过程，首先数据的初始状态如图所示，这里为了更好地体现希尔排序的优点，我特地把值较大的元素放到了靠左的位置，把值较小的元素放到了靠右的位置
该数组长度为8，因此我们设置初始的增量为 8 / 2 = 4，那么该数组的分组情况如下图所示：
图中颜色相同的元素为一组，每组内的各个元素间隔都为4，现在对每个组内进行从小到大排序，排序结果如下图所示：
此时我们将增量缩小一半，即 4 / 2 = 2，同样的，现在将所有元素重新组合，把所有间隔为2的元素视作一组，分组结果如下图所示：
图中颜色相同的元素为一组，每组内的各个元素间隔都为2，现在对每个组内进行从小到大排序，排序结果如下图所示：
我们继续将增量缩小一半，即 2 / 2 = 1，同样的，现在将所有元素重新组合，把所有间隔为1的元素视作一组，此时所有的元素都为同一组了，就相当于对所有的数据进行普通的插入排序，我们可以看到，对比最开始的数据，总得来说，小的值都比较靠左了，大的值也都比较靠右了，这样排序起来效率就很高了。结果如下图所示：
接下来用一个动图，演示一下完整的希尔排序全过程
代码实现
根据上述流程的讲解相信大家都应该有思路了，接下来演示我写希尔排序的步骤
1、首先写出插入排序算法
public static void sort1(int[] arr) {
for (int begin=1; begin=0 && value
这段代码是上面插入排序-优化01的代码，我们在这个段代码的基础上简单修改即可
2、首先加个for循环，step作为增量， 来表示根据增量不同，进行不同轮的排序，每一轮我们都使用插入排序对序列排序
for (int step=arr.length/2; step>0; step/=2){
}
3、将第一步中插入排序的代码直接放到循环中
for (int step=arr.length/2; step>0; step/=2){
for (int begin=1; begin=0 && value
这段代码目前是不能运行的，接下来我们稍作修改
- 首先第二层for循环的初始值begin就不能为1了，应该为step
- 然后while循环里的条件要变一下，应该写成while (cur-step>=0 && value
- while代码段里，改成arr[cur] = arr[cur-step]; cur-=step;
4、修改完成后的代码
//希尔排序
public static void sort(int[] arr) {
for (int step=arr.length/2; step>0; step/=2){
for (int begin=step; begin=0 && value
总结
上述情况中，希尔排序最坏情况下的时间复杂度为O(n²)。其实希尔排序的时间复杂度跟增量也有关系，我们上面是通过数组长度一直取一半获取的增量，其实还有一些别的增量规则，可以使得希尔排序的效率更高，例如Hibbard增量序列、Sedgewick增量序列，本文就不对这两种增量做过多的讲解了，大家可以去网上搜索一下。
归并排序
动画排序过程
执行流程
归并排序采用了 分治（Divide and Conquer）和 递归（Recursion）的思想（快速排序也是一样，这里你可以和快速排序比较一下他们的区别）
流程：
- 划分：将待排序列二分，一直向下划分，直到只有一个元素为止（只有一个元素相当于已排序）
- 合并：将已排序的两个子序列合并为一个新的有序序列（主要逻辑）
实现代码
归并排序实现代码：
public static void sort(int[] arr, int[] tempArr, int left, int right) {
// 如果只有一个元素，那么就不需要再继续划分了 （只有一个元素本身就是有序的，只需要被合并即可）
// 如果 left
测试代码：
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入你想生成随机数的个数");
int num = sc.nextInt();
int[] arr = new int[num];
int[] tempArr = new int[num];
for (int i=0; i
总结
空间复杂度：O(n)
- 因为创建一个相同大小的临时数组嘛
时间复杂度：O(NlogN)
- 每一层归并的时间复杂度为O(N)
- 归并层数最大为O(logN+1)
快速排序
动画排序过程
执行流程
执行流程：
- 从序列中选择一个轴点元素（pivot）。假设每次选择第一个位置的元素为轴点元素；
- 利用pivot将序列分割成2个子序列 。 将小于pivot的元素放到pivot前面（左侧）；将大于pivot的元素放到pivot后面（右侧）；等于pivot的元素放到哪都可以；
- 对子序列进行1、2操作。直到不能再分割（子序列中只剩下一个元素）；
案列图：
快速排序的大致思想我们了解了，关键是我们怎么构建轴点呢？
轴点构造：
- 一般选取数组的第一个元素作为轴点元素（pivot）
- 将轴点元素（pivot）备份一份，后面会用
- begin表示坐标，初始值是轴点坐标；end表示坐标，初始值是最后元素下标；
- 从右向左开始检索。如果end坐标的元素大于轴点元素，则不用动，end–；检索下一个end，如果end坐标元素小于轴点元素，则将end元素赋值给begin坐标（因为之前pivot已经备份了，所以不会造成数据丢失），然后让begin++，开始从左向右检索
- 从左向右开始检索。如果begin坐标的元素小于轴点元素，则不用动，begin++；检索下一个begin，如果begin坐标元素大于轴点元素，则将begin元素赋值给end坐标，然后让end–，开始从右向左检索
- 重复 4、5 操作直到begin==end
- 最后找到的轴点下标就是begin
代码实现
package 排序算法;
public class 快速排序 {
public static void main(String[] args) {
int[] arr = {0,9,8,6,5,7,3,1,2,4,0,10,11,12,13,15};
System.out.println("排序前：");
for(int i: arr){
System.out.print(i+" ");
}
sort(arr, 0, arr.length-1);
System.out.println();
System.out.println("排序后：");
for(int i: arr){
System.out.print(i+" ");
}
}
// 核心逻辑
public static void sort(int[] arr, int begin, int end) {
if (end - begin <= 0) return; // 终止条件是，序列只剩下一个元素
// 确定轴点的位置
int mid = pivotIndex(arr, begin, end);
// 对子序列进行排序
sort(arr, begin, mid-1);
sort(arr, mid+1, end);
}
// 找到中心轴
public static int pivotIndex(int[] arr, int begin, int end) {
// 备份begin下标的元素，作为中心轴元素
int pivot = arr[begin];
while (beginpivot) { // 如果begin
堆排序
有待总结。。。
桶排序
动画排序过程
概述
桶排序（Bucket sort）或所谓的箱排序，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来既得到有序序列。
思想：
桶排序采用的是分治的思想
桶排序假设待排序的一组数均匀独立的分布在一个范围中，并将这一范围划分成几个子范围（桶）。
然后基于某种映射函数f ，将待排序列的关键字 k 映射到第i个桶中 (即桶数组B 的下标i) ，那么该关键字k 就作为 B[i]中的元素
接着将各个桶中的数据有序的合并起来 : 对每个桶B[i] 中的所有元素进行比较排序 (插入、快速、归并排序都可以)。然后依次枚举输出 B[0]….B[M] 中的全部内容即是一个有序序列。
注意：
- 尽可能保证最后的数据均匀分布在桶中，与你的映射函数f(重要的一步)有关
- 理论上区分区间越小，即桶分的越多，整体时间复杂度越接近于线性，但对应的空间复杂度就大了(空间换时间)。当区间只有一个大小，就变成相当于计数排序了
- 时间复杂度也和每个桶用的排序算法有关
执行流程
- 创建桶
- 将数据根据映射函数放到对应的桶中，并保持有序
- 然后再按顺序将数据取出
代码实现
桶排序最重要的是它里面分治思想。这里代码我就举一个简单的例子，输入0-99之间的随机整数，0-9放入0号桶，10-19放到1号桶，20-29放入2号桶…以此类推
import java.util.ArrayList;
import java.util.List;
public class 桶排序 {
public static void main(String[] args) {
int[] arr = new int[100];
for (int i=0; i<100; i++) arr[i] = (int)(Math.random()*100);
System.out.println("排序前的数据：");
for (int i=0; i> buckets = new ArrayList<>();
for (int i=0; i());
}
// 将数组的每个数据都放入到对应的桶中，并保证桶内数据有序
for (int i=0; i bucket, int data) {
bucket.add(data);
int cur = bucket.size()-1; // 当前数据的下标
while (cur-1>=0 && bucket.get(cur-1)>data) { // 如果当前数据小于前面那个数据
bucket.set(cur, bucket.get(cur-1)); // 前面那个数据后移
cur--; // 当前下标前移
}
bucket.set(cur, data); // 将数据插入到合适的位置
}
}
这里因为每个桶的大小是不确定的，因此每个桶容器我使用的是一个ArrayList集合来表示。
里面每个桶的排序算法我使用的是插入排序算法，不熟悉插入排序的话可以看看上面总结的插入排序。
总结
桶排序中很重要的一步就是桶的设定了，我们必须根据输入元素的情况，使得输入元素能够正确的放入对应的桶内，且保证输入数据能够尽量均匀的放入不同的桶内。
其次，我们可以发现，区间划分的越细，即桶的数量越多，理论上分到每个桶中的元素就越少，桶内数据的排序就越简单，其时间复杂度就越接近于线性。
极端情况下，就是区间小到只有1，即桶内只存放一种元素，桶内的元素不再需要排序，因为它们都是相同的元素，这时桶排序差不多就和计数排序一样了。
借鉴的优秀博文
https://blog.csdn.net/l_ppp/article/details/108855298
https://blog.csdn.net/meibenxiang/article/details/92796909
