Java数据结构常见排序算法(总结分享)

风枫君_4596

风枫君_4596

2023-01-22

2038人浏览

转载

本篇文章给大家带来了关于java的相关知识,其中主要介绍了一些常见的排序算法,包括了直接插入排序、希尔排序(缩小增量排序)、选择排序以及堆排序等内容,下面一起来看一下,希望对大家有帮助。

1、 认识排序

在学校中,如果我们要参加运动会,或者军训的时候,会按照身高从矮到高进行站队,比如上课老师手上拿的考勤表,通常是按照学号从低到高进行排序的。再比如编程语言排行榜,也是在排序。

生活中有相当多的排序场景,由此可知,排序还是很重要的, 本章就会介绍常见的一些排序算法。

所谓排序呢,就拿我们上面的举例来说,会按照某个或某些关键字的大小,递增或者递减排列起来的操作,这就是排序,这里面也涉及到排序的稳定性,举个例子:

比如有这样的一组数据:B  D  A  C  A  F,要按照他们的 ascll 码来排序,这里出现了两个 A,我们把第一个出现的 A 称为 A1,第二个出现的 A 称为 A2。

假定排序后结果为:A1  A2  B  C  D  F,那么这个排序算法就是稳定的。假设排序后结果为:A2  A1  B  C  D  F,那么这个排序算法就是不稳定的。

简而言之,如果待排序的数据中,有两个相同的元素,排序结束后,这两个元素的关系没有发生改变,比如 A1 排序前在 A2 前面,排完序后,A1 还在 A2 前面,这就是稳定的排序算法。

注意:一个不稳定的排序算法,天生就是不稳定的,但是一个稳定的排序算法,你可以把它设计成不稳定的。 

2、常见排序的分类

这张图,概括了我们后续要讲的排序算法,接着正式进入本章的学习吧!(排序算法章节,默认都是升序排序) 注:后续所说的复杂度 log,都是以2为底,特殊的会标注出来。

3、直接插入排序

现在想请各位小伙伴,想象一下自己在摸扑克牌,摸了第一张牌放在了自己的手中,接着再摸一张,把这张牌跟手上的一张牌进行比较,把它放到合适的位置, 接着再摸一张,把这张牌跟手上的两张牌进行比较,放到合适的位置。

这就是直接插入排序,简单来说,我们每次取的元素,会往一个有序的序列中插入,也就是每次摸牌之前,手上的牌都是排好序的,我们只需要把新摸到的牌,依次与手上有序的牌进行比较,把它放入合适的位置就行!

这里我们用一副静态的图来简单演示下:

大致的思想我们已经明白了,接下来我们就需要用代码来实现他:

public void insertSort(int[] array) {
    // 外循环控制趟数, 第一张牌默认有序, 所以 i 从 1 开始
    for (int i = 1; i = 0; j--) {
            //如果当前位置的牌,大于我摸到的牌,就往后挪
            if (array[j] > tmp) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        // 把摸到的牌放到对应位置上
        array[j + 1] = tmp;
    }
}
  • 时间复杂度分析:外循环一共要 n - 1 次,内循环每次最差的情况下要比较 1....n 次,那么去掉 n 前面的小项,也就是 (n - 1) * n 次,即 n^2 - n,去掉最小项,最后的时间复杂度为 O(n^2)
  • 空间复杂度分析:只是开辟了一个 tmp 的变量 i,j,常数,即空间复杂度:O(1)
  • 稳定性:稳定 
  • 该排序再数据越接近有序的情况,时间效率越高。

4、希尔排序(缩小增量排序)

这个排序是直接插入排序的一种优化,你可以想象一下,你面前有并排放好的 8 个爱心号码牌,但是它们是无序的,我们要给号码牌分组,按要求,第一次间隔为 4 个号码牌的为一组,分完组后进行直接插入排序,第二次间隔为 2 个号码牌的为一组,进行直接插入排序,第三次间隔为 1 个号码牌为一组,进行直接插入排序。

听到这有点没理解,没关系,我们就通过画图来把我上述说的内容再次理解下:

由上图我们可以发现,当间隔 > 1 的时候,都是预排序,也就是让我们的数据更接近有序,但是当间隔为 1 的时候,就是直接插入排序了,前面我们说过,直接插入排序,再数据接近有序的时候时间效率是很快的。由此可见,希尔排序,是直接插入排序的优化版。

Java Development Man
Java Development Man

Java开发手册规约集合,基于阿里巴巴Java开发手册(嵩山版)。 涵盖7大维度:编程规约、异常日志、单元测试、安全规约、MySQL数据库、工程结构、设计规约。

下载

如何在代码中实现呢?间隔的值如何取呢?代码中把这个间隔的值称为 gap,这个 gap 的取值方法有很多,有的人提出 gap 为奇数好,有的提出 gap 为偶数好,我们就采取一种比较简单的方法来取 gap 值,首次取数组长度一半的值为 gap,后续 gap /= 2,即可。当 gap 为 1,也就是直接插入排序了。

代码实现如下:

public void shellSort(int[] array) {
    // gap初始值设置成数组长度的一半
    int gap = array.length >> 1;
    // gap 为 1 的时候直接插入排序
    while (gap >= 1) {
        shell(array, gap);
        gap >>= 1; // 更新 gap 值 等价于 -> gap /= 2;
    }
}
private void shell(int[] array, int gap) {
    for (int i = gap; i = 0; j -= gap) {
            if (array[j] > tmp) {
                array[j + gap] = array[j];
            } else {
                break;
            }
        }
        array[j + gap] = tmp;
    }
}

如果实在是不好理解,就结合上边讲的直接插入排序来理解,相信你能理解到的。

  • 时间复杂度分析:希尔排序的时间复杂度不好分析, 这里我们就大概记一下,约为 O(n^1.3),感兴趣的话,可以查阅一下相关书籍。
  • 空间复杂度分析:仍然开辟的是常数个变量,空间复杂度为 O(1)
  • 稳定性:不稳定

5、选择排序

这个排序是个很简单的排序,你想象一下,有个小屁孩,喜欢玩小球,我给他安排了个任务,把这一排小球从小到大排列起来,摆给我看,于是小屁孩就找,每次从一排小球中找出最大的,放到最后,固定不动,那是不是也就是说,每次能确定一个最大的石子的最终位置了。我们来看图:

通过图片我们也能看出来,每次找到最大值于最后一个值交换,所以每趟都能把最大的放到最后固定不动,每趟能排序一个元素出来,那这样用代码来实现就很简单了:

public void selectSort(int[] array) {
    int end = array.length - 1;
    // 剩最后一个元素的时候, 不用比较了, 已经有序了
    // 所以 i  array[max]) {
                max = j;
            }
            j++;
        }
        //找到了最大值的下标, 把最大值与最后一个值交换
        swap(array, max, end--); // end-- 最后一个元素固定了, 不用参与比较
    }
}

这个算法有没有可以优化的空间呢?

有!那么既然小屁孩能一次找出最大的球,那能不能让小屁孩一次找出两个球出来呢?分别是这些球中,最大的和最小的,最大的放在最右边,最小的放在最左边,那么我们每次就能确定两个球的最终位置,也就是我们一次能排序两个元素。图解:

代码实现如下:

public void selectSort(int[] array) {
    int left = 0;
    int right = array.length - 1;
    while (left  每次找最大最小值下标的时候, 可以不用算默认给的最大值和最小值下标
        for (int i = left + 1; i  array[maxIndex]) {
                maxIndex = i;
            }
            if (array[i] <blockquote><ul>
<li>
<strong>时间复杂度分析:</strong>虽然是优化了,但去小项之后,还是 O(n^2)</li>
<li>
<strong>空间复杂度分析:</strong>O(1)</li>
<li>
<strong>稳定性:</strong>不稳定</li>
<li>实际开发中用的不多</li>
</ul></blockquote><h2>6、堆排序</h2><p>如果你有学习过优先级队列,或者看过博主优先级队列的文章,那么这个排序对于你来说还是很轻松的,当然在堆排序的讲解中,不会过多的去介绍堆的概念,如果对这部分概念还不理解,可以移至博主的上一篇文章进行学习。 </p><p>堆排序,简单来说,就是把一组数据,看成一个完全二叉树,再把这棵树,建大堆或者建小堆,接着进行排序的一种思路。至于如何建大堆或小堆,和向上调整算法以及向下调整算法,这里也不多介绍了,博主的上篇文章都详细介绍过。</p><p>这里我们来分析一下,排升序应该建什么堆?大堆!排降序建小堆!</p><p>这里我们来排升序,建大堆,因为大堆堆顶元素一定是堆中最大的,所以我们可以把堆顶元素和最后一个元素进行交换,这样我们就确认了最大值的位置,接着将交换后的堆顶元素进行向下调整,仍然使得该数组满足大堆的特性!图解如下:</p><p><img alt="" src="https://img.php.cn/upload/article/000/000/067/2bc60faf9fc0c95d70ba2ea59969f749-7.png?x-oss-process=image/resize,p_40"></p><p  style="max-width:90%"><img alt="" src="https://img.php.cn/upload/article/000/000/067/b7212cc82d02b12aea3900b8247d02ae-8.png?x-oss-process=image/resize,p_40"></p><p>如上图步骤也很简单,先是将数组建成大堆,然后利用大堆来进行堆排序,首先将堆顶元素和最后一个元素交换,由此最大的元素就有序了,接着将该堆进行向下调整,使继续满足大堆性质,依次进行下去即可。</p><p><strong>代码实现:</strong></p><pre class="brush:php;toolbar:false;">public void heapSort(int[] array) {
    // 建大堆 从最后一个非叶子节点开始向下调整
    // 非叶子节点下标 = (孩子节点下标 - 1) / 2
    for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
        shiftDown(array, parent, array.length);
    }
    // 建大堆完成后, 每次堆顶元素与最后一个元素交换, 锁定最大元素的位置
    for (int len = array.length - 1; len > 0; len--) {
        swap(array, 0, len); //根节点与最后一个元素交换
        shiftDown(array, 0, len); //根节点位置向下调整
    }
}
private void shiftDown(int[] array, int parent, int len) {
    int child = parent * 2 + 1;
    while (child  array[child]) {
            child++;
        }
        // 判断父节点是否大于较大的孩子节点
        if (array[parent] <blockquote><ul>
<li>
<strong>时间复杂度分析:</strong>建堆的时间复杂度优先级队列那期有说过为 O(n),排序调整堆的时候,一共要调整 n-1 次,每次向下调整的时间复杂度是 logn,所以即 logn(n - 1),即 O(n*logn),加上面建堆的时间复杂度:O(n) + O(n*logn),最终时间复杂度也就是:O(n*logn)。</li>
<li>
<strong>空间复杂度分析:</strong>O(1)</li>
<li>
<strong>稳定性:</strong>不稳定</li>
</ul></blockquote>

推荐学习:《java视频教程》

Java免费学习笔记:立即使用
解锁 Java 大师之旅:从入门到精通的终极指南

相关文章

java速学教程(入门到精通)
java速学教程(入门到精通)

java怎么学习?java怎么入门?java在哪学?java怎么学才快?不用担心,这里为大家提供了java速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

java

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
treenode的用法
treenode的用法

​在计算机编程领域,TreeNode是一种常见的数据结构,通常用于构建树形结构。在不同的编程语言中,TreeNode可能有不同的实现方式和用法,通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

2023.12.01

3001

7

C++ 高效算法与数据结构
C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化,涵盖排序算法(快速排序、归并排序)、查找算法、图算法、动态规划、贪心算法等,并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构(链表、树、堆、哈希表等),帮助开发者提升 在复杂应用中的算法设计与性能优化能力。

2025.12.22

416

20

深入理解算法:高效算法与数据结构专题
深入理解算法:高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念,适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用,如数组、链表、栈、队列、哈希表、树、图等;以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析,帮助开发者不仅能熟练运用这些基础知识,还能在实际编程中优化性能,提高代码的执行效率。本专题适合准备面试的开发者,也适合希望提高算法思维的编程爱好者。

2026.01.06

437

22

C++ 数据结构与算法实现教程合集
C++ 数据结构与算法实现教程合集

以 C++ 为实现语言,系统讲解核心数据结构与算法,涵盖链表(单链表/双链表/环检测)、栈与队列(单调栈/优先队列)、二叉树(遍历/BST/AVL/红黑树)、哈希表(开地址法/链地址法)、图(邻接表/BFS/DFS/Dijkstra/拓扑排序)、常见排序算法(快排/归并/堆排/计数排序)的实现与复杂度分析,同时分享 LeetCode 刷题技巧、竞赛编程常用模板(二分/前缀和/滑动窗口/动态规划),帮助开发者夯实算法基础。

2026.05.09

512

25

堆和栈的区别
堆和栈的区别

堆和栈的区别:1、内存分配方式不同;2、大小不同;3、数据访问方式不同;4、数据的生命周期。本专题为大家提供堆和栈的区别的相关的文章、下载、课程内容,供大家免费下载体验。

2023.07.18

7267

5

堆和栈区别
堆和栈区别

堆(Heap)和栈(Stack)是计算机中两种常见的内存分配机制。它们在内存管理的方式、分配方式以及使用场景上有很大的区别。本文将详细介绍堆和栈的特点、区别以及各自的使用场景。php中文网给大家带来了相关的教程以及文章欢迎大家前来学习阅读。

2023.08.10

2968

6

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7376

4

GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

20

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

20

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
dev.java 官方:Learn Java
dev.java 官方:Learn Java

共0课时 | 0人学习

Java JDBC数据库连接官方教程
Java JDBC数据库连接官方教程

共0课时 | 0人学习