第二篇《程序员必知8大排序3大查找(二)》
《程序员必知8大排序3大查找(三)》
每天都在叫嚣自己会什么技术,什么框架,可否意识到你每天都在被这些新名词、新技术所迷惑,.NET、XML等等技术固然诱人,可是如果自己的基础不扎实,就像是在云里雾里行走一样,只能看到眼前,不能看到更远的地方。这些新鲜的技术掩盖了许多底层的原理,要想真正的学习技术还是走下云端,扎扎实实的把基础知识学好,有了这些基础,要掌握那些新技术也就很容易了。
要编写出优秀的代码同样要扎实的基础,如果排序和查找算法学的不好,怎么对程序的性能进行优化?废话不多说,本文要介绍的这些排序算法就是基础中的基础,程序员必知!
1、直接插入排序
(1)基本思想:在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排
好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数
也是排好顺序的。如此反复循环,直到全部排好顺序。
(2)实例
2、希尔排序(也称最小增量排序)
(1)基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。当增量减到1时,进行直接插入排序后,排序完成。
(2)实例:
3、简单选择排序
(1)基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;
然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。
(2)实例:
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
建堆:
交换,从堆中踢出最大数
剩余结点再建堆,再交换踢出最大数
依次类推:最后堆中剩余的最后两个结点交换,踢出一个,排序完成。
5、冒泡排序
(1)基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。
(2)实例:
未完待续,第二篇将介绍剩余3大排序,排序稳定性,复杂度(这句话过期,呵呵!)
第二篇杀到,《程序员必知8大排序3大查找(二)》
希望大家多多支持!
分享到:
相关推荐
此文档中不紧包括8大排序3大查找算法的基本思想,而且还附上有每种算法实现的源码,还有清楚明了的图文解析,更加易懂。对于一个程序员来讲,要编写出优秀的代码同样要扎实的基础,如果排序和查找算法学的不好,怎么...
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找 Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找
每天都在叫嚣自己会什么技术,什么框架,可否意识到你每天都在被这些新名词、新技术所迷惑,.NET、XML等等技术固然诱人,可是如果自己的基础不...废话不多说,本文要介绍的这些排序算法就是基础中的基础,程序员必知!
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找(同步到博客).doc
本书作者介绍了一些有用但很少被讨论的算法,它们可用于语音查找、日期和时间例程(直到公元1年)、B树和索引文件、数据压缩、任意精度的算术、校验和与数据验证,并且还最全面地介绍了查找例程、排序算法和数据结构...
1.2.10 DBA与程序员 第2章 数据表的创建和管理 2.1 数据类型 2.1.1 整数类型 2.1.2 数值类型 2.1.3 字符相关类型 2.1.4 日期时间类型 2.1.5 二进制类型 2.2 通过SQL语句管理数据表 2.2.1 创建数据...
本书(程序员常用算法)重点关注的是实用,立即可用的代码,并且广泛...日期和时间例程(直到公元1年)、B树和索引文件、数据压缩、任意精度的算术,校验和与数据验证,并且全面地介绍了查找例程、排序算法和数据结构。..
专业的程序设计人员常被称为程序员。 2.程序设计=数据结构+算法 Programming = Data Structures + Algorithm 3.程序设计:为计算机处理问题编制一组指令集。 算法:处理问题的策略。 数据结构:问题的数学模型。...
1.2.10 DBA与程序员 第2章 数据表的创建和管理 2.1 数据类型 2.1.1 整数类型 2.1.2 数值类型 2.1.3 字符相关类型 2.1.4 日期时间类型 2.1.5 二进制类型 2.2 通过SQL语句管理数据表 2.2.1 创建数据...
5.7 小结:选择一种排序算法 5.8 资源和参考资料 第6章 树 6.1 二叉树 6.1.1 树查找 6.1.2 节点插入 6.1.3 节点删除 6.1.4 二叉查找树的性能 6.1.5 AVL树 6.2 红黑树 6.3 伸展树 ...
程序员面试题精选 100 题(01)-把二元查找树转变成排序的 双向链表 题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点, 只调整指针的指向。 程序员面试题精选 100 题...
1.2.10 DBA与程序员 第2章 数据表的创建和管理 2.1 数据类型 2.1.1 整数类型 2.1.2 数值类型 2.1.3 字符相关类型 2.1.4 日期时间类型 2.1.5 二进制类型 2.2 通过SQL语句管理数据表 2.2.1 创建数据...
• 第四章 查找匹配 o 4.1 有序数组的查找 o 4.2 行列递增矩阵的查找 o 4.3 出现次数超过一半的数字 • 第五章 动态规划 o 5.0 本章导读 o 5.1 最大连续乘积子串 o 5.2 字符串编辑距离 o o o 5.3 格子取数 5.4 ...
1.2.10 DBA与程序员 第2章 数据表的创建和管理 2.1 数据类型 2.1.1 整数类型 2.1.2 数值类型 2.1.3 字符相关类型 2.1.4 日期时间类型 2.1.5 二进制类型 2.2 通过SQL语句管理数据表 2.2.1 创建数据...
1.2.10 DBA与程序员 第2章 数据表的创建和管理 2.1 数据类型 2.1.1 整数类型 2.1.2 数值类型 2.1.3 字符相关类型 2.1.4 日期时间类型 2.1.5 二进制类型 2.2 通过SQL语句管理数据表 2.2.1 创建数据...
详细介绍了直接插入排序、希尔排序、简单选择排序、堆排序、冒泡排序、快速排序、归并排序、基数排序等
此外,文档还包括一个逐步指南,介绍了如何在Java中实现有序矩阵查找,包括详细的代码示例和实现细节。 文档还涵盖了高级主题,如如何优化代码以提高性能,以及如何处理大的矩阵。该资源包括实用练习,让读者可以...
日期和时间例程(直到公元1年)、B树和索引文件、数据压缩、任意精度的算术,校验和与数据验证,并且全面地介绍了查找例程、排序算法和数据结构。.. 本书只要求读者具有C语言的初级知识以及基本代数的相关知识。源代码...
【作 者】(美)DonaldE.Knuth著 【内容提要】 关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷已经组成了程序设计理论和实践...第3卷为排序和查找,分“排序”和“...