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

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

分类:

1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基数排序) 所需辅助空间最多:归并排序 所需辅助空间最少:堆排序 平均速度最快:快速排序

不稳定:快速排序,希尔排序,堆排序。

先来看看8种排序之间的关系:

1. 直接插入排序

(1)基本思想:在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排

好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数

也是排好顺序的。如此反复循环,直到全部排好顺序。

(2)实例

(3)用java实现(点击图片查看清晰大图)

(4)【排序舞蹈视频学习】

视频内容

2. 希尔排序(最小增量排序)

(1)基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。当增量减到1时,进行直接插入排序后,排序完成。

(2)实例:

(3)用java实现(点击图片查看清晰大图)

(4)【排序舞蹈视频学习】

视频内容

3. 简单选择排序

(1)基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;

然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。

(2)实例:

(3)用java实现(点击图片查看清晰大图)

(4)【排序舞蹈视频学习】

视频内容

4. 堆排序

(1)基本思想:堆排序是一种树形选择排序,是对直接选择排序的有效改进。

堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项(大顶堆)。完全二叉树可以很直观地表示堆的结构。堆顶为根,其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储序,使之成为一个堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

(2)实例:

初始序列:46,79,56,38,40,84

建堆:

交换,从堆中踢出最大数

剩余结点再建堆,再交换踢出最大数

依次类推:最后堆中剩余的最后两个结点交换,踢出一个,排序完成。

(3)用java实现(点击图片查看清晰大图)

(4)【排序舞蹈视频学习】

http://v.youku.com/v_show/id_XMzQzNzAwODQ=.html

原文发布于微信公众号 - zhisheng(zhisheng_blog)

原文发表时间:2016-05-11

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏轮子工厂

快速搞定8大排序算法

11220
来自专栏数据小魔方

左手用R右手Python系列7——排序

排序可能是日常数据清洗过程中比较高频的应用了,今天这一篇给大家介绍R语言和Python中最为常见的排序函数应用。 R语言: sort order rank ar...

30340
来自专栏magicsoar

Effective Modern C++翻译(2)-条款1:明白模板类型推导

第一章 类型推导 C++98有一套单一的类型推导的规则:用来推导函数模板,C++11轻微的修改了这些规则并且增加了两个,一个用于auto,一个用于decltyp...

197100
来自专栏noteless

[一]基础类型概述

https://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html

13530
来自专栏架构师小秘圈

秒懂排序算法

作者:郭耀华,来自:cnblogs.com/guoyaohua 0、排序算法说明 0.1 排序的定义 对一序列对象根据某个关键字进行排序。 0.2 术语说明 稳...

42350
来自专栏顶级程序员

各大排序算法性能比较及演示实例

所谓排序,即将原来无序的一个序列重新排列成有序的序列。 排序方法中涉及到稳定性,所谓稳定性,是指待排序的序列中有两个或两个以上相同的项,在排序前和排序后看这些相...

370100
来自专栏软件开发 -- 分享 互助 成长

经典算法学习之分治法(以排列、组合程序为例)

分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归的求解这些子问题,然后再合并这些子问题的解来建立原问题的解。 分治法在每层递归是遵循的三个步...

42870
来自专栏cmazxiaoma的架构师之路

一个Java小白通向数据结构算法之旅(6) - 插入排序

19550
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之 适合大规模的数据排序 数据结构与算法学习笔记之如何分析一个排序算法?

在数据排序的算法中,不同数据规模应当使用合适的排序算法才能达到最好的效果,如小规模的数据排序,可以使用冒泡排序、插入排序,选择排序,他们的时间复杂度都为O(n...

10240
来自专栏微信公众号:Java团长

十大经典排序算法最强总结(含Java代码实现)

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位...

41410

扫码关注云+社区

领取腾讯云代金券