做国内电影网站赚钱不山东专业网站开发公司

当前位置： 首页 > news >正文

做国内电影网站赚钱不,山东专业网站开发公司,网站改版不收录,河南比较出名的外贸公司8.排序 8.1排序的概念 什么是排序#xff1f; 排序#xff1a;将一组杂乱无章的数据按一定规律顺序排列起来。即#xff0c;将无序序列排成一个有序序列#xff08;由小到大或由大到小#xff09;的运算。 如果参加排序的数据结点包含多个数据域#xff0c;那么排序往…8.排序 8.1排序的概念 什么是排序 排序将一组杂乱无章的数据按一定规律顺序排列起来。即将无序序列排成一个有序序列由小到大或由大到小的运算。 如果参加排序的数据结点包含多个数据域那么排序往往是针对其中某个域而言。
排序方法的分类 按存储介质可分为 内部排序数据量不大、数据在内存无需内外存交换数据 外部排序数据量较大、数据在外存文件排序 ​ 外部排序时要将数据分批调入内存在排序中间结果还要及时放入外存显然外部排序要复杂得多。 按比较器个数可分为 串行排序单处理机同一时刻比较一对元素并行排序多处理机同一时刻比较多对元素 按主要操作可分为 比较排序用比较的方法 ​ 插入排序、交换排序、选择排序、归并排序 基数排序不比较元素的大小仅仅根据元素本身的取值确定其有序位置。 按辅助空间可分为 原地排序辅助空间用量为O(1)的排序方法。 ​ 所占的辅助存储空间与参加排序的数据量大小无关 非原地排序辅助空间用量超过O(1)的排序方法。 按稳定性可分为 稳定排序能够使任何数值相等的元素排序以后相对次序不变。非稳定性排序不是稳定排序的方法。 按自然性可分为 自然排序输入数据越有序排序的速度越快的排序方法。非自然排序不是自然排序的方法。
存储结构——记录序列以顺序表存储 #define MAXSIZE 20 typedef int KeyType;//设关键字为整型量int型Typedef struct{//定义每个记录数据元素的结构KeyType key;//关键字InfoType otherinfo;//其他数据项 }RedType;Typedef struct{//定义顺序表的结构RedType r[MAXSIZE1];//存储顺序表的向量int length;//r[0]一般作哨兵或缓冲区 }SqList;8.2插入排序 基本思想每一步将一个待排序的对象按其关键码大小插入到前面已经排好序的一组对象的适当位置上直到对象全部插入为止。 即边插遍排序保证子序列中随时都是排好序的 基本操作有序插入 在有序序列中插入一个元素保持序列有序有序长度不断增加。起初a[0]是长度为1的子序列。然后逐一将a[1]至a[n-1]插入到有序子序列中。 有序插入方法 在插入a[i]前数组a的前半段a[0]~a[i-1]是有序段后半段a[i] ~a[n-1]是停留于输入次序的无序段。在插入a[i]使a[0]~a[i-1]有序也就是要为a[i]找到有序位置j(0≤j≤i)将a[i]插入在a[j]的位置上。 插入排序的种类 ​ 顺序法定位插入位置————直接插入排序 ​ 二分法定位插入位置————二分插入排序 ​ 缩小增量多遍插入排序————希尔排序 8.2.1直接插入排序 直接插入排序——采用顺序查找法查找插入位置 复制插入元素记录后移查找插入位置插入到正确位置 xa[i]; for(ji-1;j0xa[j];j–)a[j1]a[j]; a[j-1]x;直接插入排序使用“哨兵” 复制为哨兵记录后移查找插入位置插入到正确位置 L.r[0]L.r[i]; for(ji-1;L.r[0].keyL.r[j].key;–j)L.r[j1]L.r[j]; L.r[j1]L.r[0];void InsertSort(SqList L){int i,j;for(i2;iL.length;i){if(L.r[i].keyL.r[i-1].key){//若“”,需将L.r[i]插入有序子表L.r[0]L.r[i];//复制为哨兵for(ji-1;L.r[0].keyL.r[j].key;–j){L.r[j1]L.r[j];//记录后移}L.r[j1]L.r[0];//插入到正确位置}} }实现排序的基本操作有两个 比较序列中两个关键字的大小移动记录。 直接插入排序在什么情况下效率比较高 ​ 直接插入排序在基本有序时效率较高 ​ 在待排序的记录个数较少时效率较高 8.2.2折半插入排序 查找插入位置时采用折半查找法 void BInsertSort(SqList L){for(i2;iL.length;i){//依次插入第2~第n个元素L.r[0]L.r[i];//当前插入元素存到“哨兵”位置low1;highi-1;while(lowhigh){mid(midhigh)/2;if(L.r[0].keyL.r[mid].key)highmid-1;else lowmid1;}//循环结束high1则为插入位置for(ji-1;jhigh1;–j)L.r[j1]L.r[j];L.r[high1]L.r[0];} }算法分析 折半查找比顺序查找快所以折半插入排序就平均性能来说比直接插入排序要快它所需要的关键码比较次数与待排序对象序列的初始排序无关仅依赖于对象个数。在插入第i个对象时需要经过[log2i]1次关键码比较才能确定它应插入的位置 当n较大时总关键码比较次数比直接插入排序的最坏情况要好得多但比其最好情况要差在对象的初始排序已经按关键码排好序或接近有序时直接插入排序比折半插入排序执行的关键码比较次数要少 折半插入排序的对象移动次数与直接插入排序相同依赖于对象的初始排列 减少了比价次数但没有减少移动次数平均性能优于直接插入排序
8.2.3希尔排序 基本思想先将整个待排记录序列分割成若干个系列分别进行直接插入排序待整个序列中的记录“基本有序”时再对全体记录进行一次直接插入排序。 希尔排序算法特点 缩小增量多遍插入排序 希尔排序特点 一次移动移动位置较大跳跃式地接近排序后的最终位置最后一次只需要少量移动增量序列必须是递减的最后一个必须是1增量序列应该是互质的 希尔排序算法主程序 void ShellSort(Sqlist L,int dlta[],int t){//按增量序列dlta[0..t-1]对顺序表L作希尔排序。for(k0;kt;k)ShellInsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序 }void ShellInsert(SqList L,int dk){//对顺序表L进行一趟增量为dk的Shell排序dk为步长因子for(idk1;iL.length;i){if(r[i].keyr[i-dk].key){r[0]r[i];for(ji-dk;j0(r[0].keyr[j].key);jj-dk)r[jdk]r[j];r[jdk]r[0];}} }希尔排序算法分析 希尔排序是一种不稳定的排序方法 如何选择最佳d序列目前尚未解决 最后一个增量值必须为1无除了1之外的公因子不宜在链式存储结构上实现
8.3交换排序 基本思想两两比较如果发生逆序则交换直到所有记录都排好序为止。 常见额交换排序方法 ​ 冒泡排序O(n2) ​ 快速排序O(nlog2n) 8.3.1冒泡排序 冒泡排序——基于简单交换思想 基本思想每趟不断将记录两两比较并按“前小后大”规则交换 总结n个记录总共需要n-1趟 第m趟需要比较 n-m次 void bubble_sort(SqList L){int m,i,j;RedType x;//交换时临时存储for(m1;mn-1;m){//总共需m趟for(j1;jn-m;j)if(L.r[j].keyL.r[ji].key){//发生逆序xL.r[j];L.r[j]L.r[j1];L.r[j1]x;//交换}} }优点每趟结束时不仅能挤出一个最大值到最后面位置还能同时部分理顺其他元素 如何提高效率 ​ 一旦某一趟比较时不出现记录交换说明已排好序了就可以结束本算法。 改进的冒泡排序算法 void bubble_sort(SqList L){int m,i,j,flag1;RedType x;//flag作为是否有交换的标记for(m1;mn-1flag1;m){flag0;for(j1;jm;j)if(L.r[j].keyL.r[j1].key){//发生逆序flag1;//发生交换flag置为1若本趟没发生交换flag保持为0xL.r[j];L.r[j]L.r[j1];L.r[j1]x;//交换}} }8.3.2快速排序 快速排序——改进的交换排序 基本思想 任取一个元素如第一个为中心所有比它小的元素一律前放比它大的元素一律后放形成左右两个子表对各子表重新选择中心元素并依次规则调整直到每个子表的元素只剩一个 基本思想通过一趟排序将待排序记录分割成独立的两部分其中一部分记录的关键字均比另一部分记录的关键字小则可分别对这两部分记录进行排序以达到整个序列有序。 具体实现选定一个中间数作为参考所有元素与之比较小的调到其左边大的调到其右边。 枢轴中间数可以是第一个数、最后一个数、最中间一个数、任选一个数等。 每一趟的子表的形成是采用从两头向中间交替式逼近法由于每趟中对各子表的操作都相似可采用递归算法 void main(){QSort(L,1,L.length); }void QSort(SqList L,int low,int high){if(lowhigh){//长度大于1pivotlocPartition(L,low,high);//将L.r[low..high]一分为二pivotloc为枢轴元素排好序的位置QSort(L,low,pivotloc-1);//对低子表递归排序QSort(L,pivotloc1,high);//对高子表递归排序} }int Partition(SqList L,int low,int high){L.r[0]L.r[low];pivotkeyL.r[low].key;while(lowhigh){while(lowhighL.r[high].keypivotkey)–high;L.r[low]L.r[high];while(lowhighL.r[low].keypivotkey)low;L.r[high]L.r[low];}L.r[low]L.r[0];return low; }快速排序算法分析 时间复杂度 可以证明平均计算时间是0(nlog2n)。 QsortO(log2n)PartitionO(n) 实验结果表明就平均计算时间而言快速排序是我们所讨论的所有排序方法中最好的一个 空间排序 快速排序不是原地排序 ​ 由于程序中使用了递归需要递归调用栈的支持而栈的长度取决于递归调用的深度。即使不用递归也需要用用户栈 在平均情况下需要O(logn)的栈空间最坏情况下栈空间可达O(n) 稳定性快速排序是一种不稳定的排序方法 ​ 由于每次枢轴记录的关键字都是大于其它所有记录的关键字致使一次划分之后得到的子序列1的长度为0这时已经退化成为没有改进措施的冒泡排序。 快速排序不适于对原本有序或基本有序的记录序列进行排序。 划分元素的选取是影响时间性能的关键 输入数据次序越乱所选划分元素值的随机性越好排序适度越快快速排序不是自然排序方法。 改变划分元素的选取方法至多只能改变算法平均情况下的世界性能无法改变最坏情况下的时间性能。即最坏情况下快速排序的时间复杂性总是O(n2) 8.4选择排序
8.4.1简单选择排序 基本思想在待排序的数据中选出最大小的元素放在其最终的位置。 基本操作 首先通过n-1次关键字比较从n个记录中找出关键字最小的记录将它与第一个记录交换再通过n-2次比较从剩余的n-1个记录中找出关键字次小的记录将它与第二个记录交换重复上述操作共进行n-1趟排序后排序结束 void SelectSort(SqList K){for(i1;iL.length;i){ki;for(ji1;jL.length;j)if(L.r[j].keyL.r[k].key) kj;//记录最小值位置if(k!i)L.r[i]←→L.r[k];//交换} }时间复杂度 记录移动次数 最好情况0最坏情况3n-1 比较次数无论待排序处于什么状态选择排序所需进行的“比较”次数都相同 算法稳定性 简单选择排序是不稳定排序 8.4.2堆排序 则分别称该序列{a1 a2 … an}为小根堆和大根堆。 ​ 从堆的定义可以看出堆实质是满足如下性质的完全二叉树二叉树中任一非叶子结点均小于大于它的孩子结点。。 堆排序若在输出堆顶的最小值最大值后使得剩余n-1个元素的序列重新又建成一个堆则得到n个元素的次小值次大值……如此反复便能得到一个有序序列这个过程称之为堆排序。 实现堆排序需解决两个问题 如何由一个无序序列建成一个堆如何在输出堆顶元素后调整剩余元素为一个新的堆 小根堆 输出堆顶元素之后以堆中最后一个元素替代之然后将根节点值与左、右子树的根结点值进行比较并与其中小者进行交换重复上述操作直至叶子结点将得到新的堆称这个从堆顶至叶子的调整过程为“筛选” 堆的调整 筛选过程的算法描述为 void HeapAdjust(elem R[],int s,int m){/已知R[s..m]中记录的关键字除R[s]之外均满足堆的定义本函数调整R[s]的关键字使R[s..m]成为一个大根堆/rcR[s];for(j2*s;jm;j*2){//沿key较大的孩子结点向下筛选if(jmR[j]R[j1])//j为key较大的记录的下标j;if(rcR[j]) break;R[s]R[j];//rc应该插入在位置s上sj;}R[s]rc;//插入 }可以看出 ​ 对一个无序序列反复“筛选”就可以得到一个堆即从一个无序序列建堆的过程就是一个反复“筛选”的过程。 如何由无序序列建成一个堆 ​ 单结点的二叉树是堆 ​ 在完全二叉树中所有以叶子结点序号in/2为根的子树是堆。 ​ 这样我们只需依次将以序号为n/2n/2-1……1的结点为根的子树均调整为堆即可。 ​ 即对应由n个元素组成的无序序列“筛选”只需从第n/2个元素开始。 由于堆实质上是一个线性表那么我们可以顺序存储一个堆。 从最后一个非叶子结点开始以此向前调整 调整从第n/2个元素开始将以该元素为根的二叉树调整为堆将以序号为n/2-1的结点为根的二叉树调整为堆再将以序号为n/2-2的结点为根的二叉树调整为堆再将以序号为n/2-3的结点为根的二叉树调整为堆 由以上分析知 ​ 若对一个无序序列建堆然后输出根重复该过程就可以由一个无序序列输出有序序列。 ​ 实质上堆排序就是利用完成二叉树中父结点与孩子结点之间的内在关系来排序的。 堆排序算法如下 void HeapSort(elem R[]){//对R[1]到R[n]进行堆排序int i;for(in/2;ii;i–)HeapAdjust(R,i,n);//建初始堆for(in;i1;i–){//进行n-1趟排序Swap(R[1],R[i]);//根与最后一个元素交换HeapAdjust(R,1,i-1);//对R[1]到R[i-1]重新建堆} }堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复筛选上。堆排序在最坏情况下其时间复杂度也为Onlog2n,这是堆排序的最大优点。无论待排序中的记录是正序还是逆序排序都不会使堆排序处于“最好”或“最坏”的状态。另外堆排序仅需一个记录大小供交换用的辅助存储空间。然而堆排序是一种不稳定的排序方法它不使用于待排序记录个数n较少的情况但对于n较大的文件还是很有效的。 8.5归并排序 基本思想将两个或两个以上的有序子序列“归并”为一个有序序列。 在内部排序中通常采用的是2-路归并排序。 即将两个位置相邻的有序子序列R[l…m]和R[m1…n]归并为一个有序序列R[l…n] 关键问题如何将两个有序序列合成一个有序序列 8.6基数排序 基本思想分配收集 也叫桶排序或箱排序设置若干个箱子将关键字为k的记录放入第k个箱子然后在按序号将非空的连接。 基数排序数字是有范围的均由0-9这十个数字组成则只需设置十个箱子相继按个、十、百…进行排序。 8.7各种排序方法比较 一、时间性能 按平均的时间性能来分有三类排序方法 时间复杂度为O(nlogn)的方法有、 快速排序、堆排序和归并排序其中以快速排序为最好 时间复杂度为O(n2)的有 直接插入排序、冒泡排序和简单选择排序其中以直接插入为最好特别是对那些对关键字近似有序的记录序列尤为如此 时间复杂度为O(n)的排序方法只有基数排序。 当待排记录序列按关键字顺序有序时直接插入排序和冒泡排序能达到O(n)的时间复杂度而对于快速排序而言这是最不好的情况此时的时间性能退化为O(n2)因此是应该尽量避免的情况。简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 二、空间性能 ​ 指的是排序过程中所需的辅助空间大小 所有的简单排序方法包括直接插入、冒泡和简单选择和堆排序的空间复杂度为O(1)快速排序为O(logn)为栈所需的辅助空间归并排序所需辅助空间最多其空间复杂度为O(n)链式基数排序需附设队列首尾指针则空间复杂度为O(rd) 三、排序方法的稳定性能 稳定的排序方法指的是对于两个关键字相等的记录它们在序列中的相对位置在排序之前和经过排序之后没有改变。当对多关键字的记录序列进行LSD方法排序时必须采用稳定的排序方法。对于不稳定的排序方法只要能举出一个实例说明即可。快速排序和堆排序是不稳定的排序方法。 四、关于“排序方法的时间复杂度的下限” 本章讨论的各种排序方法除基数排序外其它方法都是基于“比较关键字”进行排序的排序方法可以证明这类排序法可能达到的最快的时间复杂度为O(nlogn)。 基数排序不是基于“比较关键字”的排序方法所以它不受这个限制 可以用一棵判定树来描述这类基于“比较关键字”进行排序的排序方法。