专栏首页尜尜人物的专栏数据结构与算法系列之常用算法:排序算法

数据结构与算法系列之常用算法:排序算法

〇、前言

<<数据结构与算法系列之总篇>>

一、排序算法

下面常用排序算法的动图都是从网络挑选的好理解的动图。

01、冒泡排序

02、选择排序

03、插入排序

04、希尔排序


05、快速排序


06、归并排序

07、堆排序

08、计数排序

09、桶排序


10、基数排序


二、Java排序

1、Arrays.sort()

根据数组的元素个数、nearly sorted(近单调性:单调升序和单调降序)和元素类型等来选在具体排序算法。例如对整数排序:

if (元素个数 < 47) {
    插入排序
} else if (元素个数 < 286) {
    双轴快排
} else if (nearly sorted) {
    归并排序
} else {
    双轴快排
}

2、Collections.sort()

其实底层也是归到Arrays.sort()对Object[]数组的排序。如果LegacyMergeSort.userRequested为true的话就会使用归并排序,可以通过代码设置为true(System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");)如果不为true的话就会用一个叫TimSort的排序算法。

Timsort 是一种混合稳定的排序算法,源自合并排序和插入排序,旨在较好地处理真实世界中各种各样的数据。该算法通过查找已经排好序的数据子序列,在此基础上对剩余部分更有效地排序。 该算法通过不断地将特定子序列(称为一个 run )与现有的 run 合并,直到满足某些条件为止来达成的更有效的排序。在JavaSE7中引入。有兴趣的可以去研究一下。

3、为何Java不使用堆做纯排序

  1. 从cpu缓存的角度,堆是跳跃操作数组的,无法利用cpu缓存预读;
  2. 从nearly sorted角度,如果一个数组很多部分都是有序的,使用堆排序,会将其先打散,反而效率不如快速排序和归并排序。

三、总结

JDK提供的排序算法很好,根据自己特定场景选择用JDK的还是自己实现。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Linux系统之进程状态

    只有在该状态的进程才可能在CPU上运行。而同一时刻可能有多个进程处于可执行状态,这些进程的task_struct结构(进程控制块)被放入对应CPU的可执行队列中...

    尜尜人物
  • Java网络编程系列之TCP连接状态

    尜尜人物
  • Linux系统之常用命令

    环境:CentOS7X64(CentOS Linux release 7.5.1804)

    尜尜人物
  • 常见排序算法分类

      此篇博客不讨论排序算法的思想,时间复杂度,空间复杂度,实现代码。只介绍常见排序算法有哪些,并按照什么进行分类。   排序算法分为两大类: 比较类...

    Dabelv
  • Java常用排序算法/程序员必须掌握的8大排序算法

    Java常用排序算法/程序员必须掌握的8大排序算法 分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排...

    zhisheng
  • EXcel如何排序,高手不告诉你的5个小技巧

    很多人在办公中都会接触到EXccel,也会用到里面的EXcel排序功能,一说到EXcel排序,很多小伙伴都觉得这个功能很简单啊,已经掌握了,没什么好学习的,其实...

    高效办公
  • 十大经典排序算法 -- 动图讲解

    外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;

    互扯程序
  • 排序算法(1)---基本概念

    排序与我们日常生活中息息相关,比如,我们要从电话簿中找到某个联系人首先会按照姓氏排序、买火车票会按照出发时间、买东西会按照销量排序、查找文件会按照最近修改时间排...

    逆月翎
  • 10.1 内部排序

    1、排序(Sorting)时计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。

    闫小林

扫码关注云+社区

领取腾讯云代金券