`

程序员必知8大排序3大查找(一)

阅读更多

 

每天都在叫嚣自己会什么技术,什么框架,可否意识到你每天都在被这些新名词、新技术所迷惑,.NET、XML等等技术固然诱人,可是如果自己的基础不扎实,就像是在云里雾里行走一样,只能看到眼前,不能看到更远的地方。这些新鲜的技术掩盖了许多底层的原理,要想真正的学习技术还是走下云端,扎扎实实的把基础知识学好,有了这些基础,要掌握那些新技术也就很容易了。

 

要编写出优秀的代码同样要扎实的基础,如果排序和查找算法学的不好,怎么对程序的性能进行优化?废话不多说,本文要介绍的这些排序算法就是基础中的基础,程序员必知!


 

1、直接插入排序

 

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

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

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

2)实例


 

 

2、希尔排序(也称最小增量排序)


1)基本思想:算法先将要排序的一组数按某个增量dn/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大查找

    ### 程序员必知的八大排序三大查找 #### 排序算法概览 排序算法是计算机科学中的一项基础技能,对数据进行排序能够帮助我们更高效地处理信息。以下将详细介绍八种常见的排序算法及其特点。 #### 1. 直接插入排序 ...

    程序员必知的8大排序(值得一看)

    ### 知识点一:直接插入排序 #### 基本思想 直接插入排序的基本思想是在待排序数组中,假设前n-1个元素已经排序好,将第n个元素插入到已排序的部分中,使得这n个元素也处于排序状态。通过不断迭代此过程,最终整个...

    开发人员必知8大排序3大查找

    标题和描述中提到的知识点是IT领域中程序员必须掌握的基础算法——八大排序算法和三大查找算法。这些算法是数据处理和程序优化的核心,对于提升软件性能至关重要。下面将详细介绍这八大排序算法及其特点: 1. **...

    程序员必备的八大排序三大查找

    每天都在叫嚣自己会什么技术,什么框架,可否意识到你每天都在被这些新名词、新技术所迷惑,.NET、XML等等技术固然诱人,可是如果自己的基础不...废话不多说,本文要介绍的这些排序算法就是基础中的基础,程序员必知!

    Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找

    本资料包聚焦于"Java常用排序算法"和"程序员必须掌握的8大排序算法",并深入探讨了"二分法查找"这一高效搜索技术。 首先,我们来看八大排序算法。这些算法包括: 1. **冒泡排序**:最简单的排序方法,通过不断交换...

    程序员必知excel操作

    下面将详细介绍一些程序员必知的Excel操作,帮助提升工作效率。 1. 数据整理: - **排序与筛选**:对数据进行升序或降序排列,利用条件筛选找出特定数据。 - **合并单元格**:在报表头部创建合并的标题,注意合并...

    程序员必知的十大基础实用算法及其讲解

    3. **递归排序:**递归地对基准左侧和右侧的子序列进行同样的操作,直到每个子序列的大小为零或一,此时序列被认为是已排序的。 **应用场景:** - 快速排序广泛应用于各种数据处理场景,特别是在大数据集的排序中...

    程序员必知必会经典算法

    "程序员必知必会经典算法"这个主题涵盖了编程领域中的重要概念,包括基础算法和数据结构,这些都是C、C++等语言中不可或缺的部分。下面将详细讨论这些经典算法及其在实际编程中的应用。 首先,我们要理解什么是算法...

    程序员必知的硬核知识大全.zip

    《程序员必知的硬核知识大全》是一份涵盖了IT行业核心知识的综合资源,旨在帮助程序员提升技能,增强职业竞争力。这份压缩包包含了一个名为"程序员必知的硬核知识大全.pdf"的文件,它详细阐述了编程、算法、数据结构...

    Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找(同步到博客).doc

    【Java 常用排序算法】排序是编程中常见的任务之一,主要分为四类:插入排序、交换排序、选择排序和归并排序。此外,还有分配排序中的基数排序。以下是对这些排序算法的详细说明: 1. **直接插入排序**: 直接插入...

    java程序员必知的十种程序算法.doc

    冒泡排序是一种简单的排序算法,通过不断交换相邻的不正确顺序的元素,逐渐将较大的元素“冒”到数组的后端,时间复杂度为O(n^2)。 6. **选择排序**: 选择排序每次找到当前未排序部分的最小(或最大)元素,放到...

    算法 快速排序 冒泡排序 监视哨 折半查找

    快速排序、冒泡排序、监视哨以及折半查找是计算机科学中非常重要的基础算法,对于理解和应用编程至关重要,特别是对于参与ACM(国际大学生程序设计竞赛)或其他算法竞赛的程序员来说,这些都是必须掌握的核心技能。...

    2013年软考程序员必考知识点总结

    【软考程序员必考知识点详解】 软考程序员是信息技术领域一项重要的资格认证考试,主要考察考生的基础编程能力、计算机系统知识、软件工程实践等方面。以下是对2013年软考程序员考试复习重点的详细解释: 1. **...

    数据结构查找、排序、二分查找、折半查找算法

    文件名中的"Sun数据结构第8章查找(第22-25讲).ppt"和"Sun数据结构第9章排序(第25-27讲).ppt"表明,内容可能详细涵盖了查找算法的各个方面,包括二分查找的原理、实现和优化,以及排序算法的介绍、实现步骤和性能...

    《计算机程序设计艺术(第3卷)》 第3卷:排序与查找 (第二版) 高清中文版 PDF

    这本书的第3卷专门探讨了排序与查找这两个核心的算法主题,它们是编程和数据处理的基础。在本卷中,Knuth深入剖析了各种排序和查找算法的设计、分析及其在实际应用中的性能表现。 排序算法是计算机科学中的重要组成...

    C语言排序查找源代码

    这里,我们围绕“C语言排序查找源代码”这个主题进行深入探讨。 首先,让我们逐一分析这些文件名所代表的算法: 1. **快速排序.c**:快速排序是一种基于分治思想的高效排序算法,由C.A.R. Hoare在1960年提出。它的...

    c程序 排序 查找

    本压缩包文件包含的“c程序 排序 查找”聚焦于C语言中两个核心概念:排序和查找,这些都是数据处理和分析的基础。下面将详细阐述这两个知识点及其在实际中的应用。 首先,我们来探讨“排序”。排序是指将一组数据...

    排序和查找

    排序和查找是计算机科学中最基础且重要的概念,尤其对于程序员来说,掌握这些算法对于优化程序性能至关重要。以下是对标题和描述中提及的八大排序算法和三大查找算法的详细解释: 1. **直接插入排序**: - 基本...

    一本关于程序员面试的书籍,希望大家喜欢

    《程序员面试宝典》包含了排序算法(如冒泡、选择、插入、快速、归并排序)、查找算法(如二分查找、哈希查找)以及动态规划、贪心算法、回溯算法等高级算法。熟练掌握这些算法,能帮助求职者在面试时快速准确地给出...

    排序及折半查找c语言简单实现

    在计算机科学领域,排序和查找是基础且至关重要的算法,它们在数据处理和信息管理中发挥着关键作用。本文将详细探讨使用C语言实现冒泡排序、选择排序以及折半查找的方法。 首先,我们来看冒泡排序。冒泡排序是一种...

Global site tag (gtag.js) - Google Analytics