专业积分商城网站建设,外贸网站建设服务机构,沙坪坝网站建设,做网站如何写需求文章目录1、基本概念1.1 什么是排序1.2 排序算法的稳定性1.3 排序算法的分类1.4 内排序的方法2、插入排序2.1 直接插入排序2.2 直接插入排序2.3 希尔排序3、交换排序3.1 冒泡排序3.2 快速排序4、选择排序4.1 简单选择排序4.2 树形选择排序4.3 堆排序4.4 二路归并排序5、基数排序…
文章目录1、基本概念1.1 什么是排序1.2 排序算法的稳定性1.3 排序算法的分类1.4 内排序的方法2、插入排序2.1 直接插入排序2.2 直接插入排序2.3 希尔排序3、交换排序3.1 冒泡排序3.2 快速排序4、选择排序4.1 简单选择排序4.2 树形选择排序4.3 堆排序4.4 二路归并排序5、基数排序5.1 链式基数排序6、各种内部排序方法的比较【说明】 大家好本专栏是
数据结构与算法
该科目是计算机类专业必修课之一比较重要也比较基础有想从事算法研究的同学这些内容是专/本科、甚至硕士期间较为基础的内容适用范围较广大学专业课学习、考研复习等。通过自己的理解进行整理希望大家积极交流、探讨多给意见。后面也会给大家更新其他一些知识。若有侵权联系删除共同维护网络知识权利1、基本概念
1.1 什么是排序 给定一个记录集合( r1,r2,…,rn)其相应的关键码分别为(k1,k2,…,kn)排序是将这些记录排成顺序为(rs1,rs2,…,rsn)的一个序列使得相应的关键码满足ks1≤ks2≤…≤ksn(非降序或升序)或ks1≥ks2≥…≥ksn非升序或降序。
1.2 排序算法的稳定性 若对任意的数据元素序列使用某个排序方法对它按关键码进行排序 (1) 若相同关键码元素间的位置关系排序前与排序后保持一致称此排序方法是稳定的 (2) 不能保持一致的排序方法则称为不稳定的
1.3 排序算法的分类 (1) 内排序和外排序 按照参加排序的数据元素记录是否全部放置在内存中可把排序分为内排序和外排序 内排序指待排序列完全存放在内存中所进行的排序过程适合不太大的元素序列。 外排序指排序过程中还需访问外存储器足够大的元素序列因不能完全放入内存只能使用外排序。 (2) 单键排序和多键排序 按照排序所依据的关键码的个数可以把排序分为单键排序和多键排序。 单键排序根据一个关键码进行的排序。 多键排序根据多个关键码进行的排序。 (3) 基于比较和不基于比较 按照排序的方法是否建立在关键码比较的基础上可以把排序分为 基于比较主要是通过关键码之间的比较和记录的移动这两种操作来实现的排序。 不基于比较根据待排序数据的特点所采取的其它方法通常是没有大量的关键码之间的比较和记录的移动操作的排序。
1.4 内排序的方法 内部排序的过程是一个逐步扩大记录的有序序列长度的过程。 内排序有如下几大类: 下面对各种排序算法做个详细介绍: 2、插入排序
2.1 直接插入排序 算法思想仅有一个记录的表总是有序的因此对于n个记录的表可从第二个记录开始直到第n个记录逐个向有序表中进行插入操作从而得到n个记录按关键码有序的表。 步骤 (1) 从第一个元素开始该元素可以认为已经被排序 (2) 取出下一个元素在已经排序的元素序列中从后向前扫描 (3) 如果该元素已排序大于新元素将该元素移到下一位置 (4) 重复步骤3直到找到已排序的元素小于或者等于新元素的位置 (5) 将新元素插入到该位置后 (6) 重复步骤2~5。 算法分析 空间效率仅用了一个辅助单元O(1)。 时间效率 最好情况下初始序列是顺序的 最坏情况下初始序列是逆序的 平均情况下初始序列是无序的 稳定性是一种稳定的排序方法。 2.2 直接插入排序 算法思想设在顺序表中有一 个对象序列 V[0], V[1], …, V[n-1]。其中, V[0], V[1], …, V[i-1] 是已经排好序的对象。在插入V[i] 时, 利用折半查找法寻找V[i] 的插入位置。 步骤 折半插入排序与直接插入排序算法原理相同。只是在向已排序的数据中插入数据时采用来折半查找二分查找。先取已经排序的序列的中间元素与待插入的数据进行比较如果中间元素的值大于待插入的数据那么待插入的数据属于数组的前半部分否则属于后半部分。依次类推不断缩小范围确定要插入的位置。 Step1: 顺序表中前j-1个记录有序将第j个记录插入。令low1highj-1r[0]r[j] Step2: 若lowhigh得到插入位置转Step5; Step3: 若low≤high则取有序子表的中点m(lowhigh)/2 Step4: 若r[0].keyr[m].key则插入位置在低半区令highm-1否则插入位置在高半区令lowm1转Step2; Step5: high1即为待插入位置从j-1到high1的记录逐个后移r[high1]r[0]放置待插入记录。 案例 (1) 待排序数据21674 取第一个元素作为有序表剩余的元素作为无序表其中有序表2无序表1674 (2) 第一次比较从无序表中取出第一个数 1与中间值2比较121插到2的前面得到有序表12无序表674 (3) 第二次比较从无序表中取出第一个数 6与中间值1比较61要放在1的后面再与后半区有序表2的中间值2比较626插入到2的后面得到 有序表126无序表74 (4) 第三次比较从无序表中取出第一个数 7与中间值2比较727放在2后面再与后半区有序表6的中间值6比较767放在6后面得到有序表1267无序表4 (5) 第四次比较从无序表中取出第一个数 4与中间值2比较424放在2后面再与后半区有序表:6,7的中间值6比较464放在6前面最终得到12467 算法分析 时间复杂度O(n2n^2n2)。 空间复杂度O(1)。 稳定性是一种稳定的排序方法。 2.3 希尔排序 算法思想先将整个待排记录分割成若干个子序列在子序列中分别进行直接插入排序待整个序列基本有序的时候再对全体序列进行一次直接插入排序。 步骤 Step1: 选择一个步长序列t1t2…tk其中 titjtk1 Step2: 按步长序列个数k对序列进行k趟排序 Step3: 每趟排序根据对应的步长ti将待排序列分割成若干长度为m的子序列分别对各子表进行直接插入排序。仅步长因子为1时整个序列作为一个表来处理表长度即为整个序列的长度。 案例 算法分析 时间复杂度由于希尔排序是依赖于增量的选取它的时间复杂度是在O(nlog2n)-O(n2n^2n2)之间。 空间复杂度在希尔排序的过程中只需要一个辅助空间用于暂存当前待插入的记录因此希尔排序的空间复杂度为O(1)。 稳定性希尔排序方法是一种不稳定的排序方法。 3、交换排序
3.1 冒泡排序 算法思想对n个记录的表第一趟冒泡得到一个关键码最大的记录r[n]第二趟冒泡对n-1个记录的表再得到一个关键码最大的记录r[n-1]如此重复直到n个记录按关键码有序的表。 步骤 (1) 比较相邻的元素。如果第一个比第二个大就交换它们两个 (2) 对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对这样在最后的元素应该会是最大的数 (3) 针对所有的元素重复以上的步骤除了最后一个 (4) 重复步骤1~3直到排序完成。 一趟冒泡方法 Step1: i1 //设置从第一个记录开始进行两两比较 Step2: 若i≥j一趟冒泡结束。 Step3: 比较r[i].key与r[i1].key若 r[i].key≤r[i1].key不交换转Step5; Step4: 当r[i].keyr[i1].key时 r[0]r[i]r[i]r[i1]r[i1]r[0] // 将r[i]与r[i1]交换 Step5: ii1对下两个记录进行两两比较转Step2; 算法分析 空间复杂度冒泡排序的空间复杂度为O(1)。 时间复杂度总共要进行n-1趟冒泡对j个记录的表进行一趟冒泡需要j-1次关键码比较。 冒泡排序的时间复杂度为O(n2n^2n2)。 稳定性冒泡排序是一种稳定的排序方法。 3.2 快速排序 算法思想找一个记录以它的关键字作为“枢轴”凡其关键字小于枢轴的记录均移动至该记录之前反之凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后记录的无序序列R[s…t]将分割成两部分R[s..i-1]和R[i1..t]且R[j].key≤ R[i].key ≤ R[j].key (s≤j≤i-1) 枢轴 (i1≤j≤t)。 步骤 Step1: 如果待排子序列中元素的个数大于1则以L.r[low]作为枢轴进行一次划分否则排序结束。 Step2: 对枢轴左半子序列重复Step1; Step3: 对枢轴右半子序列重复Step1; 案例 算法分析 空间复杂度快速排序是递归的递归调用层次数与其二叉树的深度一致。因而存储开销在理想情况下为O(log2n)在最坏情况下为O(n)。 时间复杂度最好情况下为O(nlog2n) 最坏情况快速排序蜕化为冒泡排序。 稳定性快速排序是一个不稳定的排序方法。 4、选择排序
4.1 简单选择排序 算法思想第一趟从n个记录中找出关键码最小的记录与第一个记录交换第二趟从第二个记录开始的n-1个记录中再选出关键码最小的记录与第二个记录交换如此第i趟则从第i个记录开始的n-i1个记录中选出关键码最小的记录与第i个记录交换直到整个序列按关键码有序。 步骤 Step1: 从L.key[i]~ 从L.key[length]记录中选择一个关键字值最小的记录将其下标保存至min中 Step2: 若L.key[i]≥L.key[min];则交换这两个记录;否则转Step3; Step3: ii1,若i≤L.length则转Step1;否则排序结束。 算法分析 时间复杂度从算法中可看出简单选择排序移动记录的次数较少但关键码的比较次数依然是算法的时间复杂度仍是O(n2n^2n2)。 空间复杂度简单选择排序算法只需要一个辅助空间来作为交换记录用的暂存单元。因此它的空间复杂度O(1)。 稳定性简单选择排序是一种不稳定的排序方法。 4.2 树形选择排序 步骤 Step1:从最底层叶子结点开始按层一一进行兄弟间的比赛关键字值较大者上升为子树根结点直到树的顶层为止 Step2:将树的根结点输出把底层叶子中值相同的结点值改为0如果输出的结点总数小于初始时树的叶子结点总数则重复Step1;否则结束排序。 案例 首先对n个记录的关键字两两进行比较然后在n/2个较小者之间再进行两两比较如此重复直至选出最小关键字的记录。整个过程可用一个含有n个叶结点的二叉树表示 选出最小记录后将树中的该最小记录修改为∞然后从该叶子结点所在子树开始修改到达树根的路径上的结点 算法分析 时间复杂度除了最大关键字之外每选择一个次大的关键字只需要进行log2n次比较因此它的时间复杂度为O(nlogn)。 空间复杂度需要附加n个辅助空间用来保存排序的结果还要n-1个辅助空间作为排序过程中使用。因此它的空间复杂度O(n)。 稳定性树形选择排序是一种不稳定的排序方法。这是因为在比较的过程中是跳跃式进行的。 4.3 堆排序 定义 第一种定义方式 设有n个元素的序列 {k1k2…kn}当且仅当满足下述关系之一时称之为堆。 第二种定义方式 堆是具有下列性质的完全二叉树每个结点的值都小于或等于其左右孩子结点的值称为小根堆或小顶堆或者每个结点的值都大于或等于其左右孩子结点的值称为大根堆或大顶堆。 算法思想设有n个元素将其按关键码排序。首先将这n个元素按关键码建成堆将堆顶元素输出得到n个元素中关键码最小(或最大)的元素。然后再对剩下的n-1个元素建成堆输出堆顶元素得到n个元素中关键码次小(或次大)的元素。如此反复便得到一个按关键码有序的序列。称这个过程为堆排序。 堆排序需解决的两个问题 1.怎样建堆如何将n个元素的序列按关键码建成堆 2. 怎样调整输出堆顶元素后怎样调整剩余n-1个元素使其按关键码成为一个新堆。 建堆方法 (1) 先把待排序序列构造成一棵完全二叉树; (2) 然后从下往上,自右而左进行筛选,最终得到堆。 步骤 Step1: i1,对顺序表L[1…L.lengh-i1]中的建大顶堆 Step2: 将堆顶元素和L[L.lengh-i1]交换 Step3: ii1,若iL.lengh,则将L[1…L.lengh-i1]调整使之成为新的大顶堆转Step2;否则排序结束。 算法分析 时间复杂度在建好堆后排序过程中的筛选次数不超过 O(nlog2n)而建堆时的比较次数不超过4n次因此堆排序最坏情况下时间复杂度也为O(nlog2n)。 空间复杂度堆排序中只需要一个用来交换的暂存单元因此它的空间复杂度为O(1)。 算法的稳定性由于记录的比较和交换是跳跃式进行的因此堆排序是一种不稳定的排序方法。 4.4 二路归并排序 算法思想归并排序的基本思想是基于将两个或两个以上的有序子序列 “归并” 为一个有序序列。 步骤 Step1: 设置两个子表的起始下标及辅助数组的起始下标iujvku Step2: 若iv 或 jt则比较选取结束转Step4 Step3: 选取r[i]和r[j]中关键码较小的存入辅助数组rf。如果 r[i].keyr[j].key则rf[k]r[i] i k否则rf[k]r[j] j k。 转Step2; Step4: 将尚未处理完的子表中元素存入rf Step5: 合并结束。 递归算法操作步骤 Step1: 将待排序的记录序列分为两个相等的子序列分别将这两个子序列进行排序 Step2: 调用一次归并算法Merge将这两个有序子序列合并成一个含有全部记录的有序序列。 案例 算法分析 时间复杂度归并过程对应由叶向根生成一棵二叉树的过程所以归并趟数约等于二叉树的高度-1即log2n每趟归并需移动记录n次故时间复杂度为O(nlog2n)。 空间复杂度需要一个与表等长的辅助元素数组空间所以空间复杂度为O(n)。 稳定性由一次归并算法中的if语句可知二路归并算法是一种稳定的算法。 5、基数排序 基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。
5.1 链式基数排序 基数排序是按照低位先排序然后收集再按照高位排序然后再收集依次类推直到最高位。有时候有些属性是有优先级顺序的先按低优先级排序再按高优先级排序。最后的次序就是高优先级高的在前高优先级相同的低优先级高的在前。 案例 算法分析 时间效率设待排序列为n个记录d个关键码关键码的取值范围为radix则进行链式基数排序的时间复杂度为O(d(nradix)) 。 空间效率需要2*radix个指向队列的辅助空间以及用于静态链表的n个指针。 稳定性在基数排序的过程中并没有交换记录的前后位置因此该排序方法是一种稳定的排序方法。 6、各种内部排序方法的比较
