北京官方网站网,网络营销推广专员,网站建设公司 云智互联,电子商务网站会员体系文章目录 一、排序算法1.1 插入排序1、直接插入排序2、折半插入排序3、希尔排序 1.2、交换排序法1、起泡排序2、快速排序 1.3 选择类排序1、简单选择排序 二、业务逻辑算法设计2.1 基本概念和术语2.2 静态查找表2.3、有序表的查找 一、排序算法 排序是数据处理过程中经常使用的… 文章目录 一、排序算法1.1 插入排序1、直接插入排序2、折半插入排序3、希尔排序 1.2、交换排序法1、起泡排序2、快速排序 1.3 选择类排序1、简单选择排序 二、业务逻辑算法设计2.1 基本概念和术语2.2 静态查找表2.3、有序表的查找 一、排序算法 排序是数据处理过程中经常使用的一种重要的运算排序的方法有很多种本节主要讨论内排序的各种算法并对每个排序算法的时间和空间复杂性以及算法的稳定性等进行讨论。 1、什么是排序 排序是计算机内经常进行的一种操作其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如:将下列关键字序列:49,38,65,97,76,13, 27,49,调整为13,2738,49,49, 65, 76, 97 2、排序算法的稳定性 排序算法的稳定性: 如果在对象序列中有两个对象r[i]和r[j]它们的关键字 k[i] k[j]且在排序之前对象r[i]排在r[j]前面。如果在排序之后对象rr 仍在对象rr;的前面则称这个排序方法是稳定的否则称这个排序方法是不稳定的。(值相同的两个不同位置上的数在排序后如果前后位置发生变化就不稳定。) 3、排序算法分类 按排序过程中使用到的存储介质来分可以将排序分成两大类序和外排序。内排序是指在排序过程中所有数据均放在内存中处理不需要使用外存的排序方法。而对于数据量很大的文件在内存不足的情况下则还需要使用外存这种排序方法称为外排序。 内部排序 分类插入排序交换排序选择排序归并排序基数排序 1.1 插入排序
基本思想每一轮比较值在有序序列R中的位置 1、实现”一趟插入排序“可分三步进行
1、直接插入排序 代码实现 直接插入排序的时间复杂度
2、折半插入排序 对于数据量不大时可以用直接插入排序对于数据量较大时选择折半插入排序。 折半插入排序基本思想是: 设在顺序表中有一 个对象序列 71],…, v[n-1]。其中1],…, v[i-l] 是已经排好序的对象。在插入 i 时利用折半搜索法寻找 vij的插入位置 3、希尔排序 基本思想:对待排记录序列先作“宏观”调整再作“微观”调整。所谓“宏观”调整指的是“跳跃式”的插入排序。 具体做法 例 1.2、交换排序法 交换排序是通过交换进行排序的方法基本思想是两两比较待排序对象的关键字如果发生逆序(即排列顺序与排序后的次序正好相反)则交换之直到所有对象都排好序为止。 1、起泡排序 起泡排序的基本方法是:设待排序对象序列中的对象个数为n。最多作 n-1 趟排序。在第 i 趟中顺次两两比较r[j-1].Key和r[j].Keyj i,i1…,n-i-1。如果发生逆序则交换r[j-1]和r[j]。 起泡排序的过程
起泡排序的结束条件为最后一趟没有进行“交换记录一般情况下每经过一趟“起泡”“i 减一”.(但并不是每趟都如此)
2、快速排序
一趟快速排序 (一次划分)。 目标找一个记录R[i]以它的关键字作为“枢轴”’凡其关键字小于枢轴的记录均移动至该记录之前反之凡关键字大于枢轴的记录均移动至该记录之后 例 具体实现 快速排序的效率 当数据量较大时效率较高数据量较小时反而慢。
1.3 选择类排序
1、简单选择排序 效率分析
二、业务逻辑算法设计
2.1 基本概念和术语
1、查找表
2、关键字 3、查找 4、平均查找长度Average Search Length):
2.2 静态查找表
使用线性表表示静态查找表。可用顺序或链式存储结构实现查找操作。 1、查找表的定义 2、基本操作 3、算法实现 4、算法“好”还是“坏”衡量
讨论各种查找算法时常以算法的效率和存储开销来衡量查找算法的优劣。然而效率和存储开销常常是相互制约的很难两者兼顾。效率只是相对的通常把对关键字的最多比较次数和平均比较次数作为两个基本的技术指标前者叫做最大查找长度(MSLMaximum Search Length)后者叫做平均查找长度(ASLAverageSearch Length)
2.3、有序表的查找
上述顺序查找表中的查找算法简单但平均查找长度较大特别不适用于表长较大的查找表。若以有序表表示静态查找表则查找过程可以基于“折半”进行
1、折半查找 写在最后 课看完了只能说质量不高全程PPT没意思就当记录笔记吧。。。。
