• 关于

    执行排序

    的搜索结果

回答

假设你有一组数字a=[1,2,5,3,4,6], 执行a.sort(),即可完成升序排序。如果想要降序排序,则执行a.sort(reverse=True)。 假设你有一组对象a=[ob1,ob2,ob3,ob4], 需要按照对象的某个特征值进行排序,我们记计算特征值的函数为f(obj), 则执行a.sort(key=lambda obj: f(obj)), 即可按照特征值排序。 其余需求如法炮制。

1056118620260801 2019-12-02 01:04:19 0 浏览量 回答数 0

回答

排序后的数组比为未排序的数组运行速率快,其实不是很确定这个“运行"具体指的什么类型的计算。尝试着回答下,如果对一组数据进行循环处理,每次循环都需要对当前游标对应的数值进行值判断,这个确实会发生,这个涉及到计算机指令流水线的工作原理,一条指令的执行都需要经过多个硬件的处理的阶段,比如取址、分析译码、执行等。为了提高指令执行效率,减少硬件资源闲置,多个指令可以叠加执行的,只要是处于不同的硬件阶段就可以,比如指令A执行到分析译码阶段,指令B可以执行取址,在这个过程中很多指令步骤是提前进行预测,如果排序好的数据预测命中的概率会大很多(比如指令是跟一个固定值的比较),而不规律的数据预测失手的概率会大很多,需要重新恢复。这个问题基本上跟java语言无关,跟机器指令运行方式有关。

talishboy 2019-12-02 01:46:46 0 浏览量 回答数 0

问题

冒泡排序法最多执行多少次?

知与谁同 2019-12-01 20:11:33 1242 浏览量 回答数 1

阿里云试用中心,为您提供0门槛上云实践机会!

0元试用32+款产品,最高免费12个月!拨打95187-1,咨询专业上云建议!

回答

直接插入排序:当数据有序时,执行效率最好,此时的时间复杂度为O(n);当数据基本反序时,执行效率最差,此时的时间复杂度为O(n2)。所以当数据越接近有序,直接插入排序算法的性能越好。 希尔排序 :时间效率为O(n(log2n)2) 直接选择排序:时间效率为 O(n^2)——虽移动次数较少,但比较次数仍多。 堆排序:时间效率为O(nlog2n) 冒泡排序:时间效率为O(n^2) —因为要考虑最坏情况(数据元素全部逆序),当然最好情况是数据元素已全部排好序,此时循环n-1次,时间复杂度为O(n) 快速排序: 时间效率:一般情况下时间复杂度为O(nlog2n),最坏情况是数据元素已全部正序或反序有序,此时每次标准元素都把当前数组分成一个大小比当前数组小1的子数组,此时时间复杂度为O(n2)

寒凝雪 2019-12-02 01:17:21 0 浏览量 回答数 0

回答

olatile 除了指令重排,还有一个可见性。volatile 的禁止指令重排序优化和可见性,是它的两种特性,volatile 的禁止指令重排序优化 。这个本来是在多线程情况下,CPU的执行指令优化。你把他放在单线程和单CPU环境讨论,意义本来就不大。instance = new Singleton() 这一行其实有三步 1.instance内存分配 2.构造函数初始化对象 3.将instance指向分配的内存空间。jvm的指令重排序可能会导致2 3的顺序不能保证 若3在2之前 即3执行完了2还没执行 被另一个线程抢去 这时线程2认为instance已经是非null,并使用 则会报错

景凌凯 2020-04-24 16:46:11 0 浏览量 回答数 0

问题

如何在Visual Basic 6 ListView上进行多列排序?

心有灵_夕 2019-12-26 22:21:21 0 浏览量 回答数 1

回答

对于排序算法,平均时间复杂度插入排序O(n^2)冒泡排序O(n^2)选择排序O(n^2)快速排序O(nlogn)堆排序O(nlogn)归并排序O(nlogn)基数排序O(n)希尔排序O(n^1.25)有一个时间复杂度的排列顺序,依次为Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)Ο(1)表示基本语句的执行次数是一个常数,一般来说,只要算法中不存在循环语句,其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间,而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法,把这类问题称为P类问题,而把后者称为NP问题。

晚来风急 2019-12-02 01:17:53 0 浏览量 回答数 0

回答

1.让JavaScript暂停下来,慢下来。 JavaScript排序是很快的,要我们肉眼能看到它的实现过程,我首先想到的是让排序慢下来。 排序的每一个循环都让它停300ms然后再继续进行。 怎么样才能停下来呢。查了一下JavaScript貌似没有sleep()这样的函数。暂停做不到,但是可以想办法让实现跟暂停差不多的效果。比如在循环里做一些无关的事情 。 首先尝试了让while(true)来一直执行一个空操作。执行一段时间再回到排序逻辑。代码大致是这样: for (var i = 0; i < 3; i++) { document.writeln(i); //DOM操作 var now = new Date().getTime(); while(new Date().getTime() - now < 3000){} } 慢是慢下来了。不过太耗资源,排序进行过程中dom并不会有任何改变,直到排序结束, DOM会变成排序好之后的样子。 但是如果设置断点一步步执行的时候 又可以看到一步步的排序变化。估计是因为这个操作太耗资源导致浏览器下达了一个DOM操作的命令但是一直腾不出资源来进行DOM操作。所以真正DOM操作的时候在js代码执行结束之后。 所以让JavaScript排序慢来来还是没有实现。 另一种让JavaScript暂停下来的思路: 写这个文章的时候又想到一种方法来让JavaScript停下来。 那就是AJAX的同步请求,以及超时操作。 也就是在要停下来的地方放一个AJAX请求,同步请求, 然后设置超时。超时的时间就是我们要暂停的时间。为了避免在到达超时请求之前服务 器就返回了我们的AJAX请求。可以在服务端运行类似 sleep()的程序 。从而保证AJAX不会返回。直接超时然后返回到我们的循环。不过这只是个设想。有兴趣的可以去尝试一下。 2.闭包和定时器。 这种思路不需要让排序过程慢下来。而是使用闭包缓存排序过程中数组的变化。然后使用setTimeout来确定展示每一个数组状态的顺序。在排序循环中放入类似下面的代码。 (function(){ var theArr = arr.slice();//当前数组状态的备份 setTimeout(function(){ bubbleSortDom(theArr);//排序的DOM操作。 },500*timeCount); timeCount++;//定时器的顺序。 })(); 不过后来发现这样子写的话代码量会比较大,逻辑有修改的话要修改的地方会有点多。局限性很多,比如要实现排序动画加快或减慢操作几乎是很困难的。所以还要另想办法。 3.缓存排序中的数组状态。 也就是在排序过程中。将数组的每一轮循环的状态保存到一个数组。然后再用这个数组依次将排序状态保存下来。 只需要在排序中加入一句就行。 this.pushHis(arr.slice(),i-1,j,k,temp); 这样就只需要一个setInterval()就可以了。并且可以很方便的实现动画的加快与减慢。逻辑也比较好理解 。 问题二:如何实现JavaScript排序动画的加快与减慢。 我们问题一使用的第三种方法。 得到一个保存了每一步排序状态的数组arr。 然后我们可以使用一个setInterval()定时器一步步展现排序状态。 如果要加快速度或减慢速度。就clearInterval(),修改定时器的执行间隔,重新setInterval(),从前一个定时器执行到数组中的位置开始执行。 问题三:对于使用递归实现的数组怎么办。 不是在原数组上进行操作的怎么办。 使用递归实现的排序。 可能并没有在一个数组上进行操作,只是最后返回一个排序好的数组出来。那么我们要如何获得排序中的数组的完整状态呢。 比如快速排序。 最开始不考虑动画,我的实现是这样的: function quickSort(arr){ var len = arr.length,leftArr=[],rightArr=[],tag; if(len<2){ return arr; } tag = arr[0]; for(i=1;i<len;i++){ if(arr[i]<=tag){ leftArr.push(arr[i]) }else{ rightArr.push(arr[i]); } } return quickSort(leftArr).concat(tag,quickSort(rightArr)); } 然后为了考虑动画,我改写了它的逻辑,让它在同一个数组上进行了实现。 其实是在递归的时候传入了当前的的子数组在原数组中的起始位置。从而在原数组上进行了操作。 用了两种方法来实现方式。在排序逻辑上略有不同。 第一种是先跟远处的对比。遇到比自己小的放到自己前面去。循环序号+1。比自己大的放到当前排序子数组的最后面去,循环序号不变。直到排列完成。 这种方法的缺点是即使是一个有序数组。它也会重新排。 第二种方法是 除了标记位,再设置一个对比位。 遇到比自己小的,放到前面去,标记位的位置+1,标记位与对比位之间所有的往后面移动一个位置。 遇到比自己大的。标记位不变,对比位+1。 这种方法的缺点是对数组进行的操作太多。优点是对有序数组不会再排。 方式一: function quickSort(arr,a,b,qArr){ var len = arr.length,leftArr=[],rightArr=[],tag,i,k,len_l,len_r,lb,ra,temp; if(a == undefined && b == undefined){ a = 0; b= arr.length-1;//初始化起始位置。 } if(qArr == undefined){ qArr = arr.slice(); } if((len == 2 && arr[0] == arr[1])||len<2){ return arr; } tag = qArr[a]; for (i = 1; i < len;) { if(qArr[a+i]<=tag){ leftArr.push(qArr[a+i]); qArr[a+i-1] = qArr[a+i]; qArr[a+i] = tag; k = a+i; i++; }else{ if(leftArr.length+rightArr.length == len-1){ break; } temp = qArr[a+i]; qArr[a+i] = qArr[b-rightArr.length]; qArr[b-rightArr.length] = temp; rightArr.push(temp); k = a+i-1; } this.pushHis(qArr.slice(),a,b,k); } len_l = leftArr.length; len_r = rightArr.length; if(len_l== 0){ lb = a; }else{ lb = a+len_l -1; this.sort(leftArr,a,lb,qArr); } if(len_r == 0){ ra = b; }else{ ra = b + 1 - len_r; this.sort(rightArr,ra,b,qArr) } return qArr } 方式二: function quickSort2(arr,a,b,qArr){ var len = arr.length,leftArr=[],rightArr=[],tag,i,j,k,temp,len_l,len_r,lb,ra; if(a == undefined && b == undefined){ a = 0; b= arr.length-1;//初始化起始位置。 } if(qArr == undefined){ qArr = arr.slice(); } if(len<2){ return arr; } if(len == 2 && arr[0] == arr[1]){ return arr; } tag = qArr[a]; for (i = 1,k = 0; i < len;) { if(qArr[a+i]>=tag){ rightArr.push(qArr[a+i]); i++; }else{ temp = qArr[a+i]; for(j = a+i;j>a+k;j--){ qArr[j] = qArr[j-1]; // this.pushHis(qArr.slice(),a,b,a+k); } qArr[a+k] = temp; leftArr.push(temp); k++; i++; } this.pushHis(qArr.slice(),a,b,a+k,i-1); } len_l = leftArr.length; len_r = rightArr.length; if(len_l== 0){ lb = a; }else{ lb = a+len_l -1; this.sort(leftArr,a,lb,qArr); } if(len_r == 0){ ra = b; }else{ ra = b + 1 - len_r; this.sort(rightArr,ra,b,qArr) } return qArr; } 具体的不同下面会有动画演示。 问题四:动画的流畅。 排序动画的DOM操作是很多的很快的。这里我做的优化只是让每一个排序步骤只涉及一个DOM操作。 全部由JavaScript拼接好,一次替换。类似下面的代码。 效果图: 主要实现了: 冒泡排序JavaScript动画演示 插入排序JavaScript动画演示 选择排序JavaScript动画演示 快速排序JavaScript动画演示 归并排序JavaScript动画演示 希尔排序JavaScript动画演示

liujae 2019-12-02 01:19:06 0 浏览量 回答数 0

回答

对于排序算法,平均时间复杂度 插入排序 O(n^2) 冒泡排序 O(n^2) 选择排序 O(n^2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 基数排序 O(n) 希尔排序 O(n^1.25) 有一个时间复杂度的排列顺序,依次为 Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)Ο(1)表示基本语句的执行次数是一个常数,一般来说,只要算法中不存在循环语句,其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间,而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法,把这类问题称为P类问题,而把后者称为NP问题。

知与谁同 2019-12-02 01:17:53 0 浏览量 回答数 0

回答

这个查询使用了scanAndOrder,该操作会消耗大量内存cpu资源,因为排序是在内存中执行的。复合索引的顺序改下可能可以解决: mongodb 复合索引字段顺序: 精确查找的字段,可能排序的字段;查询某个范围的字段,避免使用scanAndOrder ,scanAndOrder 会在内存中执行,而且慢,而且耗费CPU

落地花开啦 2019-12-02 01:43:31 0 浏览量 回答数 0

回答

本人学习数据结构时看到的不错的总结,共享一下了 文件有一组记录组成,记录有若干数据项组成,唯一标识记录的数据项称关键字; 排序是将文件按关键字的递增(减)顺序排列; 排序文件中有相同的关键字时,若排序后相对次序保持不变的称稳定排序,否则称不稳定排序; 在排序过程中,文件放在内存中处理不涉及数据的内、外存交换的称内部排序,反之称外部排序; 排序算法的基本操作:1)比较关键字的大小;2)改变指向记录的指针或移动记录本身。 评价排序方法的标准:1)执行时间;2)所需辅助空间,辅助空间为O(1)称就地排序;另要注意算法的复杂程度。 若关键字类型没有比较运算符,可事先定义宏或函数表示比较运算。 8.2插入排序 8.2.1直接插入排序 实现过程: void insertsort(seqlist R) { int i, j; for(i=2;i<=n;i++) if(R[i].key< R[i-1].key{ R[0]=R[i];j=i-1; do{R[j+1]=R[j];j--;} while(R[0].key R[j+1]=R[0]; } } 复制代码 算法中引入监视哨R[0]的作用是:1)保存 R[i] 复制代码 的副本;2)简化边界条件,防止循环下标越界。 关键字比较次数最大为(n+2)(n-1)/2;记录移动次数最大为(n+4)(n-1)/2; 算法的最好时间是O(n);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的稳定的排序; 8.2.2希尔排序 实现过程:是将直接插入排序的间隔变为d。d的取值要注意:1)最后一次必为1;2)避免d值互为倍数; 关键字比较次数最大为n^1.25;记录移动次数最大为1.6n^1.25; 算法的平均时间是O(n^1.25);是一种就地的不稳定的排序; 8.3交换排序 8.3.1冒泡排序 实现过程:从下到上相邻两个比较,按小在上原则扫描一次,确定最小值,重复n-1次。 关键字比较次数最小为n-1、最大为n(n-1)/2;记录移动次数最小为0,最大为3n(n-1)/2; 算法的最好时间是O(n);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的稳定的排序; 8.3.2快速排序 实现过程:将第一个值作为基准,设置i,j指针交替从两头与基准比较,有交换后,交换j,i。i=j时确定基准,并以其为界限将序列分为两段。重复以上步骤。 关键字比较次数最好为nlog2n+nC(1)、最坏为n(n-1)/2; 算法的最好时间是O(nlog2n);最坏时间是O(n^2);平均时间是O(nlog2n);辅助空间为O(log2n);是一种不稳定排序; 8.4选择排序 8.4.1直接选择排序 实现过程:选择序列中最小的插入第一位,在剩余的序列中重复上一步,共重复n-1次。 关键字比较次数为n(n-1)/2;记录移动次数最小为0,最大为3(n-1); 算法的最好时间是O(n^2);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的不稳定的排序; 8.4.2堆排序 实现过程:把序列按层次填入完全二叉树,调整位置使双亲大于或小于孩子,建立初始大根或小根堆,调整树根与最后一个叶子的位置,排除该叶子重新调整位置。 算法的最好时间是O(nlog2n);最坏时间是O(nlog2n);平均时间是O(nlog2n);是一种就地的不稳定排序; 8.5归并排序 实现过程:将初始序列分为2个一组,最后单数轮空,对每一组排序后作为一个单元,对2个单元排序,直到结束。 算法的最好时间是O(nlog2n);最坏时间是O(nlog2n);平均时间是O(nlog2n);辅助空间为O(n);是一种稳定排序; 8.6分配排序 8.6.1箱排序 实现过程:按关键字的取值范围确定箱子的个数,将序列按关键字放入箱中,输出非空箱的关键字。 在桶内分配和收集,及对各桶进行插入排序的时间为O(n),算法的期望时间是O(n),最坏时间是O(n^2)。 8.6.2基数排序 实现过程:按基数设置箱子,对关键字从低位到高位依次进行箱排序。 算法的最好时间是O(d*n+d*rd);最坏时间是O(d*n+d*rd);平均时间是O(d*n+d*rd);辅助空间O(n+rd);是一种稳定排序; 8.7各种内部排序方法的比较和选择 按平均时间复杂度分为: 1) 平方阶排序:直接插入、直接选择、冒泡排序; 2) 线性对数阶:快速排序、堆排序、归并排序; 3) 指数阶:希尔排序; 4) 线性阶:箱排序、基数排序。 选择合适排序方法的因素:1)待排序的记录数;2)记录的大小;3)关键字的结构和初始状态;4)对稳定性的要求;5)语言工具的条件;6)存储结构;7)时间和辅助空间复杂度。 结论: 1) 若规模较小可采用直接插入或直接选择排序; 2) 若文件初始状态基本有序可采用直接插入、冒泡或随机快速排序; 3) 若规模较大可采用快速排序、堆排序或归并排序; 4) 任何借助于比较的排序,至少需要O(nlog2n)的时间,箱排序和基数排序只适用于有明显结构特征的关键字; 5) 有的语言没有提供指针及递归,使归并、快速、基数排序算法复杂; 6) 记录规模较大时为避免大量移动记录可用链表作为存储结构,如插入、归并、基数排序,但快速、堆排序在链表上难以实现,可提取关键字建立索引表,然后对索引表排序。 附二: 第八章排序 ************************************************************************************* 记录中可用某一项来标识一个记录,则称为关键字项,该数据项的值称为关键字。 排序是使文件中的记录按关键字递增(或递减)次序排列起来。·基本操作:比较关键字大小;改变指向记录的指针或移动记录。 ·存储结构:顺序结构、链表结构、索引结构。 经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的,否则排序算法是不稳定的。 排序过程中不涉及数据的内、外存交换则称之为"内部排序"(内排序),反之,若存在数据的内外存交换,则称之为外排序。 内部排序方法可分五类:插入排序、选择排序、交换排序、归并排序和分配排序。 评价排序算法好坏的标准主要有两条:执行时间和所需的辅助空间,另外算法的复杂程序也是要考虑的一个因素。 ************************************************************************************* 插入排序:·直接插入排序: ·逐个向前插入到合适位置。 ·哨兵(监视哨)有两个作用: ·作为临变量存放 R[i] 复制代码 ·是在查找循环中用来监视下标变量j是否越界。 ·直接插入排序是就地的稳定排序。时间复杂度为O(n^2),比较次数为(n+2)(n-1)/2;移动次数为(n+4)(n-1)/2; ·希尔排序: ·等间隔的数据比较并按要求顺序排列,最后间隔为1。 ·希尔排序是就地的不稳定排序。时间复杂度为O(n^1.25),比较次数为(n^1.25);移动次数为(1.6n^1.25); 交换排序:·冒泡排序:·自下向上确定最轻的一个。·自上向下确定最重的一个。·自下向上确定最轻的一个,后自上向下确定最重的一个。 ·冒泡排序是就地的稳定排序。时间复杂度为O(n^2),比较次数为n(n-1)/2;移动次数为3n(n-1)/2; ·快速排序:·以第一个元素为参考基准,设定、动两个指针,发生交换后指针交换位置,直到指针重合。重复直到排序完成。 ·快速排序是非就地的不稳定排序。时间复杂度为O(nlog2n),比较次数为n(n-1)/2; 选择排序:·直接选择排序: ·选择最小的放在比较区前。 ·直接选择排序就地的不稳定排序。时间复杂度为O(n^2)。比较次数为n(n-1)/2; ·堆排序 ·建堆:按层次将数据填入完全二叉树,从int(n/2)处向前逐个调整位置。 ·然后将树根与最后一个叶子交换值并断开与树的连接并重建堆,直到全断开。 ·堆排序是就地不稳定的排序,时间复杂度为O(nlog2n),不适宜于记录数较少的文件。。 归并排序: ·先两个一组排序,形成(n+1)/2组,再将两组并一组,直到剩下一组为止。 ·归并排序是非就地稳定排序,时间复杂度是O(nlog2n), 分配排序:·箱排序: ·按关键字的取值范围确定箱子数,按关键字投入箱子,链接所有非空箱。 ·箱排序的平均时间复杂度是线性的O(n). ·基数排序:·从低位到高位依次对关键字进行箱排序。 ·基数排序是非就稳定的排序,时间复杂度是O(d*n+d*rd)。 各种排序方法的比较和选择: ·.待排序的记录数目n;n较大的要用时间复杂度为O(nlog2n)的排序方法; ·记录的大小(规模);记录大最好用链表作为存储结构,而快速排序和堆排序在链表上难于实现; ·关键字的结构及其初始状态; ·对稳定性的要求; ·语言工具的条件; ·存储结构; ·时间和辅助空间复杂度。 排序(sort)或分类 所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。其确切定义如下: 输入:n个记录R1,R2,…,Rn,其相应的关键字分别为K1,K2,…,Kn。 输出:Ril,Ri2,…,Rin,使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。 1.被排序对象--文件 被排序的对象--文件由一组记录组成。 记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录,称为关键字项。该数据项的值称为关键字(Key)。 注意: 在不易产生混淆时,将关键字项简称为关键字。 2.排序运算的依据--关键字 用来作排序运算依据的关键字,可以是数字类型,也可以是字符类型。 关键字的选取应根据问题的要求而定。 【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录,则必须用"准考证号"作为关键字。若要按照考生的总分数排名次,则需用"总分数"作为关键字。 排序的稳定性 当待排序记录的关键字均不相同时,排序结果是惟一的,否则排序结果不唯一。 在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。 注意: 排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中,只要有一个实例使得算法不满足稳定性要求,则该排序算法就是不稳定的。 排序方法的分类 1.按是否涉及数据的内、外存交换分 在排序过程中,若整个文件都是放在内存中处理,排序时不涉及数据的内、外存交换,则称之为内部排序(简称内排序);反之,若排序过程中要进行数据的内、外存交换,则称之为外部排序。 注意: ① 内排序适用于记录个数不很多的小文件 ② 外排序则适用于记录个数太多,不能一次将其全部记录放人内存的大文件。 2.按策略划分内部排序方法 可以分为五类:插入排序、选择排序、交换排序、归并排序和分配排序。 排序算法分析 1.排序算法的基本操作 大多数排序算法都有两个基本的操作: (1) 比较两个关键字的大小; (2) 改变指向记录的指针或移动记录本身。 注意: 第(2)种基本操作的实现依赖于待排序记录的存储方式。 2.待排文件的常用存储方式 (1) 以顺序表(或直接用向量)作为存储结构 排序过程:对记录本身进行物理重排(即通过关键字之间的比较判定,将记录移到合适的位置) (2) 以链表作为存储结构 排序过程:无须移动记录,仅需修改指针。通常将这类排序称为链表(或链式)排序; (3) 用顺序的方式存储待排序的记录,但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表) 排序过程:只需对辅助表的表目进行物理重排(即只移动辅助表的表目,而不移动记录本身)。适用于难于在链表上实现,仍需避免排序过程中移动记录的排序方法。 3.排序算法性能评价 (1) 评价排序算法好坏的标准 评价排序算法好坏的标准主要有两条: ① 执行时间和所需的辅助空间 ② 算法本身的复杂程度 (2) 排序算法的空间复杂度 若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间是O(1),则称之为就地排序(In-PlaceSou)。 非就地排序一般要求的辅助空间为O(n)。 (3) 排序算法的时间开销 大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模,还取决于输入实例中数据的状态。

马铭芳 2019-12-02 01:19:07 0 浏览量 回答数 0

回答

对于排序算法,平均时间复杂度 插入排序 O(n^2) 冒泡排序 O(n^2) 选择排序 O(n^2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 基数排序 O(n) 希尔排序 O(n^1.25) 有一个时间复杂度的排列顺序,依次为 Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)Ο(1)表示基本语句的执行次数是一个常数,一般来说,只要算法中不存在循环语句,其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间,而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法,把这类问题称为P类问题,而把后者称为NP问题。 这只能基本的计算时间复杂度,具体的运行还会与硬件有关。

沉默术士 2019-12-02 01:17:53 0 浏览量 回答数 0

问题

Mysql实现跨表查询排序

落地花开啦 2019-12-01 19:49:58 1199 浏览量 回答数 1

回答

基本术语: 假设记录集大小为n。排序过程需要经过若干趟操作,每一趟操作由若干次子操作组成。 算法思想: 选择类排序(包括简单选择排序、树形选择排序和堆排序等)的基本算法思想是执行第i趟操作时,从第i条记录后选择一条最小的记录和第i条记录交换。 初始状态: 49 38 65 97 76 13 27 第一趟: 从(38 65 97 76 13 27)中选择最小值13与49交换 13 38 65 97 76 49 27 第二趟: 从(65 97 76 49 27)中选择最小值27与38交换 13 27 65 97 76 49 38 ... ...

青衫无名 2019-12-02 01:18:06 0 浏览量 回答数 0

问题

【RDS教程】专业DBA速成 - CPU优化篇

rds-pd 2019-12-01 21:59:13 15591 浏览量 回答数 3

回答

Step1 将n个元素个数列分为5个小组,在每个小组内按直接插入法排序;step2 在第i步,分组个数取 di+1 =(di +1)/2 {9,5,3,2,1};相临两组之间的对应元素进行比较,如果ai>aj,则交换它们的位置;Step3 当dK = 1的循环过程完成后,排序过程结束。希尔排序举例:设有字符数列f d a c b e,执行Shell排序:

知与谁同 2019-12-02 01:18:11 0 浏览量 回答数 0

回答

先补充一下概念:Java 内存模型中的可见性、原子性和有序性。可见性:  可见性是一种复杂的属性,因为可见性中的错误总是会违背我们的直觉。通常,我们无法确保执行读操作的线程能适时地看到其他线程写入的值,有时甚至是根本不可能的事情。为了确保多个线程之间对内存写入操作的可见性,必须使用同步机制。  可见性,是指线程之间的可见性,一个线程修改的状态对另一个线程是可见的。也就是一个线程修改的结果。另一个线程马上就能看到。比如:用volatile修饰的变量,就会具有可见性。volatile修饰的变量不允许线程内部缓存和重排序,即直接修改内存。所以对其他线程是可见的。但是这里需要注意一个问题,volatile只能让被他修饰内容具有可见性,但不能保证它具有原子性。比如 volatile int a = 0;之后有一个操作 a++;这个变量a具有可见性,但是a++ 依然是一个非原子操作,也就是这个操作同样存在线程安全问题。  在 Java 中 volatile、synchronized 和 final 实现可见性。原子性:  原子是世界上的最小单位,具有不可分割性。比如 a=0;(a非long和double类型) 这个操作是不可分割的,那么我们说这个操作时原子操作。再比如:a++; 这个操作实际是a = a + 1;是可分割的,所以他不是一个原子操作。非原子操作都会存在线程安全问题,需要我们使用同步技术(sychronized)来让它变成一个原子操作。一个操作是原子操作,那么我们称它具有原子性。java的concurrent包下提供了一些原子类,我们可以通过阅读API来了解这些原子类的用法。比如:AtomicInteger、AtomicLong、AtomicReference等。  在 Java 中 synchronized 和在 lock、unlock 中操作保证原子性。有序性:  Java 语言提供了 volatile 和 synchronized 两个关键字来保证线程之间操作的有序性,volatile 是因为其本身包含“禁止指令重排序”的语义,synchronized 是由“一个变量在同一个时刻只允许一条线程对其进行 lock 操作”这条规则获得的,此规则决定了持有同一个对象锁的两个同步块只能串行执行。下面内容摘录自《Java Concurrency in Practice》:  下面一段代码在多线程环境下,将存在问题。复制代码+ View code1 /** 2 * @author zhengbinMac 3 */ 4 public class NoVisibility { 5 private static boolean ready; 6 private static int number; 7 private static class ReaderThread extends Thread { 8 @Override 9 public void run() {10 while(!ready) {11 Thread.yield();12 }13 System.out.println(number);14 }15 }16 public static void main(String[] args) {17 new ReaderThread().start();18 number = 42;19 ready = true;20 }21 }复制代码  NoVisibility可能会持续循环下去,因为读线程可能永远都看不到ready的值。甚至NoVisibility可能会输出0,因为读线程可能看到了写入ready的值,但却没有看到之后写入number的值,这种现象被称为“重排序”。只要在某个线程中无法检测到重排序情况(即使在其他线程中可以明显地看到该线程中的重排序),那么就无法确保线程中的操作将按照程序中指定的顺序来执行。当主线程首先写入number,然后在没有同步的情况下写入ready,那么读线程看到的顺序可能与写入的顺序完全相反。  在没有同步的情况下,编译器、处理器以及运行时等都可能对操作的执行顺序进行一些意想不到的调整。在缺乏足够同步的多线程程序中,要想对内存操作的执行春旭进行判断,无法得到正确的结论。  这个看上去像是一个失败的设计,但却能使JVM充分地利用现代多核处理器的强大性能。例如,在缺少同步的情况下,Java内存模型允许编译器对操作顺序进行重排序,并将数值缓存在寄存器中。此外,它还允许CPU对操作顺序进行重排序,并将数值缓存在处理器特定的缓存中。二、Volatile原理  Java语言提供了一种稍弱的同步机制,即volatile变量,用来确保将变量的更新操作通知到其他线程。当把变量声明为volatile类型后,编译器与运行时都会注意到这个变量是共享的,因此不会将该变量上的操作与其他内存操作一起重排序。volatile变量不会被缓存在寄存器或者对其他处理器不可见的地方,因此在读取volatile类型的变量时总会返回最新写入的值。  在访问volatile变量时不会执行加锁操作,因此也就不会使执行线程阻塞,因此volatile变量是一种比sychronized关键字更轻量级的同步机制。  当对非 volatile 变量进行读写的时候,每个线程先从内存拷贝变量到CPU缓存中。如果计算机有多个CPU,每个线程可能在不同的CPU上被处理,这意味着每个线程可以拷贝到不同的 CPU cache 中。  而声明变量是 volatile 的,JVM 保证了每次读变量都从内存中读,跳过 CPU cache 这一步。当一个变量定义为 volatile 之后,将具备两种特性:  1.保证此变量对所有的线程的可见性,这里的“可见性”,如本文开头所述,当一个线程修改了这个变量的值,volatile 保证了新值能立即同步到主内存,以及每次使用前立即从主内存刷新。但普通变量做不到这点,普通变量的值在线程间传递均需要通过主内存(详见:Java内存模型)来完成。  2.禁止指令重排序优化。有volatile修饰的变量,赋值后多执行了一个“load addl $0x0, (%esp)”操作,这个操作相当于一个内存屏障(指令重排序时不能把后面的指令重排序到内存屏障之前的位置),只有一个CPU访问内存时,并不需要内存屏障;(什么是指令重排序:是指CPU采用了允许将多条指令不按程序规定的顺序分开发送给各相应电路单元处理)。volatile 性能:  volatile 的读性能消耗与普通变量几乎相同,但是写操作稍慢,因为它需要在本地代码中插入许多内存屏障指令来保证处理器不发生乱序执行。

wangccsy 2019-12-02 01:48:10 0 浏览量 回答数 0

问题

论坛推荐的Node.jsOSSSDK执行Multipart.complete操作有误

老羊肖恩 2019-12-01 21:28:01 7572 浏览量 回答数 3

问题

如何对从MySQL调用的HTML表行进行排序?mysql

保持可爱mmm 2020-05-17 19:17:16 0 浏览量 回答数 1

回答

当你自己实现接口时,“自然顺序”就是你在compareTo()方法中实现的内容。然后,在对可比较对象集合排序时,这种顺序将是默认的排序顺序。 该接口对实现它的每个类的对象强制执行总排序。这种顺序称为类的自然顺序

一码平川MACHEL 2019-12-02 02:19:48 0 浏览量 回答数 0

问题

我可以在逻辑上对表中的列进行重新排序吗?

心有灵_夕 2019-12-24 22:00:14 0 浏览量 回答数 1

问题

SQL Select 执行顺序 Select Order by 谁先执行

吴孟桥 2019-12-01 19:57:30 1168 浏览量 回答数 2

回答

诸如List<T>等泛型集合类,直接提供了sort()方法用于将集合中的元素进行排序。 但是,其前提是集合中存放的是可直接排序的基本类型,如List<int>, List<double>,如果 我们定义了一个自定义类型 Class MyClass,并创建一个自定义类型的集合如List<MyClass>, 那么无参的sort()方法就不可用了,因为不知道如何排序了。这时就需要借助: IComparer 和 IComparable 首先,我们来看一下c#泛型List提供的Sort方法: 泛型List类的Sort方法有四种形式,分别是 1,不带有任何参数的Sort方法----Sort(); 2,带有比较器参数的Sort方法 ----Sort(IComparer<T>) 3,带有比较代理方法参数的Sort方法----Sort(Comparison<(Of <(T>)>)) 4,带有比较器参数,可以指定排序范围的Sort方法----Sort(Int32, Int32 IComparer(T)) 【解析:】第一种方法 使用这种方法不是对List中的任何元素对象都可以进行排序,List中的元素对象必须继承IComparable接口,并且要实现IComparable接口中的CompareTo()方法,在CompareTo()方法中要自己实现对象的比较规则。 例如,Int32和Double都是实现了IComparable接口并重载了CompareTo方法的结构。(注:int和double都是Int32和Double的别名(alias)) 【解析:】第二种方法 2,带有比较器参数的Sort方法 ----Sort(IComparer<T>), 1)创建一个额外的比较器类:其实就相当于将排序功能中的比较操作,留个使用者来完成。这个比较操作必须在实现了IComparer接口的自定义比较类中完成;如: class myComparer:IComparer<MyClass> 2)制定比较规则实现比较方法:因为接口中有一个用于比较的重载函数Compare,所在在比较器类中我们必须实现它,完成自己希望的比较。所谓自己希望的比较就是说自己实现自定义对象的比较规则,例如你知道自定义类MyClass中哪个属性适合用来排序,那么就选择这个属性作为整个自定义类对象的排序属性,如该类中有年龄,学号,入学日期等属性,你可以选择年龄属性作为排序属性。如: public class myComparer:IComparer<MyClass> { //实现按年龄升序排列 public int Compare(MyClass x, MyClass y) { return (x.age.CompareTo(y.age)); //age代表年龄属性是整型,即其已支持CompareTo方法 } } 3)使用比较器的排序方法调用:然后,在自定义类型的集合如List<MyClass> myList,上就可以进行sort排序了,如 myList.Sort(new myComparer()); 【解析:】第三种方法 3,带有比较代理方法参数的Sort方法----Sort(Comparison<(Of <(T>)>)) Comparison<(Of <(T>)>是一种泛型委托。所以,需要编写一个对象排序比较的方法,对List中的元素对象没有特殊的要求,但在比较方法中需要实现 对象比较规则,这个方法实现后,就可以把这方名字作为参数委托给List的Sort方法,Sort方法在排序时会执行这个方法对List中的对象进行比较 需要编写一个对象排序比较的方法,对List中的元素对象没有特殊的要求,但在比较方法中需要实现对象比较规则,这个方法实现后,就可以把这方名字作为参 数委托给List的Sort方法,Sort方法在排序时会执行这个方法对List中的对象进行比较 【解析:】第四种方法 4,带有比较器参数,可以指定排序范围的Sort方法----Sort(Int32, Int32 IComparer(T)) 对于第四排序方法,实际是第二种比较器排序的一个扩展,在指定排序比较器的同时,指定排序范围,即List中准备排序的开始元素索引和结束元素索引

行者武松 2019-12-02 01:17:43 0 浏览量 回答数 0

回答

Hive基于HADOOP执行分布式程序,和普通单机程序不同的一个特点就是最终的数据会产生多个子文件,每个reducer节点都会处理partition给自己的那份数据产生结果文件,这导致了在HADOOP环境下很难对数据进行全局排序,如果在HADOOP上进行order by全排序,会导致所有的数据集中在一台reducer节点上,然后进行排序,这样很可能会超过单个节点的磁盘和内存存储能力导致任务失败。 一种替代的方案则是放弃全局有序,而是分组有序,比如不求全百度最高的点击词排序,而是求每种产品线的最高点击词排序。

不语奈何 2020-01-09 19:23:29 0 浏览量 回答数 0

问题

快速排序算法对下列实例排序

知与谁同 2019-12-01 20:10:53 385 浏览量 回答数 1

回答

select 先执行没错,有结果了再来排序,个人觉得可以这样想,select 查询出来后,在显示id和name之前,先对age进行排序(这时所有的字段都还存在)

吴孟桥 2019-12-02 02:46:47 0 浏览量 回答数 0

问题

Javascript Array.sort实现?

保持可爱mmm 2020-01-16 16:06:05 1 浏览量 回答数 1

回答

1、LIMIT 语句 分页查询是最常用的场景之一,但也通常也是最容易出问题的地方。比如对于下面简单的语句,一般 DBA 想到的办法是在 type, name, create_time 字段上加组合索引。这样条件排序都能有效的利用到索引,性能迅速提升。 好吧,可能90%以上的 DBA 解决该问题就到此为止。但当 LIMIT 子句变成 “LIMIT 1000000,10” 时,程序员仍然会抱怨:我只取10条记录为什么还是慢?要知道数据库也并不知道第1000000条记录从什么地方开始,即使有索引也需要从头计算一次。出现这种性能问题,多数情形下是程序员偷懒了。在前端数据浏览翻页,或者大数据分批导出等场景下,是可以将上一页的最大值当成参数作为查询条件的。SQL 重新设计如下: 在新设计下查询时间基本固定,不会随着数据量的增长而发生变化。 2、隐式转换 SQL语句中查询变量和字段定义类型不匹配是另一个常见的错误。比如下面的语句: 其中字段 bpn 的定义为 varchar(20),MySQL 的策略是将字符串转换为数字之后再比较。函数作用于表字段,索引失效。上述情况可能是应用程序框架自动填入的参数,而不是程序员的原意。现在应用框架很多很繁杂,使用方便的同时也小心它可能给自己挖坑。 3、关联更新、删除 虽然 MySQL5.6 引入了物化特性,但需要特别注意它目前仅仅针对查询语句的优化。对于更新或删除需要手工重写成 JOIN。比如下面 UPDATE 语句,MySQL 实际执行的是循环/嵌套子查询(DEPENDENT SUBQUERY),其执行时间可想而知。 执行计划: 重写为 JOIN 之后,子查询的选择模式从 DEPENDENT SUBQUERY 变成 DERIVED,执行速度大大加快,从7秒降低到2毫秒 执行计划简化为: 4、混合排序 MySQL 不能利用索引进行混合排序。但在某些场景,还是有机会使用特殊方法提升性能的。 执行计划显示为全表扫描: 由于 is_reply 只有0和1两种状态,我们按照下面的方法重写后,执行时间从1.58秒降低到2毫秒。 5、EXISTS语句 MySQL 对待 EXISTS 子句时,仍然采用嵌套子查询的执行方式。如下面的 SQL 语句: 执行计划为: 去掉 exists 更改为 join,能够避免嵌套子查询,将执行时间从1.93秒降低为1毫秒。 新的执行计划: 6、条件下推外部查询条件不能够下推到复杂的视图或子查询的情况有: 聚合子查询; 含有 LIMIT 的子查询; UNION 或 UNION ALL 子查询; 输出字段中的子查询; 如下面的语句,从执行计划可以看出其条件作用于聚合子查询之后 确定从语义上查询条件可以直接下推后,重写如下: 执行计划变为: 7、提前缩小范围 先上初始 SQL 语句: 数为90万,时间消耗为12秒。 由于最后 WHERE 条件以及排序均针对最左主表,因此可以先对 my_order 排序提前缩小数据量再做左连接。SQL 重写后如下,执行时间缩小为1毫秒左右。 再检查执行计划:子查询物化后(select_type=DERIVED)参与 JOIN。虽然估算行扫描仍然为90万,但是利用了索引以及 LIMIT 子句后,实际执行时间变得很小。 8、中间结果集下推 再来看下面这个已经初步优化过的例子(左连接中的主表优先作用查询条件): 那么该语句还存在其它问题吗?不难看出子查询 c 是全表聚合查询,在表数量特别大的情况下会导致整个语句的性能下降。其实对于子查询 c,左连接最后结果集只关心能和主表 resourceid 能匹配的数据。因此我们可以重写语句如下,执行时间从原来的2秒下降到2毫秒。 但是子查询 a 在我们的SQL语句中出现了多次。这种写法不仅存在额外的开销,还使得整个语句显的繁杂。使用 WITH 语句再次重写: 总结数据库编译器产生执行计划,决定着SQL的实际执行方式。但是编译器只是尽力服务,所有数据库的编译器都不是尽善尽美的。上述提到的多数场景,在其它数据库中也存在性能问题。了解数据库编译器的特性,才能避规其短处,写出高性能的SQL语句。程序员在设计数据模型以及编写SQL语句时,要把算法的思想或意识带进来。编写复杂SQL语句要养成使用 WITH 语句的习惯。简洁且思路清晰的SQL语句也能减小数据库的负担 。

茶什i 2020-01-13 11:11:06 0 浏览量 回答数 0

回答

不知道题主基于哪个发行版本,提供一个思路可供参考查找下对应发行版本的Runlevel不同的等级对应不同的指令,然后写入脚本,在对应指令执行时,就会依次按照固定规则(重点)执行脚本如果想要在网络关闭之前执行脚本,则该脚本的规则排序应该在网络控制脚本之前

客官来玩啊 2019-12-02 03:11:42 0 浏览量 回答数 0

问题

关于递归的问题

a123456678 2019-12-01 19:51:03 857 浏览量 回答数 1
阿里云大学 云服务器ECS com域名 网站域名whois查询 开发者平台 小程序定制 小程序开发 国内短信套餐包 开发者技术与产品 云数据库 图像识别 开发者问答 阿里云建站 阿里云备案 云市场 万网 阿里云帮助文档 免费套餐 开发者工具 企业信息查询 小程序开发制作 视频内容分析 企业网站制作 视频集锦 代理记账服务 2020阿里巴巴研发效能峰会 企业建站模板 云效成长地图 高端建站