文档章节

数据结构之排序算法

白志华
 白志华
发布于 2015/10/18 10:56
字数 1145
阅读 22
收藏 2
点赞 0
评论 0

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


    算法排序大致分为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
博文 260
码字总数 57524
作品 0
长沙
程序员
排序(sort)

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

野渡书生 ⋅ 2016/04/29 ⋅ 0

排序算法 - java实现

前言 之前一段时间闲来无聊,整理了一下各种排序算法,并且对各种算法做了一些分析和统计。。。吐血推荐。。。 一共统计了11种排序算法,并且4种类型的随机数字。并且附上实际使用和性能测试...

黑妹妹牙膏 ⋅ 2014/08/19 ⋅ 0

常用数据结构以及数据结构的排序算法

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

带梦想一7飞 ⋅ 2012/09/13 ⋅ 0

python-Processing data

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

伊人梦醉 ⋅ 2016/06/20 ⋅ 0

八种排序算法效率比较

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

lwaif ⋅ 2015/10/22 ⋅ 0

维基百科上的算法和数据结构链接很强大

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

晨曦之光 ⋅ 2012/03/09 ⋅ 1

算法分析(2)经典排序算法对比

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

wustor ⋅ 2017/11/06 ⋅ 0

六种排序算法的JavaScript实现以及总结

最近几天在系统的复习排序算法,之前都没有系统性的学习过,也没有留下过什么笔记,所以很快就忘了,这次好好地学习一下。 首先说明为了减少限制,以下代码通通运行于Node V8引擎而非浏览器,...

DM.Zhong ⋅ 05/24 ⋅ 0

学习数据结构与算法,成为出色的程序员

原文出处:Happy Bear 译文出处:LCTT - icybreaker “相较于其它方式,我一直热衷于推崇围绕数据设计代码,我想这也是Git能够如此成功的一大原因[…]在我看来,区别程序员优劣的一大标准就在...

Happy Bear ⋅ 2015/11/10 ⋅ 0

最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析

作者:jack 1. 关于排序 很高兴与大家一起探讨计算机科学中的基础算法之排序算法。排序算法是非常基础同时又应用非常广泛的算法,无论在工作还是在生活中,比如: 数据库脚本,如MSSql, MySq...

小数点 ⋅ 2017/12/04 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Jenkins实践3 之脚本

#!/bin/sh# export PROJ_PATH=项目路径# export TOMCAT_PATH=tomcat路径killTomcat(){pid=`ps -ef | grep tomcat | grep java|awk '{print $2}'`echo "tom...

晨猫 ⋅ 今天 ⋅ 0

Spring Bean的生命周期

前言 Spring Bean 的生命周期在整个 Spring 中占有很重要的位置,掌握这些可以加深对 Spring 的理解。 首先看下生命周期图: 再谈生命周期之前有一点需要先明确: Spring 只帮我们管理单例模...

素雷 ⋅ 今天 ⋅ 0

zblog2.3版本的asp系统是否可以超越卢松松博客的流量[图]

最近访问zblog官网,发现zlbog-asp2.3版本已经进入测试阶段了,虽然正式版还没有发布,想必也不久了。那么作为aps纵横江湖十多年的今天,blog2.2版本应该已经成熟了,为什么还要发布这个2.3...

原创小博客 ⋅ 今天 ⋅ 0

聊聊spring cloud的HystrixCircuitBreakerConfiguration

序 本文主要研究一下spring cloud的HystrixCircuitBreakerConfiguration HystrixCircuitBreakerConfiguration spring-cloud-netflix-core-2.0.0.RELEASE-sources.jar!/org/springframework/......

go4it ⋅ 今天 ⋅ 0

二分查找

二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于...

人觉非常君 ⋅ 今天 ⋅ 0

VS中使用X64汇编

需要注意的是,在X86项目中,可以使用__asm{}来嵌入汇编代码,但是在X64项目中,再也不能使用__asm{}来编写嵌入式汇编程序了,必须使用专门的.asm汇编文件来编写相应的汇编代码,然后在其它地...

simpower ⋅ 今天 ⋅ 0

ThreadPoolExecutor

ThreadPoolExecutor public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, ......

4rnold ⋅ 昨天 ⋅ 0

Java正无穷大、负无穷大以及NaN

问题来源:用Java代码写了一个计算公式,包含除法和对数和取反,在页面上出现了-infinity,不知道这是什么问题,网上找答案才明白意思是负的无穷大。 思考:为什么会出现这种情况呢?这是哪里...

young_chen ⋅ 昨天 ⋅ 0

前台对中文编码,后台解码

前台:encodeURI(sbzt) 后台:String param = URLDecoder.decode(sbzt,"UTF-8");

west_coast ⋅ 昨天 ⋅ 0

实验楼—MySQL基础课程-挑战3实验报告

按照文档要求创建数据库 sudo sercice mysql startwget http://labfile.oss.aliyuncs.com/courses/9/createdb2.sqlvim /home/shiyanlou/createdb2.sql#查看下数据库代码 代码创建了grade......

zhangjin7 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部