插入、快排、堆排、归并、计数和桶排序详解以及测试

最新推荐文章于 2023-06-14 18:06:09 发布
最新推荐文章于 2023-06-14 18:06:09 发布
阅读量2.4k 收藏 2
点赞数
分类专栏： 数据结构 java 文章标签： 桶排序 插入排序 快速排序 堆排序 归并排序
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_18297675/article/details/90716912
版权

==> 学习汇总（持续更新）
==> 从零搭建后端基础设施系列（一）-- 背景介绍

一、代码 

package com.example.sort;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Random;

public class Sort {
    public static void main(String[] args) {
        int n = 1000000;
        int BUCKET_COUNT = 1000;
        int bound = n;
        int[] array1 = genRandArray(n, bound);
        int[] array2 = new int[n];
        System.arraycopy(array1, 0, array2, 0, n);
        int[] array3 = new int[n];
        System.arraycopy(array1, 0, array3, 0, n);
        int[] array4 = new int[n];
        System.arraycopy(array1, 0, array4, 0, n);
        int[] array5 = new int[n];
        System.arraycopy(array1, 0, array5, 0, n);
        int[] array6 = new int[n];
        System.arraycopy(array1, 0, array6, 0, n);
        int[] array7 = new int[n];
        System.arraycopy(array1, 0, array7, 0, n);
        int[] array8 = new int[n];
        System.arraycopy(array1, 0, array8, 0, n);
        int[] array9 = new int[n];
        System.arraycopy(array1, 0, array9, 0, n);
        int[] array10 = new int[n];
        System.arraycopy(array1, 0, array10, 0, n);
        int[] array11 = new int[n];
        System.arraycopy(array1, 0, array11, 0, n);

        long b , e;
        //printArray(array1);

        System.out.println("数据量: " + n + ", 桶个数：" + BUCKET_COUNT + ", 数据范围：[0, " + bound + "]\n---------------------");
//        b = System.currentTimeMillis();
//        insertSort(array1);
//        e = System.currentTimeMillis() - b;
//        System.out.println("插入：" + e + " ms");

        b = System.currentTimeMillis();
        quickSort(array2);
        e = System.currentTimeMillis() - b;
        System.out.println("普通快排：" + e + " ms");

        b = System.currentTimeMillis();
        quickSort2(array3);
        e = System.currentTimeMillis() - b;
        System.out.println("基准数随机快排：" + e + " ms");

        b = System.currentTimeMillis();
        quickSort3(array4);
        e = System.currentTimeMillis() - b;
        System.out.println("基准数三取中快排：" + e + " ms");

        b = System.currentTimeMillis();
        heapSort1(array5);
        e = System.currentTimeMillis() - b;
        System.out.println("递归堆排序：" + e + " ms");

//        b = System.currentTimeMillis();
//        heapSort2(array2);
//        e = System.currentTimeMillis();
//        System.out.println(e - b);

        b = System.currentTimeMillis();
        heapSort3(array6);
        e = System.currentTimeMillis() - b;
        System.out.println("循环堆排序：" + e + " ms");

        b = System.currentTimeMillis();
        mergeSort(array7);
        e = System.currentTimeMillis() - b;
        System.out.println("归并排序：" + e + " ms");

        b = System.currentTimeMillis();
        countSort(array8);
        e = System.currentTimeMillis() - b;
        System.out.println("计数排序：" + e + " ms");

        b = System.currentTimeMillis();
        bucketSort(array9, BUCKET_COUNT);
        e = System.currentTimeMillis() - b;
        System.out.println("桶排序(使用TimSort排序桶)：" + e + " ms");

        b = System.currentTimeMillis();
        bucketSort2(array10, BUCKET_COUNT);
        e = System.currentTimeMillis() - b;
        System.out.println("桶排序(使用插入排序桶)：" + e + " ms");

        b = System.currentTimeMillis();
        bucketSort3(array11, BUCKET_COUNT);
        e = System.currentTimeMillis() - b;
        System.out.println("桶排序(使用插入和归并排序桶--自定义数组结构)：" + e + " ms");

        if(checkResult(array2, array3, array4, array5, array6, array7, array8, array9, array10, array11)) {
            System.out.println("结果校验一致");
        } else {
            System.out.println("结果校验错误");
        }
//        printArray(array1);
//        printArray(array2);
//        printArray(array3);
//        printArray(array4);
//        printArray(array5);
//        printArray(array6);
//        printArray(array7);
    }

    /**
     * 插入排序
     * @param array
     */
    public static void insertSort(int[] array){
        /**
         * 假设排序5 7 2 3 4 1 8 6 9 10
         * 我们可以依次从序列的第一个拿出来，从后往前插
         * 第一次：[5] 7 2 3 4 1 8 6 9 10
         * 第二次：[5 7] 2 3 4 1 8 6 9 10
         * 第三次：[2 5 7] 3 4 1 8 6 9 10
         * 第四次：[2 3 5 7] 4 1 8 6 9 10
         * 第五次：[2 3 4 5 7] 1 8 6 9 10
         * 第六次：[1 2 3 4 5 7] 8 6 9 10
         * 第七次：[1 2 3 4 5 7 8] 6 9 10
         * 第八次：[1 2 3 4 5 6 7 8] 9 10
         * 第九次：[1 2 3 4 5 6 7 8 9] 10
         * 第十次：[1 2 3 4 5 6 7 8 9 10]
         *
         */
        int pre, cur;
        for (int i = 1; i < array.length; i++) {
            cur = array[i];     //从数组中拿出第一个未排序的出来
            pre = i -1;         //默认第一个是已经排好序的
            while (pre >=0 && cur < array[pre]){
                array[pre + 1] = array[pre--]; //后移
            }
            //插入
            //就算没有进循环，例如7 > 5，保持原地不动，那么pre+1就是7的位置
            array[pre + 1] = cur; 
        }
    }

    public static void insertSort2(int[] array, int len){
        int pre, cur;
        for (int i = 1; i < len; i++) {
            cur = array[i];     //从数组中拿出第一个未排序的出来
            pre = i -1;         //默认第一个是已经排好序的
            while (pre >=0 && cur < array[pre]){
                array[pre + 1] = array[pre--]; //后移
            }
            //插入
            //就算没有进循环，例如7 > 5，保持原地不动，那么pre+1就是7的位置
            array[pre + 1] = cur; 
        }
    }

    /**
     * 快速排序算法
     * 核心思想：选取数组中的一个值为基准值，将比它小的放到左边，比它大的放到右边，
     *         分成两个子数组，然后子数组按照同样的步骤递归下去即可
     * 例如：5 7 2 3 4 1 8 6 9 10
     * 选取5作为基准数，从后找小于5的数交换，从前找大于5的数交换
     * 第一次：[1] 7 2 3 4 [5] 8 6 9 10
     * 第二次：1 [5] 2 3 4 [7] 8 6 9 10
     * 第三次：1 [4] 2 3 [5] 7 8 6 9 10
     * 经过三次，将数组分为两个子数组[1 4 2 3] 和 [7 8 6 9 10]
     * 选取1作为基准数
     * 第四次：[1] 和 [4 2 3]
     * 选取4作为基准数
     * 第五次：[3 2] 和 [4]
     * 选取3作为基准数
     * 第六次：[2 3]
     * 选取7作为基准数
     * 第七次：[6 8] 和 [9 10]
     * 结束
     * @param array
     */
    public static void quickSort(int[] array){
        quickSort(array, 0, array.length);
    }

    public static void quickSort(int[] array, int left, int right){
        if(left < right) {
            int mid = partition(array, left, right);
            quickSort(array, left, mid);
            quickSort(array, mid + 1, right);
        }
    }

    public static void quickSort2(int[] array){
        quickSort2(array, 0, array.length);
    }

    public static void quickSort2(int[] array, int left, int right){
        if(left < right) {
            //从区间[lef, right)随机取一个基准值，并且和left交换
            swap(array, left, (getRandNum(right) % (right - left)) + left);
            int mid = partition(array, left, right);
            quickSort2(array, left, mid);
            quickSort2(array, mid + 1, right);
        }
    }

    public static void quickSort3(int[] array){
        quickSort3(array, 0, array.length);
    }

    public static void quickSort3(int[] array, int left, int right){
        if(left < right) {
            //取区间[left,right)，left，中间，right-1的中间数作为基准值
            swap(array, left, getMidNum(array, left, (left + right) / 2, right-1));
            int mid = partition(array, left, right);
            quickSort3(array, left, mid);
            quickSort3(array, mid + 1, right);
        }
    }

    public static int partition(int[] array, int left, int right){
        int mid = left;
        int i = left, j = right - 1;
        while (i < j) {
            //从后往前找第一个小于基准数的
            while (i < j && array[j] >= array[mid]){
                --j;
            }

            //防止自己和自己交换
            if(i < j){
                mid = swap(array, mid, j);
            }

            //从前往后找第一个大于基准数的
            while (i < j && array[i] <= array[mid]) {
                ++i;
            }

            if(i < j){
                mid = swap(array, mid, i);
            }
        }
        return mid;
    }

    //递归下沉式构建堆
    public static void heapSort1(int[] array){
        //构造大顶堆
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            buildHeadDown(array, array.length, i);
        }

        //堆排序，每循环一次，将root放到数组后面
        for (int i = 0; i < array.length - 1; i++) {
            swap(array, 0, array.length - 1 - i);
            buildHeadDown(array, array.length - 1 - i, 0);
        }
    }

    //递归上浮+下沉构建堆
    public static void heapSort2(int[] array){
        //构造大顶堆
        for (int i = 0; i < array.length; i++) {
            buildHeadUp(array, i + 1, 0);
        }

        //堆排序，每循环一次，将root放到数组后面
        for (int i = 0; i < array.length - 1; i++) {
            swap(array, 0, array.length - 1 - i);
            buildHeadDown(array, array.length - 1 - i, 0);
        }
    }

    //for循环下沉式构建堆
    public static void heapSort3(int[] array){
        //构造大顶堆
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            buildHeadDown2(array, array.length, i);
        }

        //堆排序，每循环一次，将root放到数组后面
        for (int i = 0; i < array.length - 1; i++) {
            swap(array, 0, array.length - 1 - i);
            buildHeadDown2(array, array.length - 1 - i, 0);
        }
    }

    //构建堆，上浮法，效率极差(知道有这么个方法就行了)
    public static void buildHeadUp(int[] array, int end, int root) {
        int lChild = 2 * root + 1, rChild = 2 * root + 2;
        if (root < end && (lChild < end || rChild < end)) {
            if(lChild < end && (2 * lChild + 1) < end){
                buildHeadUp(array, end, lChild);
            }
            if(rChild < end && (rChild < end || rChild < end)){
                buildHeadUp(array, end, rChild);
            }
            if(lChild < end && rChild < end){
                if(array[root] < array[lChild] && array[root] < array[rChild]){
                    swap(array, root, array[lChild] < array[rChild] ? rChild : lChild);
                } else if(array[root] < array[lChild]){
                    swap(array, root, lChild);
                } else if(array[root] < array[rChild]){
                    swap(array, root, rChild);
                }
            } else if(lChild < end){
                if(array[root] < array[lChild]){
                    swap(array, root, lChild);
                }
            } else if(rChild < end) {
                if(array[root] < array[rChild]){
                    swap(array, root, rChild);
                }
            }
        }
    }

    //递归构建堆，下沉法
    public static void buildHeadDown(int[] array, int end, int root) {
        int lChild = 2 * root + 1, rChild = 2 * root + 2;
        //此根节点不是叶节点、并且左右孩子也不是叶节点就可以继续递归下去
        //如果是叶子节点，递归进去，还是什么都不做，直接返回
        if (root < end && (lChild < end || rChild < end)) {
            //该节点有左右孩子
            if(lChild < end && rChild < end && (array[root] < array[lChild] || array[root] < array[rChild])){
                buildHeadDown(array, end, swap(array, root, array[lChild] < array[rChild] ? rChild : lChild));
            } else if(lChild < end && array[root] < array[lChild]){
                //该节点只有左孩子
                buildHeadDown(array, end, swap(array, root, lChild));
            } else if(rChild < end && array[root] < array[rChild]) {
                //该节点只有右孩子
                buildHeadDown(array, end, swap(array, root, rChild));
            }
        }
    }

    //for循环构建堆，下沉法
    public static void buildHeadDown2(int[] array, int end, int root) {
        int lChild = 0, rChild = 0;
        //i一直跟着传进来的root节点
        for (int i = root; i < end && (lChild < end || rChild < end); ) {
            lChild = 2 * i + 1;
            rChild = 2 * i + 2;
            //该节点有左右孩子
            if(lChild < end && rChild < end && (array[i] < array[lChild] || array[i] < array[rChild])){
                i = swap(array, i, array[lChild] < array[rChild] ? rChild : lChild);
            } else if(lChild < end && array[i] < array[lChild]){
                //该节点只有左孩子
                i = swap(array, i, lChild);
            } else if(rChild < end && array[i] < array[rChild]){
                //该节点只有右孩子
                i = swap(array, i, rChild);
            } else {
                break;
            }
        }
    }


    //归并排序
    public static void mergeSort(int[] array){
        if(array == null || array.length == 1){
            return;
        }
        //直接在最外面创建一个大小一样的临时数组，避免递归创建临时数组带来的空间时间损耗
        int[] tmp = new int[array.length];
        mergeSort(array, tmp, 0, array.length - 1);
        tmp = null;
    }

    public static void mergeSort(int[] array, int[] tmp, int left, int right){
        if(left < right){
            //计算拆分中间位置
            int mid = left + (right - left) / 2;
            mergeSort(array, tmp, left, mid);
            mergeSort(array, tmp, mid + 1, right);
            merge(array, tmp, left, mid, right);
        }
    }

    public static void merge(int[] array, int[] tmp, int left, int mid, int right) {
        int i = mid + 1,j = 0 , k = left;
        //两个有序子数组合并
        while (k <= mid && i <= right) {
            tmp[j++] = array[k] < array[i] ? array[k++] : array[i++];
        }
        //如果左子数组有剩余元素，直接加到临时数组即可
        while (k <= mid) {
            tmp[j++] = array[k++];
        }
        //如果左右子数组有剩余元素，直接加到临时数组即可
        while (i <= right) {
            tmp[j++] = array[i++];
        }
        //将排好序的元素，覆盖回去
        for (i = left, j = 0; i <= right; i++) {
            array[i] = tmp[j++];
        }
    }

    //计数排序
    public static void countSort(int[] array){
        //找范围[min, max]
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i = 0; i < array.length; i++) {
            max = array[i] > max ? array[i] : max;
            min = array[i] < min ? array[i] : min;
        }
        //创建桶，个数为max - min + 1
        int[] buckets = new int[max - min + 1];

        //将数放入桶中
        for (int i = 0; i < array.length; i++) {
            //如果数字重复，那么计数累加就好
            buckets[array[i] - min]++;
        }

        //顺序遍历桶则为从小到大排序，逆序遍历则为从大到小排序
        for (int i = 0, j = 0; i < buckets.length; i++) {
            while (buckets[i]-- != 0) {
                array[j++] = i + min;
            }
        }
    }

    //桶排序
    public static void bucketSort(int[] array, int bucketCount){
        //找范围[min, max]
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i = 0; i < array.length; i++) {
            max = array[i] > max ? array[i] : max;
            min = array[i] < min ? array[i] : min;
        }
        //计算桶间间隔
        double size = (max - min + 1) / (double)bucketCount;
        ArrayList<Integer>[] arrayList = new ArrayList[bucketCount];

        //将数放入桶中
        int index;
        for (int i = 0; i < array.length; i++) {
            index = (int)Math.floor((array[i] - min) / size);
            if(arrayList[index] == null) {
                arrayList[index] = new ArrayList<>();
            }
            arrayList[index].add(array[i]);
        }

        //将桶中的数据排序
        for (int i = 0, j = 0; i < bucketCount; i++) {
            if(arrayList[i] == null || arrayList[i].isEmpty()){
                continue;
            }
            if(arrayList[i].size() == 1){
                array[j++] = arrayList[i].get(0);
            } else {
                arrayList[i].sort(new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return o1 - o2;
                    }
                });
                int len = arrayList[i].size();
                for (int k = 0; k < len; k++) {
                    array[j++] = arrayList[i].get(k);
                }
            }
        }
    }

    public static void bucketSort2(int[] array, int bucketCount){
        //找范围[min, max]
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i = 0; i < array.length; i++) {
            max = array[i] > max ? array[i] : max;
            min = array[i] < min ? array[i] : min;
        }
        //计算桶间间隔
        double size = (max - min + 1) / (double)bucketCount;
        ListNode[] arrayList = new ListNode[bucketCount];

        //将数放入桶中
        //使用链表作为桶，插入的时候即时排序
        int index;
        for (int i = 0; i < array.length; i++) {
            index = (int)Math.floor((array[i] - min) / size);
            if(arrayList[index] == null) {
                arrayList[index] = new ListNode(array[i]);
            } else {
                ListNode pre = arrayList[index], cur = arrayList[index];
                if(array[i] == cur.val){
                    arrayList[index].count++;
                    continue;
                }
                if(array[i] < cur.val){
                    ListNode node = new ListNode(array[i]);
                    node.next = pre;
                    arrayList[index] = node;
                    continue;
                }
                while (cur != null){
                    if(array[i] == cur.val){
                        cur.count++;
                        break;
                    }
                    if(array[i] < cur.val || cur.next == null){
                        ListNode node = new ListNode(array[i]);
                        if(array[i] < cur.val){
                            node.next = pre.next;
                            pre.next = node;
                        } else {
                            cur.next = node;
                        }
                        break;
                    }
                    pre = cur;
                    cur = cur.next;
                }
            }
        }

        //遍历
        for (int i = 0, j = 0; i < arrayList.length; i++) {
            while (arrayList[i] != null){
                while (arrayList[i].count-- > 0){
                    array[j++] = arrayList[i].val;
                }
                arrayList[i] = arrayList[i].next;
            }
        }
    }

    public static void bucketSort3(int[] array, int bucketCount){
        //找范围[min, max]
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i = 0; i < array.length; i++) {
            max = array[i] > max ? array[i] : max;
            min = array[i] < min ? array[i] : min;
        }
        //计算桶间间隔
        double size = (max - min + 1) / (double)bucketCount;
        Array[] arrayList = new Array[bucketCount];

        //将数放入桶中
        int index;
        for (int i = 0; i < array.length; i++) {
            index = (int)Math.floor((array[i] - min) / size);
            if(arrayList[index] == null) {
                arrayList[index] = new Array();
            }
            arrayList[index].add(array[i]);
        }

        //将桶中的数据排序
        for (int i = 0, j = 0; i < bucketCount; i++) {
            if(arrayList[i] == null || arrayList[i].isEmpty()){
                continue;
            }
            if(arrayList[i].size() == 1){
                array[j++] = arrayList[i].get(0);
            } else {
                arrayList[i].sort();
                int len = arrayList[i].size();
                for (int k = 0; k < len; k++) {
                    array[j++] = arrayList[i].get(k);
                }
            }
        }
    }

    static class ListNode {
        public int val;
        public int count;
        public ListNode next = null;
        public ListNode(int val) {
            this.val = val;
            this.count = 1;
        }
    }

    public static int swap(int[] array, int pos1, int pos2) {
        if(pos1 < 0 || pos2 < 0 || pos1 >= array.length || pos2 >= array.length){
            throw new RuntimeException("数组越界");
        }
        if(pos1 == pos2) {
            return pos1;
        }
        array[pos1] = array[pos1] ^ array[pos2];
        array[pos2] = array[pos1] ^ array[pos2];
        array[pos1] = array[pos1] ^ array[pos2];
        return pos2;
    }

    public static void printArray(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }

    public static int[] genRandArray(int n, int bound){
        int[] array = new int[n];
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            array[i] = random.nextInt(bound);
        }
        return array;
    }

    public static boolean checkResult(int[] ... arrs){
        for (int i = 1; i < arrs.length; i++) {
            for (int j = 0; j < arrs[0].length; j++) {
                if(arrs[0][j] != arrs[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    public static int getMidNum(int[] array, int a, int b, int c){
       if((array[b] - array[a] >= 0 && array[c] - array[a] <= 0 ) || (array[b] - array[a] <= 0 && array[c] - array[a] >= 0 )) {
            return a;
        } else if((array[a] - array[b] >= 0 && array[c] - array[b] <= 0 ) || (array[a] - array[b] <= 0 && array[c] - array[b] >= 0 )){
            return b;
        } else {
            return c;
        }
    }

    private static Random random = new Random();
    public static int getRandNum(int n){
        return random.nextInt(n);
    }

    static class Array {
        int[] array;
        int size;
        int cap;
        public Array(){
            array = new int[16];
            size = 0;
            this.cap = 16;
        }
        public Array(int cap){
            array = new int[cap];
            size = 0;
            this.cap = cap;
        }

        public void add(int e){
            if(size >= cap){
                reAlloc();
            }
            array[size++] = e;
        }

        public int get(int index){
            return array[index];
        }

        private void reAlloc(){
            if(size >= cap) {
                int[] tmp = new int[cap];
                System.arraycopy(array, 0, tmp, 0, size);
                cap = 2 * cap;
                array = new int[cap];
                System.arraycopy(tmp, 0, array, 0, size);
                tmp = null;
            }
        }
        public void sort(){
            if(size < 10) {
                insertSort2(array, size);
            } else {
                int[] tmp = new int[size];
                mergeSort(array, tmp, 0, size - 1);
            }
        }

        public int size(){
            return size;
        }

        public boolean isEmpty(){
            return size < 1 ;
        }
    }
}

二、核心思想

1.插入排序
  • 从后往前比较
  • 比较的同时将元素往后移
  • 找到要插入的位置时，直接array[i]=val即可
例如：5 7 2 3 4 1 8 6 9 10
第一个元素肯定是已排序的
第一步：从7开始，从后往前比较，7比5大，位置不变
5 7
第二步：2比7小，7往后移（2这个值是已经被拿出来的了，所以可以覆盖2的位置）
5 x 7
x 5 7
2 5 7
第三步：和第二步类似
2 5 x 7
2 x 5 7
2 3 5 7
第四步：同理
……

2.快速排序

  • 找基准值，将数组一分为2，比基准值小的在左边，大的在右边
    • 基准值一般要么在最左边，要么在最右边，假设在左边，那么从右往左找比基准值小的，交换，从左往右找比基准值大的，交换，直到首尾指针相遇
  • 对划分出来的子数组执行同样的操作，直到数组不能划分为止

快速排序可以说是非常简单的一种排序了，就是选择排序的升级版而已。

例如：5 7 2 3 4 1 8 6 9 10
第一步：
选取5为基准值，从右往左找比5小的，交换
[1] 7 2 3 4 [5] 8 6 9 10
从左往右找比5大的，交换
1 [5] 2 3 4 [7] 8 6 9 10
从右往左找比5小的，交换
1 [4] 2 3 [5] 7 8 6 9 10
划分后的两个数组[1 4 2 3 5]和[7  8  6  9 10]
第二步：
选取1为基准值，从右往左找比1小的，找不到，结束
划分后的两个数组[1]和[4 2 3 5]，1不可划分了
第三步：
选取4为基准值，从右往左找比4小的，交换
[3] 2 [4] [5]
从左往右找比4大的，找不到，结束
划分后的两个数组[3 2 4]和[5], 5不可划分了
第四步：
选取3为基准值，从右往左找比3小的，交换
[2] [3] 4
划分后的两个数组[2 3]和[4], 4不可划分了
第五步：
选取2为基准值，从右往左找比2小的，找不到，结束
划分后的两个数组[2]和[3], 2和3都不可划分了
第六步：对[7  8  6  9 10]执行同样的操作
……

3.堆排序

  • 构建堆
    • 将小的数字往下沉，即从根节点开始往下一层层比较
  • 从堆顶拿到最大的元素，放到数组最后
  • 调整堆，重复上述步骤即可
例如：5 7 2 3 4 1 8 6 9 10 下沉法构建堆的过程如下

在这里插入图片描述
排序就是不断从堆顶拿元素，然后再调整的过程，如图
在这里插入图片描述
4.归并排序

  • 将数组一分为二
  • 重复上述步骤，直到数组不可分割
  • 排序、合并
归并排序比较简单，如图：

在这里插入图片描述

5.计数排序

  • 找到数组最小和最大的值（为了节约空间）
  • 创建数组，大小为max - min + 1
  • 将数放入到对应的位置，重复数字个数累加即可，buckets[array[i] - min]++
这种排序是所有排序中最快最快的，因为没有比较，整个过程只是赋值遍历输出而已， 但是空间消耗却是不可控的，容易出现极端情况。 例子如图：

在这里插入图片描述

6.桶排序

  • 找到数组最小和最大的值（为了节约空间）
  • 计算桶间间隔（桶的个数需要人为指定）
  • 将数放入到对应的桶
桶排序其实是计数排序的升级版（ 这个不是我说的，个人感觉桶排序在速度和空间上没啥大优势，快的话，比不上计数排序，空间消耗上，只会比快排和归并多，所以我觉得只适合特定场景应用需要这种排序算法才有优势。）

例子如图：
在这里插入图片描述

三、测试结果

时间单位：ms
1.随机数组测试，范围[0, n]

排序算法n = 1000n = 10000n = 100000n = 1000000n = 10000000
插入排序2171144108900–
普通快速排序13261391577
基准值随机快速排序15131521695
基准值三数取中快速排序03121341501
递归堆排序24202073110
for循环堆排序15262023150
归并排序13171511597
计数排序01423223

2.随机+重复数组测试，范围[0, bound], n = 10000000 固定
当bound <= 1000 时，使用JVM默认的栈大小会栈溢出，需要调大 -Xss10m

排序算法bound = 1000000bound = 100000bound = 10000bound = 1000bound = 100
普通快速排序14341269216214236117685
基准值随机快速排序15821538252514322143182
基准值三数取中快速排序14861392222113937128836
递归堆排序30292942270120011443
for循环堆排序30563024252020221590
归并排序15711518138512151060
计数排序9264464142

3.随机+重复+部分有序数组测试，范围[0, bound], n = 10000000 固定，有序序列长度 = bound

排序算法bound = 10000000bound = 1000000bound = 100000bound = 10000bound = 1000bound = 100
普通快速排序-12401248221815401146420
基准值随机快速排序66512581296234116071151542
基准值三数取中快速排序27511661095212315011154526
递归堆排序127218192266209120201467
for循环堆排序118017622059234319491525
归并排序446519488476586678
计数排序744944414143

4.桶排序测试
计数排序的变量只有n
随机数组测试，范围[0, n]，n = 10000000，桶个数bc为变量

排序算法bc = 10bc = 100bc = 1000bc = 10000bc = 100000bc = 1000000bc = 10000000
计数排序247296231222224237218
桶排序(使用TimSort排序桶)4756393027312784320741838250
桶排序(使用插入排序桶)----1160637931440
桶排序(使用插入和归并排序桶–自定义数组结构)1730151613431310195023873701

随机+重复数组测试，范围[0, bound], n = 10000000 固定，桶个数bc为变量
bound = 1000000

排序算法bc = 10bc = 100bc = 1000bc = 10000bc = 100000bc = 1000000bc = 10000000
计数排序82827789787981
桶排序(使用TimSort排序桶)4779375328022837323139184375
桶排序(使用插入排序桶)---33850420710091927
桶排序(使用插入和归并排序桶–自定义数组结构)1806146013081211168321292543

bound = 100000

排序算法bc = 10bc = 100bc = 1000bc = 10000bc = 100000bc = 1000000bc = 10000000
计数排序63656563636575
桶排序(使用TimSort排序桶)4208347725502510249330473730
桶排序(使用插入排序桶)--814511262094151167
桶排序(使用插入和归并排序桶–自定义数组结构)1527134011341001163420952749

bound = 10000

排序算法bc = 10bc = 100bc = 1000bc = 10000bc = 100000bc = 1000000bc = 10000000
计数排序44434344444542
桶排序(使用TimSort排序桶)3304295724011609181421572345
桶排序(使用插入排序桶)254422842607116160147369
桶排序(使用插入和归并排序桶–自定义数组结构)134212709909438459701537

bound = 1000

排序算法bc = 10bc = 100bc = 1000bc = 10000bc = 100000bc = 1000000bc = 10000000
计数排序43424243434243
桶排序(使用TimSort排序桶)2912245913551388143217051737
桶排序(使用插入排序桶)126238786111111231201
桶排序(使用插入和归并排序桶–自定义数组结构)119811188578348499351020

bound = 100

排序算法bc = 10bc = 100bc = 1000bc = 10000bc = 100000bc = 1000000bc = 10000000
计数排序44444446434546
桶排序(使用TimSort排序桶)1477405426443441457622
桶排序(使用插入排序桶)443110137137141143239
桶排序(使用插入和归并排序桶–自定义数组结构)1091953832769778803920

bound = 10

排序算法bc = 10bc = 100bc = 1000bc = 10000bc = 100000bc = 1000000bc = 10000000
计数排序46444748485345
桶排序(使用TimSort排序桶)650599512474681519738
桶排序(使用插入排序桶)117134151150135208166
桶排序(使用插入和归并排序桶–自定义数组结构)915807866804885859822

四、总结

  • 插入排序核心思想，从后往前插入已排序序列。插入排序适合数据量小的（5 ~ 20）排序，如果该序列是已排序序列，那么使用 插入排序的时间复杂度是O(n)
  • 快速排序的核心思想，基于基准值，划分数组，直到不能划分为止。普通的快速排序 适合元素重复度不高，且随机的序列。关于快排的各种优化，可以参考该博客三种快速排序以及快速排序的优化
  • 堆排序的核心思想，构建堆和调整堆，弄明白堆的构建就明白了如何利用堆来排序。 堆排序一般适合用来求topN问题，因为快速和稳定性和归并排序都比不了。
  • 归并排序的核心思想，递归分割、回溯合并。它几乎适合所有类型的序列，很稳定，唯一 的缺点只是空间复杂度恒定在O(n)。
  • 计数排序的核心思想，利用数组下标计数，例如10这个数，放入数组中，那么a[10]计数+1。它适合元素均匀分布的序列，如果分布太极端，例如10个元素的数组，最小的是0，最大的是10000000，那么就会创建10000000大小的数组，来排序这10个数。
  • 桶排序的核心思想，分桶排序，即将每个数放入到对应范围的桶中，最后每个桶再单独排序，最后遍历数组输出即可。
Algorithm：【算法进阶之路】之算法面试刷题集合—十大经典排序算法(​简单插入排序/希尔排序、选择排序/堆排序、冒泡排序/快速排序、归并排序、计数排序/桶排序/基数排序)动态图文讲解及其代码实现
头部AI社区如有邀博主AI主题演讲请私信—心比天高，仗剑走天涯，保持热爱，奔赴向梦想！低调，专注，谦虚，自律，反思，成长，还算比较正能量的博主，公益免费传播…内心特别想在AI界做出一些可以推进历史进程影响力的技术(兴趣使然，有点小情怀，也有点使命感呀
05-21 4万+
​ Algorithm：【算法进阶之路】之算法面试刷题集合—十大经典排序算法(​简单插入排序/希尔排序、选择排序/堆排序、冒泡排序/快速排序、归并排序、计数排序/桶排序/基数排序)动态图文讲解及其代码实现 目录 相关文章 排序算法思维导图 十大算法复杂度、稳定性比较 十大排序算法 相关文章 DSt：数据结构的简介、最强学习路线(逻辑结构【数组-链表-栈和队列/树-图-哈希】、物理结构【元素/关系】、数据运算【十大排序/四大查找-图三大搜索-树三大遍历】
C++常用的排序算法收藏：冒泡排序、快速排序、插入排序、选择排序、桶排序、归并排序、堆排序、希尔排序、计数排序、基数排序
青少年编程学习指导
03-11 1198
排序算法（十大排序） 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：
快排、归并排序（分治）、堆排序
u013071074的专栏
07-04 1913
（1）快速排序算法以及应用快速排序中划分的思想求数组中第k小的数，最小的前k个数。（2）归并排序算法以及利用归并排序计算数组的逆序对数。（3）堆排序
快排堆排归并
acttell的博客
08-28 268
https://blog.csdn.net/morewindows/article/details/6684558 https://blog.csdn.net/morewindows/article/details/6709644/ https://blog.csdn.net/morewindows/article/details/6678165
排序（快排， 计数排序）
yun1221的专栏 | Smile, open your eyes, love and go on
03-13 843
1. 快排 #include using namespace std; void swap(int *p, int *q) { int temp = *p; *p = *q; *q = temp; } int PARTITION(int A[], int p, int q) { int i=p-1; int r = A[q]; for(int j = p; j <= q-1;j
【Leetcode刷题日记】排序算法-快排与桶排序
qq_42446653的博客
11-21 232
快速排序与桶排序
归并排序和桶排序
所思 所学 我写 我得
05-08 3328
归并排序就是将两个或多个有序表合并成一个有序表的过程。若将两个有序表合并成一个表则称为二路归并。 二路归并过程如下： 首先把待排的每一个元素看成一个有序表。n个元素构成n个有序表。接着两两合并，即第一个表和第二个表合并；第三个表和第四个表合并；.....。依次类推，若最后还剩一个表没有合并(即n为奇数)，则直接进入下一次两路归并。此为一趟归并。然后再两两合并，直到最后合并为一个表结束。 例如
内部排序算法详解：插入、快速、堆、归并与基数排序
包括但不限于计数排序、桶排序、基数排序等，它们通常适用于特定类型的输入数据，如整数范围有限的情况。 现在我们详细讨论一下每种内部排序方法： 1. 插入排序 插入排序的基本思想是将未排序的元素逐个插入到已...
如何根据不同的应用场景选择合适的排序算法？请从Java的角度出发，对冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序、计数排序、桶排序、基数排序和希尔排序的特点进行详细对比。
最新发布
11-12
桶排序适用于数据分布均匀的情况；基数排序适合整数排序，尤其在数值范围较大时；希尔排序是插入排序的改进版，适合有部分有序特性的数组。 通过分析每种排序算法的优缺点和适用场景，你可以根据实际需要选择合适...
Python3十大排序算法详解及实现：冒泡、快速、归并等
本文主要介绍了10种Python3中常用的排序算法，包括快速排序、冒泡排序、桶排序、基数排序、堆排序、希尔排序、归并排序和计数排序，并给出了冒泡排序和快速排序的实例代码。 排序算法是编程中基础且重要的概念，...
排序算法——归并排序和桶排序
weixin_57154303的博客
08-02 2157
读完本文，完全学会归并列和桶排序。可以将其看作是n个有序的子序列，每一个子序列个数为一，然后开始两两合并，这是子序列个数/2(此时，每一个子序列个数为2)，然后再开始两两合并，以此类推，直到所有的数据都在同一个序列内才停止（两两合并指的是两个子序列进行排序合并），基数排序（Radix sort）是将所有数据按照从最低位开始进行排序，也就是按照个位，十位，百位，千位........，而判断需要进行几次排序，则是根据数据中最大位数来...
python-算法与数据结构-DAY_6
soulproficiency的博客
02-28 173
1.快速排序 基本原理 1.首先选出一个值作为中间值，将中间值放旁边，在头尾分别放置两个游标 2.头尾游标通过夹逼，得到中间值所在位置，以次为基准，一分为二，这时左侧为小于中间值的数组，右侧为大于中间值的数组 3.在左右数组分别重复上述步骤，直至排序完成 ...
归并排序，桶排序，计数排序
2201_75943325的博客
06-14 186
主要思路这是一串数字，在一个数组里面。我们可以第一步把数组均分成两个部分，然后假设两个数组有序我们可以创建一个临时数组去使用，（使用临时数组去存放我们的临时排序好的一个范围然后要记得把排序好的这个临时数组内容拷贝回去）从两个数组的开始进行一个一个比较，小的放在前面放进去之后对应的一部分就向后++。我们就要想怎么可以让我们的这个数组有序？是不是可以把左右两个部分再各自当成一个数组去再一次我们什么内容的操作，如果还是没有分到两个数组都只有一个元素为止！！
【算法】快速排序、桶排序
X1qgirl的博客
08-08 368
目录快速排序快排思想如何选择基准数快速排序的4种优化代码桶排序基本思想什么是堆如何调整一个堆为大顶堆？代码 快速排序 简单易懂的一篇博客 快排思想 不断的选定一个基准（pivot），然后把比基准数小的放在基准数的左边，把基准数大的都放在基准数的右边,最终找到了基准在数组中的正确索引位置（分区过程partition）。然后递归的对这两部分记录继续快排，以达到整个序列有序。 第一轮快排： 先选出第一个数作为基准pivot，存到临时空间中，同时这个索引也是low。然后双指针索引low和high。第一次从high往
时间/空间复杂度、冒泡/选择/插入/快速/归并/计数排序
贵有恒，何必三更眠五更起；最无益，只怕一日曝十日寒
08-30 257
时间复杂度 时间复杂度是用来估计算法运行时间的一个式子（单位）——执行的次数 一般来说，时间复杂度高的算法比低的算法快 如何一眼判断时间复杂度 1、循环减半的过程（O(logn)） 2、几次循环就是n的几次方的复杂度（O(nn)） 空间复杂度 程序执行所耗内存空间的大小 1、冒泡排序 拿第一个数与后一个数比，如果大，就挪到后面；如果后面的数大，就开始用这个大的数再往后走，直到比到最...
一个使用快排结合桶排的排序案例
qq_39839075的博客
06-05 202
快排+桶排
快速排序+归并排序+桶排序
qq_41486775的博客
09-22 345
快速排序o(nlogn) 平均时间复杂度o（nlogn），最坏情况下的时间复杂度o（n^2）。 是冒泡排序的改进版，它的每一趟都定位一个基准元素，基准元素的左边的所有元素都比基准元素小，基准元素的右边的所有的元素都比基准元素大。然后对左右两边的元素接着进行递归操作，知道所有的元素都有序。 代码: package com.lhh; import java.util.Arrays; public class QuickSort { public static void main(String[]
【算法】最快最简单的排序——桶排序
热门推荐
Twinkle
06-23 1万+
本文出自 “啊哈磊” 博客，请务必保留此出处 http://ahalei.blog.51cto.com/4767671/1362789 在我们生活的这个世界中到处都是被排序过的。站队的时候会按照身高排序，考试的名次需要按照分数排序，网上购物的时候会按照价格排序，电子邮箱中的邮件按照时间排序……总之很多东西都需要排序，可以说排序是无处不在。现在我们举个具体的例子来介绍一下排序算法。...
排序算法 快速排序 归并排序 堆排序
杨博东的博客
12-14 1701
一：插入排序思想：在对整个数组循环for(i = 0;i < n;i++)的过程中，保证此时走到的i位置的前面已经是一个有序序列，所以对于i位置的处理就是由i位置依次向前，找到第一个不满足大于此时i位置的元素的位置，插入即可。 #include<stdio.h>void Insert(int a[],int n) //a是待排序数组,n是数组大小 { int i,j;
十大经典排序之：归并排序 ｜桶排序
菜菜bu菜的博客
11-28 2223
十大经典排序之：选择排序 ｜堆排序选择排序选择排序原理算法实现例题堆排序堆排序原理算法实现例题
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值