文档章节

数据结构之排序算法

白志华
 白志华
发布于 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

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

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

野渡书生
2016/04/29
31
0
常用数据结构以及数据结构的排序算法

数组 (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
算法分析(2)经典排序算法对比

[TOC] 概述 上一篇文章分析了一下基本的排序算法以及Java的实现,不过没有比较深入的去分析,因为对于O(n^2)的算法实现比较简单,但是对于O(nLogn)的算法本身有些复杂,所以就分为两篇文章来...

wustor
2017/11/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

20180925 df与du命令、fdisk磁盘分区

df 命令 disk filesystem的缩写,查看已挂载磁盘的总容量、使用容量、剩余容量信息。 [root@centos01 ~]# dfFilesystem 1K-blocks Used Available Use% Mounted on/dev/sda3 27...

野雪球
27分钟前
0
0
Shell编程(expect同步文件、指定host和同步文件、构建文件分发系统、批量执行命令)

expect脚本同步文件 需求:自动同步文件 实验准备: A机器:192.168.248.130 B机器:192.168.248.129 实现: 1.A机器编写4.expect脚本文件,内容如下所示: #!/usr/bin/expectset passwd "...

蛋黄_Yolks
53分钟前
2
0
ppwjs之bootstrap颜色:背景颜色

<!DOCTYPT html><html><head><meta http-equiv="content-type" content="text/html; charset=utf-8" /><title>ppwjs欢迎您</title><link rel="icon" href="/favicon.ico" ......

ppwjs
54分钟前
1
0
Ubuntu与 Fedora之对比

大家好。今天我将重点介绍两个流行的Linux发行版之间的一些特性和差异; Ubuntu 18.04和Fedora 28。它们都有自己的包管理; Ubuntu使用DEB,而Fedora使用RPM,但它们都具有相同的桌面环境(GNO...

linuxprobe16
57分钟前
2
0
线性代数入门

线性代数的概念对于理解机器学习背后的原理非常重要,尤其是在深度学习领域中。它可以帮助我们更好地理解算法内部到底是怎么运行的,借此,我们就能够更好的做出决策。所以,如果你真的希望了...

牛奋Debug
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部