【Java数据结构与算法】Day2-高级排序（希尔、归并、快速、计数）

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

✅作者简介热爱Java后端开发的一名学习者大家可以跟我一起讨论各种问题喔。
🍎个人主页Hhzzy99
🍊个人信条坚持就是胜利
💞当前专栏【Java数据结构与算法】
🥭本文内容Java数据结构与算法中的比较高级的排序希尔排序、归并排序、快速排序、计数排序

Java数据结构与算法

文章目录

上一篇文章我们介绍了Java中的简单排序传送门🚩本文介绍Java中的高级排序希尔排序、归并排序、快速排序、计数排序

排序方法时间复杂度平均时间复杂度最坏时间复杂度最好空间复杂度稳定性
插入排序O(n²)O(n²)O(n)O(1)稳定
希尔排序O(n1.5)O(n²)O(n)O(1)不稳定
选择排序O(n²)O(n²)O(n²)O(1)不稳定
堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定
冒泡排序O(n²)O(n²)O(n)O(1)稳定
快速排序O(nlog2n)O(n²)O(nlog2n)O(nlog2n)不稳定
归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定

高级排序

1.希尔排序

描述

第一批突破O(n2)时间复杂度的排序算法是简单插入排序的改进版。它与插入排序的不同之处在于他会优先比较距离较远的元素。希尔排序又叫 缩小增量排序

算法的核心思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接 插入排序具体算法描述

  • 先根据数组长度/n获取增量K第一次n为2
  • 按增量序列个数K进行分组一般可以分为K组
  • 根据已分好的组进行插入排序每组排序根据对应的增量k来找到当前组的元素
  • 当每组都排序完成之后回到第一步将n*2再次分组进行插入排序直到最终k=1的时候再执行一次 插入排序 完成最终的排序

实现

分解1 先将数组根据长度分为length/2组增量并且将第一组的元素进行插入排序

可以先实现获取第一组的元素:

第一轮增量10/2=5组

public static void main(String[] args) {
        int[] arrs = new int[]{8,6,1,7,2,5,4,12,9,3};
        //分组
        int group = arrs.length / 2;
        System.out.println("输出第一组的元素");
        for (int j = 0; (j + group) < arrs.length; j += group){
            int insert = j + group;
            while ((insert - group) >= 0){
                if(arrs[insert - group] > arrs[insert]){
                    //交换
                    int temp = arrs[insert - group];
                    arrs[insert - group] = arrs[insert];
                    arrs[insert] = temp;
                    //插入的指针向前移动
                    insert = insert - group;
                }else {
                    break;
                }

            }
        }
        for (int i = 0; i < arrs.length; i++){
            System.out.print(arrs[i] + ",");
        }
    }

1

分解2 将第一轮分好的所有的组都进行插入排序。

第二轮增量5/2=2组

外面嵌套一个小于group的循环

for (int i = 0; i < group; i++) {
            for (int j = i; (j + group) < arrs.length; j += group){
                int insert = j + group;
                while ((insert - group) >= 0){
                    if(arrs[insert - group] > arrs[insert]){
                        //交换
                        int temp = arrs[insert - group];
                        arrs[insert - group] = arrs[insert];
                        arrs[insert] = temp;
                        //插入的指针向前移动
                        insert = insert - group;
                    }else {
                        break;
                    }

                }
            }
        }

分解3 执行完第一轮之后再继续分组执行分解1和分解2的操作最终到无法分组排序完成

public static void main(String[] args) {
        int[] arrs = new int[]{8,6,1,7,2,5,4,12,9,3};
        //分组
        int group = arrs.length;
        //等于1时说明无法再分组了
        while (group != 1){
            //分组
            group = group / 2;
            for (int i = 0; i < group; i++) {
                for (int j = i; (j + group) < arrs.length; j += group){
                    int insert = j + group;
                    while ((insert - group) >= 0){
                        if(arrs[insert - group] > arrs[insert]){
                            //交换
                            int temp = arrs[insert - group];
                            arrs[insert - group] = arrs[insert];
                            arrs[insert] = temp;
                            //插入的指针向前移动
                            insert = insert - group;
                        }else {
                            break;
                        }

                    }
                }
            }
        }



            /*int j = i;
            while ((j + group) < arrs.length){
                int insert = j + group;
                while((insert - group) >= 0){
                    if(arrs[insert - group] > arrs[insert]){
                        //进行交换
                        int temp = arrs[insert - group];
                        arrs[insert - group] = arrs[insert];
                        arrs[insert] = temp;
                        //插入的指针向前移动
                        insert = insert - group;
                    }else {
                        break;
                    }
                }
                //j进行增量
                j += group;
            }*/




        for (int i = 0; i < arrs.length; i++){
            System.out.print(arrs[i] + ",");
        }
    }

在这里插入图片描述

2.归并排序

描述

归并排序是利用归并的思想实现的排序方法该算法采用经典的分治策略即将问题分成一些小的问题然后递归求解而治的阶段则将分的阶段得到的各答案 “修补” 在一起即分而治之 。

归并排序是稳定排序它也是一种十分高效的排序能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了 名为TimSort的排序算法就是归并排序的优化版本。每次合并操作的平均时月复杂度为O(n)而完全二叉树的深度为|1og2n|。总的平均时间复杂度为O(nlogn)。而旦归并排序的最好最坏平均时间复杂度均为o(nlogn)。

归井排序核心思想是先分再治,具体算法描述如下

先将未排序数组/2进行分组,然后再将分好组的数组继续/2再次分组,直到无法分组,这个就是分的过程。

然后再将之后把两个数组大小为1的合并成一个大小为2的再把两个大小为2的合并成4的同时在合并的过程中完成数组的排列最终直到全部小的数组合并起来这个就是治的过程。

在这里插入图片描述

实现

分解1 先实现分的思想将数组分解进行实现

先获取数组的中轴然后以中轴将数组分为两个部分

使用递归分别执行左右两部分分解

public static void main(String[] args) {
        int[] arrs = {8,6,3,7,2,5,4,1};
        mergeSort(arrs,0,arrs.length-1);
    }

    //实现归并排序
    public static void mergeSort(int[] arrs, int first, int last){
        //实现递归推出的条件
        if(first >= last){
            return;
        }
        //求出当前数组的中间值
        int mid = (first + last)/2;

        //将左边的数组继续分解
        mergeSort(arrs,first,mid);
        //将右边的数组继续分解
        mergeSort(arrs,mid + 1, last);

        //输出分组情况
        //先输出左边的数组
        for (int i = first; i <= mid; i++){
            System.out.print(arrs[i] + " ");
        }
        System.out.print("--------");
        //输出右边的数组
        for (int i = mid + 1; i <= last; i++) {
            System.out.print(arrs[i] + " ");
        }

        System.out.println("   ");

    }

分解2 实现具体治的过程将左右两个数组合并到一个临时数组中

分别设计两指针i和j遍历左右两个数组取出元素进行比较将小的元素放入到临时数组中。

然后将左右剩下的元素放入到数组中

将排序好的临时数组中的元素返回到未排序的数组中

public static void main(String[] args) {
        int[] arrs = {8,6,3,7,2,5,4,1};
        mergeSort(arrs,0,arrs.length-1);
        //输出排序结果
        for (int i = 0; i < arrs.length; i++) {
            System.out.print(arrs[i] + " ");
        }
    }

    //实现归并排序
    public static void mergeSort(int[] arrs, int first, int last) {
        //实现递归推出的条件
        if (first >= last) {
            return;
        }
        //求出当前数组的中间值
        int mid = (first + last)>>>1;

        //将左边的数组继续分解
        mergeSort(arrs, first, mid);
        //将右边的数组继续分解
        mergeSort(arrs, mid + 1, last);

        //治实现插入并完成排序
        int[] temp = new int[last + 1];
        //定义两个指针
        int i = first;//左边数组的遍历指针
        int j = mid + 1;//右边数组的遍历指针
        int t = 0;//临时数组的指针
        //遍历左右两个数组将较小的元素插入到临时数组中
        while (i <= mid && j <= last) {
            if (arrs[i] <= arrs[j]) {
                //将左边的指针指向的元素插入到临时数组中
                temp[t++] = arrs[i++];
            } else {
                //将右边的指针指向的元素插入到临时数组中
                temp[t++] = arrs[j++];
            }
        }
        //再将左右剩余的元素插入到临时数组中
        while (i<=mid){
            temp[t++] = arrs[i++];
        }
        while (j<=last){
            temp[t++] = arrs[j++];
        }

        //还需要将临时数组中的元素复制到原始数组中
        //先将t重置
        t = 0;
        //将t指向的值复制到first指向的原始数组的位置
        while (first <= last){
            arrs[first++] = temp[t++];
        }
    }

3.快速排序

描述:

快速排序是对冒泡排序的一种改进通过分而治之的思想减少排序中交换和遍历的次数整个过程可以通过递归的方式完成。

具体描述如下

1.首先通过比较算法找到基准数比较过程通过交换最终达到基准数左边的数字都比右边的小。

2.然后以基准数作为中轴将数组分为两部分分别执行步骤1的算法可以通过递归实现直到无法再次分割排序完毕

递归

一个含直接或间接调用本函数语句的函数被称之为递归函数他必须满足以下两个条件

1在每一次调用自己时必须是在某种意义上更接近于解

2必须有一个终止处理或计算的准则

基本格式

void func()
{
	//递归条件
	if(condition)
		func();
	else
		//退出递归
}

实现

分解1 创建左右两个指针将最后一个值作为基准值通过不断交换将数组分为两部分左边的比右边的要小。

  • 先判断左指针和基准的值如果小于等于就向后移动直到遇到比基准值大的值
  • 再判断右边指针和基准值如果大于等于就向前移动直到遇到比基准值小的值
  • 然后交换左右指针的值
  • 循环上述操作直到左右指针重合然后交换重合值和基准值
public static void main(String[] args) {
        int[] arrs = {3,9,8,7,2,5,4,1,6};
        //执行快速排序
        quickSort(arrs);

        for (int i = 0; i < arrs.length; i++) {
            System.out.print(arrs[i] + " ");
        }
    }

    //定义快速排序方法
    public static void quickSort(int[] arrs){
        //定义左指针
        int left = 0;
        //定义右指针
        int right = arrs.length - 1;
        //定义基准值
        int pos = arrs.length - 1;
        while (left != right){
            //判断左指针是否比基准值大如果大就停止移动
            while(arrs[left] <= arrs[pos]){
                left++;
            }

            if(left == right)
                break;

            //判断右指针是否比基准值小如果小就停止移动
            while (arrs[right] >= arrs[pos]){
                right--;
            }
            if(left < right){
                //交换左右指针指向的值
                int temp = arrs[left];
                arrs[left] = arrs[right];
                arrs[right] = temp;
            }
        }
        //当left和right重合之后需要将重合的值和基准值进行交换
        int temp = arrs[left];
        arrs[left] = arrs[pos];
        arrs[pos] = arrs[left];
    }

在这里插入图片描述

分解2 将以left和right的重复位置作为中轴将数组分为两部分左右分别执行分解1的操作直到排序完成

public static void main(String[] args) {
        int[] arrs = {3,9,8,7,2,5,4,1,6};
        //执行快速排序
        quickSort(arrs, 0, arrs.length-1);

        for (int i = 0; i < arrs.length; i++) {
            System.out.print(arrs[i] + " ");
        }
    }

    //定义快速排序方法
    public static void quickSort(int[] arrs, int first, int last){
        //设置一下递归退出条件
        if(first >= last)
            return;
        //定义左指针
        int left = first;
        //定义右指针
        int right = last;
        //定义基准值
        int pos = last;
        //当left不等于right
        while (left != right){
            //判断左指针是否比基准值大如果大就停止移动
            while(arrs[left] <= arrs[pos]){
                left++;
            }
            //判断右指针是否比基准值小如果小就停止移动
            while (arrs[right] >= arrs[pos] && left < right){
                right--;
            }
            if(left < right){
                //交换左右指针指向的值
                int temp = arrs[left];
                arrs[left] = arrs[right];
                arrs[right] = temp;
            }
        }
        //当left和right重合之后需要将重合的值和基准值进行交换
        int temp = arrs[left];
        arrs[left] = arrs[pos];
        arrs[pos] = temp;

        //将左边的数组执行快速排序
        quickSort(arrs, first,left - 1);

        //将右边的数组执行快速排序
        quickSort(arrs,right + 1,last);
    }

4.计数排序

描述

计数排序是一个非基于比较的排序算法该算法于1954年由Harold H.Seward提出。它的优势在于在对一定范围内的整数排序时它的复杂度为o(n+k)(其中k是整数的范围快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序基于比较的排序的时间复杂度在理论上的下限是O(nlog(n))如归并排序堆排序)

计数排序是一种适合于最大值和最小值的差值不是不是很大的排序也就是说重复的数据会比较多的情况。

实现

分解1 找到最大的数字并且以数字的大小创建一个统计数组

	//分解1根据最大值创建统一数组
    //遍历数组找到最大的值
    int max = arrs[0];

    for (int i = 0; i < arrs.length; i++) {
        if(arrs[i] > max){
            max = arrs[i];
        }
    }
    //根据最大值创建统一数组
    int[] countArrs = new int[max];

分解2 遍历未排序的数组统计每个数字出现的次数根据下标添加到新的统计数组中

for (int i = 0; i < arrs.length; i++) {
            //以arrs[i]作为下标++
            countArrs[arrs[i]]++;
        }

分解3 将排序的结果返回到原先的数组中

public static void main(String[] args) {
        int[] arrs = {0,2,1,3,0,2,0,1,1};
        //分解1根据最大值创建统一数组
        //遍历数组找到最大的值
        int max = arrs[0];

        for (int i = 0; i < arrs.length; i++) {
            if(arrs[i] > max){
                max = arrs[i];
            }
        }
        //分解2
        //根据最大值创建统一数组
        int[] countArrs = new int[max + 1];//注意考虑0要加一个
        //遍历原先数组
        for (int i = 0; i < arrs.length; i++) {
            //以arrs[i]作为下标++
            countArrs[arrs[i]]++;
        }

        //分解3:将统计数组对应的下标的数字返回到排序数组中
        int k = 0;//统计数组的下标
        int index = 0;//排序数组的下标
        while (k < countArrs.length){
            //判断统计数组中的值是否大于0
            while(countArrs[k] > 0){
                //将对应的下标返回到排序数组中
                arrs[index++] = k;
                //统计的数字减少一个
                countArrs[k]--;
            }
            k++;
        }
        //输出结果
        for (int i = 0; i < arrs.length; i++) {
            System.out.print(arrs[i] + " ");

        }
    }

统计数组优化

如果待排序的数字很大那么在创建数组的时候会浪费没有空间同时也会导致创建的数组所以需要进行优化;

可以通过使用最大数字减去最小数字求出需要数组的大小。

public static void main(String[] args) {
        int[] arrs = {90,92,91,93,90,92,90,91,91};
        //分解1根据最大值创建统一数组
        //遍历数组找到最大和最小的值
        int max = arrs[0];
        int min = arrs[0];
        for (int i = 0; i < arrs.length; i++) {
            if(arrs[i] > max){
                max = arrs[i];
            }
            if(arrs[i] < min){
                min = arrs[i];
            }
        }
        //分解2
        //根据最大值创建统一数组
        int[] countArrs = new int[max - min + 1];//注意考虑0要加一个
        //遍历原先数组
        for (int i = 0; i < arrs.length; i++) {
            //以arrs[i]作为下标++
            //获取值时需要减去min
            countArrs[(arrs[i] - min)]++;
        }

        //分解3:将统计数组对应的下标的数字返回到排序数组中
        int k = 0;//统计数组的下标
        int index = 0;//排序数组的下标
        while (k < countArrs.length){
            //判断统计数组中的值是否大于0
            while(countArrs[k] > 0){
                //将对应的下标返回到排序数组中
                //需要还原成之前的值+min
                arrs[index++] = k + min;
                //统计的数字减少一个
                countArrs[k]--;
            }
            k++;
        }
        //输出结果
        for (int i = 0; i < arrs.length; i++) {
            System.out.print(arrs[i] + " ");

        }
    }

结语

本文的内容主要是Java数据结构与算法中的高级排序大家如果感兴趣可以点点赞关注一下你们的支持是我最强大的动力非常感谢您的阅读(❁´◡`❁)

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
标签: Java
返回列表

上一篇：学习笔记——SpringMVC文件上传与下载

下一篇：《小猫猫大课堂》3之字符串，转义字符，注释，选择和循环语句，函数等小概括。

“【Java数据结构与算法】Day2-高级排序（希尔、归并、快速、计数）” 的相关文章

【JavaWeb篇】三分钟学会HTTP协议(面试必会)1年前 (2023-02-02)
【Java】1003 我要通过！ (20 分)1年前 (2023-02-02)
【JavaEE】网络初识之网络通信基础1年前 (2023-02-02)
将写好的.py/.java程序变成.exe文件1年前 (2023-02-02)
Java学习（78）字符串概述、String字符串的定义形式1年前 (2023-02-02)
Java while和do while循环详解1年前 (2023-02-02)
分享111个JavaScript源码，总有一款适合您1年前 (2023-02-02)
【Java 数据结构及算法实战】系列 013：Java队列07——双端队列Deque1年前 (2023-02-02)
Java多线程案例——线程池及ThreadPoolExecutor类1年前 (2023-02-02)
Linux 发布 JavaWeb 项目1年前 (2023-02-02)

阿里云国际版