[数据结构与算法]【七大排序算法】插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序、归并排序

• 所谓排序，就是把一堆杂乱的数据，排成升序或降序(递增/增减)。

• 排序稳定性： 假设一组数据[1,2,9,5,5,6,8]，进行升序排序后，两个5的相应位置不发生改变，即称为稳定的排序，否则就是不稳定排序。
  

• 内部排序： 数据元素全部放在内存中进行排序。

• 外部排序： 即将待排序的记录存储在外存中，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间地交换。

1. 插入排序

思路：

1. 默认为第一个元素自己是有序的，从第二个元素开始。
2. 取出第二个元素tmp，往前进行比较。
3. 若该元素比tmp大，则将该元素往后移一位，直到找到比tmp小的。
4. 找到比tmp小于等于的元素后，tmp插入到该元素的下一位。
5. 循环2~4步骤。

步骤具体实现：

1. 定义下标 i ，遍历数组。默认 i 下标已经是有序的，把i下标元素存入tmp。
2. 定义 j，j 从 i-1 的位置，开始向前遍历，遇到比 tmp大的元素，就把此时j下标的元素往后移一位，直到下标等于或小于0停止。
3. j下标元素小于tmp，则把tmp元素插入该j下标的下一个位置。

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

空间复杂度： O(1);

稳定性： 稳定；

具体代码实现：

    public static void insertSort(int[] array){
        //1.遍历数组
        for (int i = 0; i < array.length; i++) {
            int tmp = array[i];
            //2.往前遍历，进行插入
            int j = i-1;
            for ( ;j >=0 ; j--) {
                if(array[j] > tmp){
                    int exchange  = array[j];
                    array[j+1] = array[j];
                    array[j] = exchange;
                }else{
                    //没有比tmp小的，退出循环
                    break;
                }
            }
            //3.此时j下标元素比tmp小，tmp插入j下标的下一个位置
            array[j+1] = tmp;
        }
    }

结论：

1. 当数据趋于有序时，排序时间越快，最好的情况下时间复杂度为O(N);
2. 当把循环中 array[j] > tmp的大于号改为大于等于，此时就不是稳定的排序了。

2. 希尔排序

思路：

1. 先将待排序列进行预排序，使得待排序列接近有序，此时进行插入排序。
2. 把待排序的数据分为多个组，每组间隔为5或3…。
3. 若此组的第一个元素大于最后一个元素，将此组第一个元素和最后一个元素交换。
4. 重复上述操作，直到每组间隔只有1时，所有数据都在统一组内进行排好序。

步骤具体实现：

1. 定义gap = 数组长度\2。
2. 把待排序列分为gap个组，每个组的第一个元素和最后一个元素进行比较交换。
3. 重复上述操作
4. 当gap为1时，进行插入排序。

时间复杂度： O(N^1.3);

空间复杂度： O(1);

稳定性： 不稳定。

具体代码实现：

 public static void shell(int[] array){
        int gap = array.length;
        while(gap > 1){
            gap /= 2;//分组
            //1.每组头和尾进行比较交换
            for (int i = 0; i < array.length; i++) {
                int tmp = array[i];
                //2.往前遍历，一次步长为gap
                int j = i-gap;
                for ( ;j >=0 ; j-=gap) {
                    if(array[j] > tmp){
                        int exchange  = array[j];
                        array[j+gap] = array[j];
                        array[j] = exchange;
                    }else{
                        break;
                    }
                }
                array[j+gap] = tmp;
            }

        }
    }

结论：

1. 希尔排序是对插入排序的优化。

2. 当gap>1时，都是预排序，目的是为了让数组更趋于有序，当gap==1时，数组已经接近有序，这样进行插入排序就会很快。

3. 希尔排序的时间复杂度不容易计算，因为gap的取值方法很多，导致很难计算，因此我们按照Knuth提出的时间复杂度O(N^1.3)来算。

3. 选择排序

思路：

每次从待排序列中选择一个最小值(最大),存放在序列的起始位置，直到全部待排序的数据排完。

步骤具体实现：

1. 定义i，假设待排序列i下标元素是最小值，用min记录当前i下标。

2. 定义j，从i下一个位置开始往后遍历，遇到小于array[min]时更新min，min指向每次遍历的最小值下标，直到遍历完一次数组。

3. 一次遍历完后array[i]和min下标进行交换。

4. 重复上述操作，直到待排序数据剩余1个元素。

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

空间复杂度: O(1);

稳定性： 不稳定；

具体代码实现：

    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int min = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[min]){
                    //更新min的值
                    min = j;
                }
            }
            if(min != i){
                int tmp = array[i];
                array[i] = array[min];
                array[min] = tmp;
            }

        }
    }

结论： 效率不是很好，实际中很少使用。

4. 堆排序

注意：排升序需要建大根堆，排降序建小根堆。 此文章默认举例排升序。

思路&具体步骤实现：

1. 首先得建立一个大根堆。

2. 把根节点与最后一个节点交换，每一次交换，最后一个节点向前走一步。

3. 进行堆向下调整。

时间复杂度： O(N*logN)；

空间复杂度： O(1);

稳定性： 不稳定；

具体代码实现：

    public static void heapSort(int[] array){
        //0.创建大根堆
        createHeap(array);// 时间 O(N)
        int end = array.length-1;
        while (end > 0){
            //1.每次根和最后一个节点交换
            int tmp = array[0];
            array[0] = array[end];
            array[end] = tmp;
            //2.向下调整 
            shiftDown(array,0,end);
            //3.最后一个节点已经是有升序的了
            end--;
        }
    }
    private static void createHeap(int[] array){
        //(array.length-1-1)->减一个1是数组下标是从0开始的，
        //减两个1是二叉树的概念：已知孩子节点求父亲节点 ->(i-1)/2
        for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
                //向下调整
                shiftDown(array,parent,array.length);
        }
    }
    private static void shiftDown(int[] array,int parent,int len){
        int child = (parent*2)+1;
        while(child < len){
            if(child+1 < len && array[child+1] > array[child]){
                child++;
            }
            if(array[child] > array[parent]){
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
                //继续向下调整
                parent = child;
                child = (parent*2)+1;
            }else {
                break;
            }
        }
    }

5. 冒泡排序

思路： 根据序列中的两个记录键值比较结果来交换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的向前部移动。

具体步骤实现：

1. 定义i遍历数组，控制趟数，总体趟数比数组长度少1；
2. 每趟让一个较大值移动到尾部。
3. 定义j每次从0下标进行两两比较交换。

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

空间复杂度： O(1)；

稳定性： 稳定；

具体代码实现：此处冒泡排序代码作了优化。

    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean  flag = false;//判断此趟排序有没有交换
            for (int j = 0; j < array.length-1-i; j++) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    flag = true;
                }
            }
            //若flag一趟下来为false 说明数组已经有序
            if(flag == false){
                break;
            }
        }
    }

6.快速排序

基本思想：任取待排序元素中的某元素作为基准值，将待排序集合分割为两子序，左子序中所有元素均小于 基准值，右子序均大于 基准值，然后左右子序重复该过程，直到所有元素都排列在相应位置上。

6.1 Hoare版

思路：

1. 取数组最左边或最右边为key。
2. 先从右边开始找到小于key值。
3. 再从左边走找到大于key值，左右进行交换。
4. 左右相遇后，相遇点为此次遍历的基准值
5. 最后与key位置交换。

具体实现步骤：

1. 定义key，指向数组最左边的元素。

2. 定义left从数组左边开始遍历；定义right从右边开始遍历。

3. 一定要right先走，再走left。

4. 当right和left相遇后，与key交换，相遇点为基准值。

5. 遍历以该基准值分割的两子序。

6. 递归重复上述操作。

具体代码实现：

    public static void quickSort(int[] array){
        quickHelp(array,0,array.length-1);
    }

    //具体实现排序调用函数
    private static void quickHelp(int[] array,int start,int end){
        if (start >= end){
            return;
        }
        //1.找基准值
        int pivot = hoare(array,start,end);
        //2.左右子序重复该操作
        quickHelp(array,start,pivot-1);
        quickHelp(array,pivot+1,end);
    }
    private static int hoare(int[] array,int left ,int right){

        int index = left;//记录key下标
        int key = array[left];
        while(left < right){
            //1.先从右 找到比key小的值
            while(left < right && array[right] >= key){
                right--;
            }
            //2.再从左找到比key大的值
            while(left < right && array[left] <= key){
                left++;
            }
            //3.交换左右值
            int tmp = array[left];
            array[left]  = array[right];
            array[right] = tmp;
        }
        //4.相遇点和key下标交换
        int tmp = array[left];
        array[left]  = array[index];
        array[index] = tmp;
        return left;
    }

代码优化：

此排序，递归下去就好像一颗二叉树，当排序的是有序时，就只有左子树或者只有右子树，此时排序的时间复杂度最高，所有：在找基准值先，尽量让左右子树划分平衡。当递归到一定层数是进行插入排序，因为越往下层遍历，这一层的递归次数越多，比如第一层递归2次，第二次递归4次…。

步骤：

1. 设定一个边界值，达到边界值时进行插入排序。

2. 保证每次划分均匀：（3个数找中数）

   如待排序：1 2 3 4 5 把1和3和5进行比较，找出中间值，把最左边值和中间值交换。

具体代码实现：

    public static void quickSort(int[] array){
        quickHelp(array,0,array.length-1);
    }

    //具体实现排序调用函数
    private static void quickHelp(int[] array,int start,int end){
        if (start >= end){
            return;
        }
        //对start - end 区间进行插入排序
        if(start <= 15){
            insertSortHelp(array,start,end);
        }
        //在找基准前尽量保证左右划分均匀
        int index = findMin(array,start,end);
        swap(array,start,index);

        //1.找基准值
        int pivot = hoare(array,start,end);
        //2.左右子序重复该操作
        quickHelp(array,start,pivot-1);
        quickHelp(array,pivot+1,end);
    }
    public static void insertSortHelp(int[] array,int left,int right){
        for (int i = left; i <= right; i++) {
            int tmp = array[i];
            int j = i-1;
            for ( ;j >=0 ; j--) {
                if(array[j] > tmp){
                    swap(array,j,j+1);
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    private static int findMin(int[] array,int left,int right){
        int midIndex = (left+right)/2;

        if(array[left] < array[right]){
            if(array[left] > array[midIndex]){
                return left;
            }else if(array[right] < array[midIndex]){
                return right;
            }else {
                return midIndex;
            }
        }else{//array[left] > array[right]
            if(array[left] < array[midIndex]){
                return left;
            }else if(array[right] > array[midIndex]){
                return right;
            }else {
                return midIndex;
            }
        }
    }
    private static int hoare(int[] array,int left ,int right){

        int index = left;//记录key下标
        int key = array[left];
        while(left < right){
            //1.先从右 找到比key小的值
            while(left < right && array[right] >= key){
                right--;
            }
            //2.再从左找到比key大的值
            while(left < right && array[left] <= key){
                left++;
            }
            //3.交换左右值
            swap(array,left,right);
        }
        //4.相遇点和key下标交换
       swap(array,left,index);
        return left;
    }
    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

6.2 挖坑法

思路：

大致思路根Hoare版本类似；

1. 选最左边的元素存入key，在此位置形成一个坑位；
2. 先从右开始遍历和key比较，再从左遍历，进行左右交换。
3. 左右相交后，把key的放入相交点位置。

具体实现步骤：

1. 先将第一个元素存入临时变量key，形成一个坑位。
2. 定义left从数组左边开始走、right从右边开始走。
3. 先从右开始遍历找到比key小的元素，放入left的位置；
4. 然后left找到比key大的元素，放入right的位置。
5. 待left和right下标相遇后，把key的元素放入相交点。
6. 重复上述操作。

具体代码实现【递归】：

    public static void digSort(int[] array,int start ,int end){
       if(start >= end){
           return;
       }
       int left = start;
       int right = end;
       int key = array[left];
       while(left < right){
           //1.先从右开始 找到比key小的
           while (left < right && array[right] >= key){
               right--;
           }
           //2.把小值填入左边的坑位
           array[left] = array[right];

           //3.再从左开始 找到比key大的
           while (left < right && array[left] <= key){
               left++;
           }
           //4.把大值填入右边的坑位
           array[right] = array[left];
       }
       array[left] = key;
       //递归
        digSort(array,start,left-1);//遍历key左边
        digSort(array,left+1,end);//遍历key右边
    }

6.3 前后指针法

了解即可，见得比较少，整体思路大体一样。

1. 定义key存储数组起始元素，prev指向数组开始位置；cur指prev后一个位置。
2. 当cur下标元素小于key，prev向后走，并且此时prev下标的元素不等于cur下标元素，则进行交换
3. 否则cur一直往后走，当cur走完时，prev下标和数组最左边左边下标交换。
4. 递归重复上述操作。

    public static void quick(int[] array,int start,int end){
        if(start >= end){
            return;
        }
        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
   private static int partition(int[] array, int left, int right) {
        int prev = left ;
        int cur = left+1;
        while (cur <= right) {
            if(array[cur] < array[left] && array[++prev] != array[left]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }

6.4 快速排序非递归

思路：使用栈，模拟递归

1. 先找到基准
2. 判断基准左右是否存在两个元素及以上。
3. 把以基准为界左边的数组最左边下标和最右边下标入栈
4. 再基准右边的数组最左边下标和最右边下标入栈
5. 弹出栈顶两个下标，对此下标区间再进行找基准【弹出顺序：先右后左】
6. 重复上述操作。
7. 快速排序非递归最重要的就是找基准。

具体代码实现：

    public static void quickSort2(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        //找基准
        int pivot = finMid(array,left,right);//排序核心代码
        //1.判断基准左边有没有2个元素    1   2    3    4    5    9
        if(pivot > left+1){       //若基准：3    left:1    pivot < left+1
            //把最左边和最右边的下标入栈
            stack.push(left);
            stack.push(pivot-1);
        }
        //2.判断基准右边有没有2个元素
        if(pivot < right-1){
            //把最左边和最右边的下标入栈
            stack.push(pivot+1);
            stack.push(right);
        }
        //3.弹出2个元素，重复上述操作
        while(!stack.isEmpty()){
            //注意弹出顺序：先右和左
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array,left,right);

            if(pivot > left+1){
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot < right-1){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }
 private static int finMid(int[] array,int left ,int right){

        int index = left;//记录key下标
        int key = array[left];
        while(left < right){
            //1.先从右 找到比key小的值
            while(left < right && array[right] >= key){
                right--;
            }
            //2.再从左找到比key大的值
            while(left < right && array[left] <= key){
                left++;
            }
            //3.交换左右值
            swap(array,left,right);
        }
        //4.相遇点和key下标交换
       swap(array,left,index);
        return left;
    }

快速排序总结：

1. 综合性能和使用场景比较好。
2. 一般快速排序三种方法使用顺序：挖坑法->Hoare法->前后指针法

7. 归并排序

核心思想：分而治之

即：将待排序列拆分，再合并成为有序序列。

• 先把序列逐层进行拆分：

• 当拆分到只有一个元素时，再从下往上逐层合并，首先对第一层序列号1(元素4)，和序列号2(元素5)进行合并

1.创建一个大数组，长度为序列号1和序列号2长度之和，s1、s2指针分别指向两个小序列号(数组)的第一个元素，ret指向大数组的第一个元素。【两个有序数组合并为一个数组】

2.比较[s1]、[s2]指向的元素，4<5，将4放入ret指向的空间，ret往右走一步，s1往右走一步。

3.此时序列号1(数组)已经没有元素，直接将序列号2的元素放入大数组中。

4.[8]和[1]、[7]和[2]、[6]和[3]，用同样方式进行合并。

5.以[4,5]为序列1，[1,8]为序列2，继续进行合并。

6.[4]和[1]比较，4>1，把[1]放入ret指向的空间，[s2]往右走一步。

7.重复上述操作，直到把[4,5]和[1,8]合并成【1,4,5,8】。

以[2,7]为序列3，[3,6]为序列4，用同样的方式合并成为新的序列【2,3,6,7】；

8.最后将[1,4,5,8]和[2,3,6,7]用同样的方式合并成新的序列

时间复杂度：O(N*logN) ： 归并排序算法每次将序列折半分组，共需要logN轮。

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

稳定性：稳定

具体代码实现：

 public static void merge(int[] array,int start,int end){
        if(start >= end){
            return;
        }
        //1.分解
        int mid = (start+end)/2;//折半递归
        merge(array,start,mid);
        merge(array,mid+1,end);
        //2.合并 合并两个小数组为一个大数组
        mergeHelp(array,start,mid,end);
    }
    private static void mergeHelp(int[] array,int left,int mid,int right){
            //这里直接合并[4,5]和[1,8],因为[4]和[5]两个数组太小了，不好理解
        //第一个小数组下标范围
        int s1 = left;
        int e1 = mid;
        //第二个小数组下标范围
        int s2 = mid+1;
        int e2 = right;
        //合并的大数组
        int[] ret = new int[right-left+1];
        int k = 0;//ret下标
        while(s1 <= e1 && s2 <= e2){
            //进行比较
            if( array[s1] <= array[s2]){
                ret[k++] = array[s1++];
            } else{
                ret[k++] = array[s2++];
            }
        }
        //存放剩余的有序元素
        while(s1 <= e1){
            ret[k++] = array[s1++];
        }
        while(s2 <= e2){
            ret[k++] = array[s2++];
        }
        //把合并完的有序元素，放入原来的数组里->所有归并排序空间复杂度高
        for (int i = 0; i < k; i++) {
            //+left 因为每次合并ret存的元素对应的array下标在发生变化
            //若存入给ret的 5 6 7 8 对应原数组下标为 4 5 6 7
            //那+left(4)，刚好存入原数组正确的位置
            array[i+left] = ret[i];
        }
    }

非递归版本：【模拟递归】

    public static void mergerSort(int[] array){
        int gap = 1;//模拟递归到每组序列只有一个元素
        while(gap < array.length){
            //合并
            for (int i = 0; i < array.length; i+= 2*gap) {
                int left = i;
                int mid = left+gap-1;
                //判断越界
                if(mid >= array.length){
                    mid = array.length-1;
                }
                int right = mid+gap;
                //判断越界
                if(right >= array.length){
                     right = array.length-1;
                }
                mergeHelp(array,left,mid,right);
            }
            gap *= 2;
        }
    }
        private static void mergeHelp(int[] array,int left,int mid,int right){
        //第一个小数组下标范围
        int s1 = left;
        int e1 = mid;
        //第二个小数组下标范围
        int s2 = mid+1;
        int e2 = right;
        //合并的大数组
        int[] ret = new int[right-left+1];
        int k = 0;//ret下标
        while(s1 <= e1 && s2 <= e2){
            //进行比较
            if( array[s1] <= array[s2]){
                ret[k++] = array[s1++];
            } else{
                ret[k++] = array[s2++];
            }
        }
        //存放剩余的有序元素
        while(s1 <= e1){
            ret[k++] = array[s1++];
        }
        while(s2 <= e2){
            ret[k++] = array[s2++];
        }
        for (int i = 0; i < k; i++) {
            array[i+left] = ret[i];
        }
    }

总结：

1. 归并的缺点是需要O(N)的空间复杂度。
2. 归并排序的思想更多是在解决磁盘中的外排序问题。

8. 排序算法复杂度及稳定性分析