【数据结构-之八大排序(下)，冒泡排序，快速排序，挖坑法，归并排序】

🌈个人主页：努力学编程’

⛅个人推荐：基于java提供的ArrayList实现的扑克牌游戏 |C贪吃蛇详解

⚡学好数据结构，刷题刻不容缓：点击一起刷题

🌙心灵鸡汤：总有人要赢，为什么不能是我呢

hello,这里提前祝大家五一快乐，每天都能快快乐乐，并且每天都能学到东西。

我们今天继续顺着上次没有说完的排序算法，这里简单复习一下，我们根据每种排序的方式不同，大致上将常见的排序算法分为选择排序，插入排序，交换排序，归并排序。今天就大家学习我们剩下的两个大类，交换排序和归并排序。

🌈交换排序

⚡冒泡排序

冒泡排序算法的原理如下：

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤，除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

这里也给大家一个动图，帮助大家理解：

public static void bubbleSort(int[] array) {
        for (int i = 0; i  array[j+1]) {
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            
            //时间复杂度为：O(N)
            if(!flg) {
                break;
            }
        }
    }

总体来说呢，冒泡排序是这几种排序中最简单的一种排序，容易理解，代码的逻辑也没有那么复杂，唯一需要提醒大家的，就是两个for循环里面的循环结束条件的判断，这里需要着重强调！！！

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：稳定

⚡快速排序

概念：快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int[] array, int left, int right)
{
if(right - left 
        int i = left;
        int tmp = array[left];
        while (left = tmp) {
                right--;
            }
            while (left 
            return;
        }
        int mid = (right+left) / 2;
        mergeSortFun(array,left,mid);
        mergeSortFun(array,mid+1,right);
        //合并
        merge(array,left,mid,right);
    }
    private static void merge(int[] array,int left,
                              int mid,int right) {
        //这里申请一块新的数组 存放排好序元素
        int[] tmp = new int[right-left+1];
        int k = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        //定义整个存放元素过程的限制条件
        while (s1 
            if(array[s1] 
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }
        //走到这里，可能是左边的数组已经排完了  
        //我们就把右边所有的元素是直接放到数组当中
        //当右边已经拍完之后，
        //我们需要将左边还剩的元素直接放到数组当中。
        while (s1 
            tmp[k++] = array[s1++];
        }
        while (s2 
            tmp[k++] = array[s2++];
        }
        //走到这里 相当于tmp数组 当中 所有的元素 都有序了
        //接下来把tmp数组的内容 拷贝到array数组当中
        for (int i = 0; i