七大排序 | 快排详解 | 比较型排序总结

深藏阁楼爱情的钟 2024-03-26 15:43 35阅读 0赞

![d520e060cacefc15815e2cd7ecda6795.png][]

--------------------

## **比较型排序** ##

### **1.直接插入排序** ###

当插入第i(i>=1)个元素时，前面的array\[0\],array\[1\],…,array\[i-1\]已经排好序，此时用array\[i\]的排序码与array\[i-1\],array\[i-2\],…的排序码顺序进行比较，找到插入位置即将array\[i\]插入，原来位置上的元素顺序后移

/**
     *时间复杂度最差情况O(N^2)
     *           最好情况O(N)
     *               当数据趋于有序的时候，排序速度会非常快
     *                   一般场景就是数据基本有序，建议直接使用直接插入排序
     * 空间复杂度：O(1)
     * 稳定性:稳定
     * 如果一个排序是稳定的 那么就可以实现为不稳定 这里直接 array[j] >= tmp 就会变得不稳定
     * @param array
     */
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            //从后往前排
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    //这时候就说明前面的数都会比tmp小(前面已经有序)
                    //节省时间效率
                    break;
                }
            }
            //break跳到的语句或者当前最小的数(全部排序了一遍)
            array[j + 1] = tmp;
        }
    }

#### **直接插入排序特性总结:** ####

1.  元素集合越接近有序，直接插入排序算法的时间效率越高

1.  时间复杂度：O(N^2) ,最好情况 O(N)

1.  空间复杂度：O(1)，它是一种稳定的排序算法

1.  稳定性：稳定

--------------------

### **2.希尔排序(缩小增量排序)** ###

希尔排序法又称缩小增量法。希尔排序法的基本思想是：**先选定一个整数，把待排序文件中所有记录分成多个组， 所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序**。

![b9a558317e3b57da7e24939886ab2cc4.png][]

**其实就是直接插入排序的一种优化,每一次都是进行了快排,只是增量为gap**

//待排序数组越有序 插入排序越快
    /**
     * 时间复杂度O(N^1.3) ~ O(N^1.5)
     * 空间复杂度O(1)
     * 稳定性: 不稳定
     * 相当于对直接插入排序进行优化
     * @param array
     */
    public static void shellSort(int[] array) {
        int gap = array.length;
        //当gap > 1的时候不断进行分组排序
        //分组逐渐变少
        while (gap > 1) {
            gap /= 2;
            //gap组数据 每组数据n/gap
            //gap为其他组的时候是预排序
            //只有当gap == 1 的时候 才是直接排序
            shell(array, gap);
        }
        //整体进行插入排序
    }
    private static void shell(int[] array, int gap) {
        //这里是i ++ 因为是间隔性的插入排序 (第一组没排序完排第二组)...
        for (int i = gap; i < array.length; i++) {
            //从后往前排
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    //往后挪
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

#### **希尔排序的特性总结：** ####

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

1.  当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

1.  希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排 序的时间复杂度都不固定：

--------------------

### **3.选择排序** ###

在元素集合array\[i\]--array\[n-1\]中选择关键码最大(小)的数据元素

若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换

在剩余的array\[i\]--array\[n-2\]（array\[i+1\]--array\[n-1\]）集合中，重复上述步骤，直到集合剩余1个元素

/**
     * 时间复杂度O(N^2)
     * 空间复杂度O(1)
     * 稳定性:不稳定
     * @param array
     */
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            //定义最小下标是i i后面都是待排序数组
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            swap(array, minIndex, i);
        }
    }
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

#### **直接选择排序的特性总结:** ####

1.  直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

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

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

1.  稳定性：不稳定

--------------------

### **4.堆排序** ###

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆 来进行选择数据。**需要注意的是排升序要建大堆，排降序建小堆**

![2cf647bc56b0a337419467e82ec888ac.png][]

![a67e716340e13b918b9c0d2943da0c80.png][]

//建堆
    public static void createHeap(int [] array){
        for (int parent  = (array.length -1-1) / 2 ; parent  >= 0 ; parent --) {
            shiftDown(array,parent,array.length);
        }
    }
    /**
     * 堆排序
     * 时间复杂度O(n * log N) | 空间复杂度 O(1)
     * 稳定度:稳定
     * @param array
     */
    public static void heapSort(int [] array){
        //1.先要获得一个大根堆 每次根节点跟最后一个互换
        createHeap(array);
        int end = array.length -1;
        while (end > 0) {
            swap(array,0,end);
            shiftDown(array,0,end);
            end --;
        }
    }
    private static void shiftDown(int [] array, int parent, int len){
        int child = parent * 2 + 1;
        while (child < len){
            //这里确保存在右孩子 才可以进行比较
            if(child + 1 < len && 
                    array[child] < array[child + 1] ){
                //右孩子大一些
                child ++;
            }
            if(array[child] > array[parent]){
                swap(array, child, parent);
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }
    }
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

#### **堆排序的特性总结:** ####

1.  堆排序使用堆来选数，效率就高了很多。

1.  时间复杂度：O(N\*logN)

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

1.  稳定性：不稳定

--------------------

### **5.冒泡排序** ###

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

/*
     * 冒泡排序
     * 时间复杂度O(n^2)
     * 空间复杂度O(1)
     * */
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    flg = true;
                }
            }
            //说明这趟循环没有改变 就说明已经有序
            if (flg == false) {
                return;
            }
        }
    }
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

#### **冒泡排序的特性总结:** ####

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

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

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

1.  稳定性：稳定

--------------------

### **6.快速排序** ###

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

##### (1)挖坑法 #####

**每次找到一个基准 再从基准划分两边区域然后继续进行寻找基准**

1) 将最左/右值记录下来用tmp表示,定义两边的指针left,right

![caa0c76e345c292bb77a6767343d2f82.png][]

2) **left寻找比tmp大的值,right寻找比tmp小的值 当right找到就覆盖left下标的值,left同理**

![f93c01df930fc0778277acc5629697c7.png][]

![cbdaafbe90eebc57b4fa7bb5f5435ad1.png][]

**3)找到left = right的基准就返回下标值 由此分割成两个数组继续进行找基准**

![b7a37e6615fd20720a10b6663530fabb.png][]

public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }
    private static void quick(int[] array, int start, int end) {
        //终止递归条件
        //大于说明连左边或者右边都没有数据 end 在最左边 或者start 在最右边的情况
        if (start >= end) {
            return;
        }
        /*
        * 优化:
        * 当数据比较少的时候可以使用直接插入排序
        * 主要减少了递归的次数
        * */
        if(end - start + 1 <= 14){
            insertSort2(array,start,end);
            return;
        }
        //优化:三数取中法
        int index = midThree(array,start,end);
        //交换
        swap(array,index,start);
        //划分
        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 tmp = array[left];
        while (left < right) {
            /*
             * 这里相当于left找一次 right 找一次 不断地找*/
            //这里面找tmp右边的值 也就是比tmp大的值
            //这里如果不取等号就会无限循环下去
            while (left < right && array[right] >= tmp) {
                right--;
            }
            /*
             * 出该while循环它有两种可能
             * 1.是 left < right 说明全部排序完成
             * 内层的这个条件是控制寻找范围 外层是终止循环条件
             * 2.是 array[right] >= tmp 那么就说明找到了比tmp大的数字进行互换
             * 但是这只是换了一个值 还需要继续往左边找直到left < right 不成立(外层的while循环)
             * */
            array[left] = array[right];
            while (left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
    
        }
        //left 与 right 相遇  就开始left的值存在现在相遇的位置
        array[left] = tmp;
        return left;
    }

我们会发现 **如果第一次找的基准太大或者太小,数组分开就会不均匀,从而影响排序效率** ,因此引出**三数取中法**找到中间的值做tmp

优化:

\[1\]三数取中

//找到中间下标
    private static int midThree(int[] array,int left,int right){
        int mid = (left + right) /2;
        if(array[left] < array[right]){
            if(array[mid] < array[left]){
                //mid < left < right
                return left;
            }else if(array[mid] > array[right]){
                //left < right < mid
                return right;
            }else {
                return mid;
            }
            //left > right
        }else {
            //left > right > mid
            if(array[mid] < array[right]){
                return right;
            }
            //mid > left > right
            else if(array[mid] > array[left]){
                return left;
            }else  {
                return mid;
            }
        }
    }

\[2\]小数据优化

递归到小的子区间时，**可以考虑使用插入排序 因为在排接近有序,或者小数组序列的时候 直接直接插入排序效率会比快排高**

//辅助快排的直接插入排序
    private static void insertSort2(int[] array,int left,int right) {
        for (int i = left + 1; i < right + 1; i++) {
            //从后往前排
            int tmp = array[i];
            int j = i - 1;
            for (; j >= left; j--) {
                if (array[j] > tmp) {
                    //往后挪
                    array[j + 1] = array[j];
                } else {
                    //array[j+1] = tmp;
                    //这时候就说明前面的数都会比tmp小 因为是排序好的
                    //节省时间效率
                    break;
                }
            }
            //break跳到的语句 或者当前最小的数(全部排序了一遍)
            array[j + 1] = tmp;
        }
    }

##### (2)Hare法 #####

与挖洞法不同的是将right值找到之后不进行覆盖而是找left值两个下标都找到之后再进**交换**

并且需要先找right的下标 然后再找left的下标

此时两种可能

1.left遇见right 说明right已经找到比tmp小的值

2.right遇见left 此时left所指位置一定是一个比tmp小的值(上一次交换的结果)

**因此交换的结果一定是比tmp小的值去了最左边**

public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }
    private static void quick(int[] array, int start, int end) {
        //终止递归条件
        //大于说明连左边或者右边都没有数据 end 在最左边 或者start 在最右边的情况
        if (start >= end) {
            return;
        }
        /*
        * 当数据比较少的时候可以使用直接插入排序
        * 主要减少了递归的次数
        * */
        if(end - start + 1 <= 14){
            insertSort2(array,start,end);
            return;
        }
        三数取中法
        int index = midThree(array,start,end);
        //交换
        swap(array,index,start);
        //划分
        int pivot = partition(array, start, end);
        //左边
        quick(array, start, pivot - 1);
        //右边
        quick(array, pivot + 1, end);
    }
    //--------------------------------------区别------------------------------------------
    public static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        int i = left;
        while (left < right) {
            //需要先走右边再走左边 不然基准大的会换到前面
            while (left < right && array[right] >= tmp) {
                right--;
            }
            while (left < right && array[left] <= tmp) {
                left++;
            }
            //left找到比tmp小的right找到比tmp大的进行交换
            swap(array, left, right);
        }
        //相遇 此时两种可能1.left遇见right 说明right已经找到比tmp小的值 2.right遇见left 此时left所指位置一定是一个比tmp小的值(上一次交换的结果)
        swap(array, left, i);
        return left;
    }

--------------------

##### (3)**快慢指针法** #####

(1)定义一个前驱指针prev和当前所指元素指针Cur

遍历数组,条件\[1\] 当cur指向的元素小于left所指元素

条件\[2\] 判断prev是否为cur的前驱,如果是就不交换

![f9488d6c1644b74cb3998c4ce79f5de1.gif][]

(2)此时满足两个条件 prev和cur内的元素进行**交换**

![08865bc54fb664784be49fdd3a1cd3b9.gif][]

(3)走完数组 将left的值和prev值进行交换,prev所在下标就是找到的基准位置.

![a7ade79cfc48e91f2a5eb3643e12cf70.gif][]

public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }
    private static void quick(int[] array, int start, int end) {
        //终止递归条件
        //大于说明连左边或者右边都没有数据 end 在最左边 或者start 在最右边的情况
        if (start >= end) {
            return;
        }
        /*
        * 当数据比较少的时候可以使用直接插入排序
        * 主要减少了递归的次数
        * */
        if(end - start + 1 <= 14){
            insertSort2(array,start,end);
            return;
        }
        三数取中法
        int index = midThree(array,start,end);
        //交换
        swap(array,index,start);
        //划分
        int pivot = partition(array, start, end);
        //左边
        quick(array, start, pivot - 1);
        //右边
        quick(array, pivot + 1, end);
    }
    //--------------------------------------区别------------------------------------------
    public static int partition(int[]array,int left,int right){
        int prev = left;
        int cur = left + 1;
        //走到尾
        while (cur <= right) {
            //刚开始++prev的位置 == cur 因此不会交换
            //只有当中间出现array[cur] > array[left] 的时候 后面的条件才会成立 可交换
            if(array[cur] < array[left] && array[++prev] != array[cur]){
                swap(array,cur,prev);
            }
            cur ++;
        }
    
        swap(array,prev,left);
        return prev;
    }

拓展:

非递归快速排序

public static void quickSort(int[] array) {
        Deque<Integer> stack = new LinkedList<>();
        int left = 0;
        int right = array.length -1;
        //找一次基准
        int pivoit = partition(array,left,right);
        //左边
        /*left + 1 和 right-1 保证两边存在数据*/
        if(pivoit > left + 1){
            //将left 和 pivot -1 放进去
            stack.push(left);
            stack.push(pivoit -1 );
        }
        //右边
        if(pivoit < right - 1){
            //将 right和 pivot  + 1 放进去
            //顺序不能换 不然后续的代码也需要换
            stack.push(pivoit + 1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            //弹出两个之后找基准
            //只要栈不为空 说明 左右两边都有元素 那么就可以不断的压栈入栈
            //直到pivot两边如果一边只存在一个元素那么就说明 排序完成
            right = stack.pop();
            left = stack.pop();
            pivoit = partition(array,left,right);
            if (pivoit > left + 1) {
                stack.push(left);
                stack.push(pivoit -1);
            }
            if (pivoit < right - 1) {
                stack.push(pivoit + 1);
                stack.push(right);
            }
        }
    }

#### **快速排序总结** ####

1.  快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫**快速**排序

1.  时间复杂度：O(N\*logN)

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

1.  稳定性：不稳定

--------------------

### **7.归并排序** ###

**基本思想**

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使 子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤:

![b6e87511fcfaac98fbb8ce712f0a54f9.png][]

/**
     * 归并排序
     * 时间复杂度N*logN
     * 空间复杂度O(n)
     * 稳定性：稳定
     * @param array
     */
    public static void mergeSort(int [] array){
        mergeSortFunc(array,0,array.length-1);
    }
    private static void mergeSortFunc(int []array,int left,int right ){
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        //分解左边
        mergeSortFunc(array,left,mid );
        //分解右边
        mergeSortFunc(array,mid + 1,right );
        //合并数组
        merge(array,left,right,mid);
    }
    //合并
    private static void merge(int[]array,int start,int end,int mid){
        int s1 = start;
        //int e1 = mid;
        int s2 = mid + 1;
        //int e2 = end;
        //申请一个合并数组
        int [] tmp = new int[end - start + 1];
        int k = 0;// tmp 数组下标
        //说明两个数组都有数据
        //这里有点像合并链表
        while (s1 <= mid && s2 <= end){
             if(array[s1] <= array[s2]){
                 //小的放进tmp里面
                 tmp[k++] = array[s1++];
             }else {
                 tmp[k++] = array[s2++];
             }
        }
        //说明第一个数组存在数据
        while (s1 <= mid) {
            tmp[k++] = array[s1++];
        }
        //第二个存在数据
        while (s2 <= end) {
            tmp[k++] = array[s2++];
        }
        //需要加strat 因为不是所有array都是从0开始
        for (int i = 0; i < tmp.length; i++) {
            array[i + start] = tmp[i];
        }
    }

拓展:

非递归实现归并排序

public static void mergeSort(int [] array){
        int gap = 1;
        while (gap < array.length){
            //从gap == 1 开始合并 每一次 gap * 2
            for (int i = 0; i < array.length; i+= gap*2) {
                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;
                }
                merge(array,left,right,mid);
            }
            //当前为两组有序 下次变成四组有序 ...
    
            gap *=2;
        }
    }

#### **归并排序总结** ####

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

1.  时间复杂度：O(N\*logN)

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

1.  稳定性：稳定

--------------------

### **排序类算法总结** ###

![230917462d274d0e3894764524e591ab.png][]

[d520e060cacefc15815e2cd7ecda6795.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/b45588bfc36244f6a5d6308ce9f630b4.png
[b9a558317e3b57da7e24939886ab2cc4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/18a562e24ed847e083e3bfbe8632573f.png
[2cf647bc56b0a337419467e82ec888ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/e0ddc24bf38d4f3cb141f66f9e5ccd5f.png
[a67e716340e13b918b9c0d2943da0c80.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/27ba660232f84ac99dd95ded308acf91.png
[caa0c76e345c292bb77a6767343d2f82.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/86ccb788e93846eeb59af12f9433d426.png
[f93c01df930fc0778277acc5629697c7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/e936d61839f34fee9e7037058c163ef2.png
[cbdaafbe90eebc57b4fa7bb5f5435ad1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/88c1ee23c9ec46f898362a2abcd6e402.png
[b7a37e6615fd20720a10b6663530fabb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/1d0df06895c94aaa903df327dd63ad60.png
[f9488d6c1644b74cb3998c4ce79f5de1.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/09b37d17aa034d5f8775ce9a77fc6da4.png
[08865bc54fb664784be49fdd3a1cd3b9.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/461d5394164545ca8a480411146099da.png
[a7ade79cfc48e91f2a5eb3643e12cf70.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/e6b6b7b11f4b4758a894adb9859b962d.png
[b6e87511fcfaac98fbb8ce712f0a54f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/161fc23ff4804fcd844ada5c82a0fc15.png
[230917462d274d0e3894764524e591ab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/27c2126eeded43f8a91252718cf29233.png