文档章节

数据结构之排序算法

白志华
 白志华
发布于 2015/10/18 10:56
字数 1145
阅读 24
收藏 2

    数据结构中的排序算法很经典,在软考中所占据的分数也不少,下面就跟大家细说一下排序算法吧。


    算法排序大致分为5类:插入排序,选择排序,交换排序,归并排序,基数排序。

 【插入排序】
     插入排序 有直接插入排序和希尔排序算法。
    直接插入排序,输入一个元素,检查数组列表中的每个元素,将其插入到一个已经排好序的数列中的适当位置,使数列依然有序,当最后一个元素放入合适位置时,该数组排序完毕。
    每次插入都是从第0个元素开始比较,若原数列为递增数列,则排在小于第i个元素的前面,反之,则从插到大于第i个元素的后面。
例如递增数列:12  28  45 76,插入30,则从第0个元素(12)开始比较,一直到第2个元素(45),小于第2个元素,所以排在第2个元素(45)的前面。
    直接排序是一个一个的比较,所以我给它起名叫“蜻蜓点水”。

     希尔排序 是对一个无序数列进行排序。是将整个无序数列分割成若干小的子序列分别进行直接插入排序的方法(初次取序列的一半为增量d,以后每次减半,直到增量为1。如果d为偶数,则加1,保证d为奇数)。
图解:

 


     希尔排序这种先分组,再排序,通过组内排序达到整个排序的目的的算法,我也给它赋予了一个名字“攘外必先安内

【选择排序
    选择排序有直接选择排序和堆排序。
       直接选择排序第1趟通过n-1次关键字的比较,从n个记录中选出关键字最小的记录,和第1个记录进行交换。然后从剩余的n-1里再找最小的和第二个元素交换,以此类推,直到所有记录排序完成为止。
图解:

 
直接选择排序,从中挑选最小的一个,然后进行交换,就像古代皇帝点状元一样,所以给它起名“金榜题名”吧。

     堆排序: 将一个序列按完全二叉树的形式构建堆,通过排序,使得所有父节点都比其孩子节点要大(大顶堆,值最大的节点为根节点)或小(小顶堆,值最小的节点为根节点)。
排序过程: 将序列按完全二叉树的形式构建 然后从第n/2个元素开始判断,如果该节点的孩子节点比父节点大,则孩子节点与父节点互换。
图解:

 

堆排序排出来的效果一头小,一头大,就像一个圆锥,所以我给它起名“颠倒圆锥”。

【交换排序
    交换排序有冒泡排序法和快速排序法。
     冒泡排序法: 有2种排序方式,第一种排法:由第一个元素跟前面的元素依次比较,如果后面的数比第一个数小,则交换,最终一个位置是存放的最小的数,然后从第2个数开始,一次类推。第二种排法:从第一个开始, 依次比较相邻两个数,将大数放在后面,一次排完后,最大的数在最后,然后还是从第一个数开始,到倒数第二个数停止,找出次大的数,然后继续循环。
图解:


     快速排序法: 采用 分治思想,选取一个数作为基数,然后对序列进行排序,小于基数的放在 基数 前面,大于基数的放在基数后面。完成一次排序后,再对前后2个集合进行相同的排序。
图解:


【归并排序
     归并排序: 归并排序法也是采用的分治法思想。首先将n个元素分成两个含n/2元素的子序列;然后再将两个子序列递归排序(最后可以将整个原序列分解成n个子序列);最后合并两个已排序好的序列。
图解:

 


【基数排序
      基数排序 : 是根据数字的性质来逐个根据个位数、十位数、百位数分类求得进行分类
图解:

 


 

版权声明:本文为博主原创文章,未经博主允许不得转载。

本文转载自:http://blog.csdn.net/xiaoxian8023/article/details/7524980

共有 人打赏支持
白志华
粉丝 31
博文 265
码字总数 57524
作品 0
长沙
程序员
私信 提问
排序(sort)

1、定义 排序 所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。其确切定义如下: 输入:n个记录R1,R2,…,Rn,其相应的关键字分别为K1,K2,…,Kn。 输出:R...

野渡书生
2016/04/29
31
0
维基百科上的算法和数据结构链接很强大

突然发现维基百科上的算法和数据结构比百度百科强多啦,图文并茂。 其实这个网站不错:http://www.sorting-algorithms.com 冒泡排序: bubble冒泡的意思 http://zh.wikipedia.org/wiki/%E5%8...

晨曦之光
2012/03/09
2.3K
1
常用数据结构以及数据结构的排序算法

数组 (Array)   在程序设计中,为了处理方便, 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中, 数组属于构造数据类型。一个数组可...

带梦想一7飞
2012/09/13
0
0
python-Processing data

string的strip()函数,去除空格,split()分割字符返回列表 set()无序的不重复的集合 sorted()排序算法,返回一个原序列的副本,而原来的序列不发生变化 sort()排序算法,直接改变原来的序列的...

伊人梦醉
2016/06/20
4
0
八种排序算法效率比较

从刚上大一那会儿学的C语言开始,就已经接触到了不少排序算法,但当时都只是为了完成简单的排序任务而已,而且所给的数据也不够多,所以看不出各个排序算法间的执行效率的优劣。最近有个数据...

lwaif
2015/10/22
2.3K
0

没有更多内容

加载失败,请刷新页面

加载更多

SpringBoot与pageHelper版本问题

<parent> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-parent</artifactId> <version>2.0.6.RELEASE</version></parent> <dependency>......

WALK_MAN
5分钟前
0
0
PHP开发支付宝微信个人免签支付接口实例

这是一个PHP开发支付宝微信个人免签支付接口实例,支付宝微信即时到帐接口,使用原生支付宝即时到帐接口修改而来,即可实现多接口收款功能,开发只需要按照支付宝即时到帐接口开发即可,减少...

sucaihuo
10分钟前
1
0
《孩子,你慢慢来》的读书笔记与读后感2600字

《孩子,你慢慢来》的读书笔记与读后感2600字: 龙——保护儿童的思维: 今天读《孩子,你慢慢来》龙这一节,安安的妈妈是中国人,她在安安两岁的时候就认识到安安有着固执的个性。安安正是处...

原创小博客
21分钟前
2
0
kubernetes每个节点创建一个服务的Pod

1. 问题场景 希望一个worker节点上仅部署同样的服务一个. 比如: kubernets有三个worker节点,三个节点部署N个副本的api服务, 为了提高服务效率希望加入缓存,需要为三个节点个部署一个redis服务...

jimmywa
24分钟前
4
0
搭建Git服务器

Git本身是没有服务器和客户端的区别,但是如果我们要共享git仓库时,就需要ssh、http,它们就有服务器和客户端的区别。 Windows平台下搭建Git服务器 1、在自己电脑搭建Git服务器,且只有自己...

国仔饼
39分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部