• 关于 排序算法类 的搜索结果

回答

就好比问,汉语中常用写作方法有多少种,怎么分类。 算法按用途分,体现设计目的、有什么特点 算法按实现方式分,有递归、迭代、平行、序列、过程、确定、不确定等等 算法按设计范型分,有分治、动态、贪心、线性、图论、简化等等 作为图灵完备的语言,理论上”Java语言“可以实现所有算法。 “Java的标准库'中用了一些常用数据结构和相关算法. 像apache common这样的java库中又提供了一些通用的算法-------------------------排序是程序开发中一种非常常见的操作,对一组任意的数据元素(或记录)经过排序操作后,就可以把他们变成一组按关键字排序的有序队列。 对一个排序算法来说,一般从下面3个方面来衡量算法的优劣: 时间复杂度:它主要是分析关键字的比较次数和记录的移动次数。 空间复杂度:分析排序算法中需要多少辅助内存。 稳定性:若两个记录A和B的关键字值相等,但是排序后A,B的先后次序保持不变,则称这种排序算法是稳定的;反之,就是不稳定的。 就现有的排序算法来看,排序大致可分为内部排序和外部排序。如果整个排序过程不需要借助外部存储器(如磁盘等),所有排序操作都是在内存中完成,这种排序就被称为内部排序。 如果参与排序的数据元素非常多,数据量非常大,计算无法把整个排序过程放在内存中完成,必须借助于外部存储器(如磁盘),这种排序就被称为外部排序。 外部排序最常用算噶是多路归并排序,即将原文件分解称多个能够一次性装入内存的部分,分别把每一部分调入内存完成排序,接下来再对多个有序的子文件进行归并排序。 就常用的内部排序算法来说,可以分为以下几类: 选择排序(直接选择排序,堆排序) 交换排序(冒泡排序,快速排序) 插入排序(直接插入排序,折半插入排序,Shell排序) 归并排序 桶式排序 基数排序

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

问题

查找,排序等对数据进行管理的这类算法在算法分类中属于什么算法

知与谁同 2019-12-01 20:11:13 429 浏览量 回答数 2

回答

楼主要复习还是怎么。 归一下类: 1.排序:插入,选择,冒泡,快排,桶排序,堆排序,基数排序,计数排序,top-k问题; 2.搜索:深搜,广搜,递归,递推,回溯; 3.图:拓扑排序,kruskal算法,prim算法,bellman-ford算法,dijkstra算法,最大流; 4.动态规划,贪心算法,hash表; 5.树;(二叉查找树,二叉平衡树。。。) 6.其他:不相交集合的路径压缩,kmp,数论(最大公约数,中国余数定理。。),随机算法。 暂时就想到这么多了。

美人迟暮 2019-12-02 01:26:15 0 浏览量 回答数 0

新用户福利专场,云服务器ECS低至96.9元/年

新用户福利专场,云服务器ECS低至96.9元/年

问题

JDK7中Arrays工具类sort()对基本类型和对象采用不同排序算法的原因是什么?

蛮大人123 2019-12-01 20:15:00 1153 浏览量 回答数 2

问题

受计算机内存大小的限制,排序类算法只能对有限数量的数据进行排序.

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

回答

排序算法一般分为以下几种: (1)非线性时间比较类排序:交换类排序(快速排序和冒泡排序)、插入类排序(简单插入排序和希尔排序)、选择类排序(简单选择排序和堆排序)、归并排序(二路归并排序和多路归并排序);(2)线性时间非比较类排序:计数排序、基数排序和桶排序。

祁同伟 2019-12-02 01:17:23 0 浏览量 回答数 0

回答

排序算法一般分为以下几种: (1)非线性时间比较类排序:交换类排序(快速排序和冒泡排序)、插入类排序(简单插入排序和希尔排序)、选择类排序(简单选择排序和堆排序)、归并排序(二路归并排序和多路归并排序); (2)线性时间非比较类排序:计数排序、基数排序和桶排序。

boxti 2019-12-02 01:18:45 0 浏览量 回答数 0

回答

假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。 对于不稳定的排序算法,只要举出一个实例,即可说明它的不稳定性;而对于稳定的排序算法,必须对算法进行分析从而得到稳定的特性。需要注意的是,排序算法是否为稳定的是由具体算法决定的,不稳定的算法在某种条件下可以变为稳定的算法,而稳定的算法在某种条件下也可以变为不稳定的算法。 例如,对于如下冒泡排序算法,原本是稳定的排序算法,如果将记录交换的条件改成r[j]>=r[j+1],则两个相等的记录就会交换位置,从而变成不稳定的算法。 void BubbleSort(int r[ ], int n){ exchange=n; //第一趟冒泡排序的范围是r[1]到r[n] while (exchange) //仅当上一趟排序有记录交换才进行本趟排序 { bound=exchange; exchange=0; for (j=1; j if (r[j]>r[j+1]) { r[j]←→r[j+1]; exchange=j; //记录每一次发生记录交换的位置 } } } 再如,快速排序原本是不稳定的排序方法,但若待排序记录中只有一组具有相同关键码的记录,而选择的轴值恰好是这组相同关键码中的一个,此时的快速排序就是稳定的。 稳定的排序方法: 堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法,而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。 首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj, Ai原来在位置前,排序后Ai还是要在Aj位置前。 其次,说一下稳定性的好处。排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就 是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。 回到主题,现在分析一下常见的排序算法的稳定性,每个都给出简单的理由。 (1)冒泡排序 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改 变,所以冒泡排序是一种稳定排序算法。 (2)选择排序 选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个 元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么 交换后稳定性就被破坏了。举个例子,序列5 8 5 2 9, 第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。 (3)插入排序 插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开 始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相 等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳 定的。 (4)快速排序 快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为 5 3 3 4 3 8 9 10 11, 现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j] 交换的时刻。 (5)归并排序 归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有 序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定 性。那么,在短的有序序列合并的过程中,稳定是不会受到破坏,合并过程中可以保证如果两个当前元素相等时,把处在前面的序列的元素保存在结 果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。 (6)基数排序 基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优 先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。 (7)希尔排序(shell) 希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小, 插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,一次插入排序是稳定的,不会改变相同元 素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。 (8)堆排序 堆的结构是节点i的孩子为2*i和2*i+1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, ...1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没 有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。 综上,得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

小旋风柴进 2019-12-02 01:18:09 0 浏览量 回答数 0

回答

排序大类分为内排序和外排序,通常排序指的是内排序 内排序主要分为: 插入排序(直接插入排序,折半插入排序,Shell排序) 交换排序(冒泡排序,快速排序) 选择排序(简单选择排序,堆排序) 归并排序 基数排序 每种排序根据问题的规模以及初始排序表排列情况性能而不同,一般来讲,快速排序的平均性能最好。在C++中,可以使用标准库算法中的sort进行排序,它会根据情况动态地选择一种高效排序算法。

小哇 2019-12-02 01:18:09 0 浏览量 回答数 0

回答

冒泡排序算法的运作如下:(从后往前) 1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元3. 素应该会是最大的数。 4. 针对所有的元素重复以上的步骤,除了最后一个。 5. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 递归算法 递归算法流程 递归过程一般通过函数或子过程来实现。递归方法:在函数或子过程的内部,直接或者间接地调用自己的算法时间复杂度 若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数 和记录移动次数 均达到最小值: , 。 所以,冒泡排序最好的时间复杂度为 。   若初始文件是反序的,需要进行 趟排序。每趟排序要进行 次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值: 冒泡排序的最坏时间复杂度为 。 综上,因此冒泡排序总的平均时间复杂度为 。 算法稳定性 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。 递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。 递归算法解决问题的特点: (1) 递归就是在过程或函数里调用自身。 (2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。 (3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。 (4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

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

回答

•策略(Strategy),对象行为型模式 =》使用组合的方式•模板方法(Template method),类行为型模式 =》 使用继承的方式Head First里面问答里面有说明因为策略模式使用对象组合。在某种程度上,你是对的——我们使用数组对象排序我们的数组,这部分和策略模式非常相似。但是请记住,在策略模式中,你所组合的类实现了整个算法。数组所实现的排序算法并不完整,它需要一个类填补compareTo()方法的实现。因此,我们认为这更像模板方法。Arrays类里面还有另外一个api:public static void sort(T[] a, Comparator<? super T> c) 将Comparator也当成一种算法看的话,感觉这个api更像策略模式。白话一点,模板方法模式的对象只是实现了算法的某个步骤,具体的算法大部分定义在父类里。而策略模式的对象实现了整个算法。

蛮大人123 2019-12-02 01:52:08 0 浏览量 回答数 0

回答

对于排序算法,平均时间复杂度插入排序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

问题

集合类的sort方法采用的什么排序算法

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

回答

对于排序算法,平均时间复杂度 插入排序 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

回答

对于排序算法,平均时间复杂度 插入排序 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

回答

排序算法 所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 分类 在计算机科学所使用的排序算法通常被分类为: 计算的复杂度(最差、平均、和最好表现),依据串列(list)的大小(n)。一般而言,好的表现是O。(n log n),且坏的行为是Ω(n2)。对於一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要Ω(n log n)。 记忆体使用量(以及其他电脑资源的使用) 稳定度:稳定排序算法会依照相等的关键(换言之就是值)维持纪录的相对次序。也就是一个排序算法是稳定的,就是当有两个有相等关键的纪录R和S,且在原本的串列中R出现在S之前,在排序过的串列中R也将会是在S之前。 一般的方法:插入、交换、选择、合并等等。交换排序包含冒泡排序(bubble sort)和快速排序(quicksort)。选择排序包含shaker排序和堆排序(heapsort)。 当相等的元素是无法分辨的,比如像是整数,稳定度并不是一个问题。然而,假设以下的数对将要以他们的第一个数字来排序。 (4, 1) (3, 1) (3, 7) (5, 6) 在这个状况下,有可能产生两种不同的结果,一个是依照相等的键值维持相对的次序,而另外一个则没有: (3, 1) (3, 7) (4, 1) (5, 6) (维持次序) (3, 7) (3, 1) (4, 1) (5, 6) (次序被改变) 不稳定排序算法可能会在相等的键值中改变纪录的相对次序,但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地时作为稳定。作这件事情的一个方式是人工扩充键值的比较,如此在其他方面相同键值的两个物件间之比较,就会被决定使用在原先资料次序中的条目,当作一个同分决赛。然而,要记住这种次序通常牵涉到额外的空间负担。 排列算法列表 在这个表格中,n是要被排序的纪录数量以及k是不同键值的数量。 稳定的 冒泡排序(bubble sort) — O(n2) 鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2) 插入排序 (insertion sort)— O(n2) 桶排序 (bucket sort)— O(n); 需要 O(k) 额外 记忆体 计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体 归并排序 (merge sort)— O(n log n); 需要 O(n) 额外记忆体 原地归并排序 — O(n2) 二叉树排序 (Binary tree sort) — O(n log n); 需要 O(n) 额外记忆体 鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体 基数排序 (radix sort)— O(n·k); 需要 O(n) 额外记忆体 Gnome sort — O(n2) Library sort — O(n log n) with high probability, 需要 (1+ε)n 额外记忆体 不稳定 选择排序 (selection sort)— O(n2) 希尔排序 (shell sort)— O(n log n) 如果使用最佳的现在版本 Comb sort — O(n log n) 堆排序 (heapsort)— O(n log n) Smoothsort — O(n log n) 快速排序 (quicksort)— O(n log n) 期望时间, O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序 Introsort — O(n log n) Patience sorting — O(n log n + k) 最外情况时间, 需要 额外的 O(n + k) 空间, 也需要找到最长的递增子序列(longest increasing subsequence) 不实用的排序算法 Bogo排序 — O(n × n!) 期望时间, 无穷的最坏情况。 Stupid sort — O(n3); 递回版本需要 O(n2) 额外记忆体 Bead sort — O(n) or O(√n), 但需要特别的硬体 Pancake sorting — O(n), 但需要特别的硬体 排序的算法 排序的算法有很多,对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序,他们对空间的要求不高,但是时间效率却不稳定;而后面三种排序相对于简单排序对空间的要求稍高一点,但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。 插入排序 冒泡排序 选择排序 快速排序 堆排序 归并排序 基数排序 希尔排序 插入排序 插入排序是这样实现的: 首先新建一个空列表,用于保存已排序的有序数列(我们称之为"有序列表")。 从原数列中取出一个数,将其插入"有序列表"中,使其仍旧保持有序状态。 重复2号步骤,直至原数列为空。 插入排序的平均时间复杂度为平方级的,效率不高,但是容易实现。它借助了"逐步扩大成果"的思想,使有序列表的长度逐渐增加,直至其长度等于原列表的长度。 冒泡排序 冒泡排序是这样实现的: 首先将所有待排序的数字放入工作列表中。 从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换。 重复2号步骤,直至再也不能交换。 冒泡排序的平均时间复杂度与插入排序相同,也是平方级的,但也是非常容易实现的算法。 选择排序 选择排序是这样实现的: 设数组内存放了n个待排数字,数组下标从1开始,到n结束。 i=1 从数组的第i个元素开始到第n个元素,寻找最小的元素。 将上一步找到的最小元素和第i位元素交换。 如果i=n-1算法结束,否则回到第3步 选择排序的平均时间复杂度也是O(n²)的。 快速排序 现在开始,我们要接触高效排序算法了。实践证明,快速排序是所有排序算法中最高效的一种。它采用了分治的思想:先保证列表的前半部分都小于后半部分,然后分别对前半部分和后半部分排序,这样整个列表就有序了。这是一种先进的思想,也是它高效的原因。因为在排序算法中,算法的高效与否与列表中数字间的比较次数有直接的关系,而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了,大大减少了数字间不必要的比较。但查找数据得另当别论了。 堆排序 堆排序与前面的算法都不同,它是这样的: 首先新建一个空列表,作用与插入排序中的"有序列表"相同。 找到数列中最大的数字,将其加在"有序列表"的末尾,并将其从原数列中删除。 重复2号步骤,直至原数列为空。 堆排序的平均时间复杂度为nlogn,效率高(因为有堆这种数据结构以及它奇妙的特征,使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度,维护需要logn的时间复杂度),但是实现相对复杂(可以说是这里7种算法中比较难实现的)。 看起来似乎堆排序与插入排序有些相像,但他们其实是本质不同的算法。至少,他们的时间复杂度差了一个数量级,一个是平方级的,一个是对数级的。 平均时间复杂度 插入排序 O(n2) 冒泡排序 O(n2) 选择排序 O(n2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 基数排序 O(n) 希尔排序 O(n1.25)

小旋风柴进 2019-12-02 01:17:41 0 浏览量 回答数 0

回答

快速排序法。 Java的排序算法有哪些。 java的排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序:1.插入排序:直接插入排序、二分法插入排序、希尔排序。 2.选择排序:简单选择排序、堆排序。 3.交换排序:冒泡排序、快速排序。 4.归并排序。 5.基数排序。 java中的算法,一共有多少种,哪几种,怎么分类。 1、算法按实现方式分,有递归、迭代、平行、序列、过程、确定、不确定等。 2、算法按设计范型分,有分治、动态、贪心、线性、图论、简化等。

游客886 2019-12-02 01:17:23 0 浏览量 回答数 0

回答

快速排序法。 Java的排序算法有哪些。 java的排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序:1.插入排序:直接插入排序、二分法插入排序、希尔排序。 2.选择排序:简单选择排序、堆排序。 3.交换排序:冒泡排序、快速排序。 4.归并排序。 5.基数排序。 java中的算法,一共有多少种,哪几种,怎么分类。 1、算法按实现方式分,有递归、迭代、平行、序列、过程、确定、不确定等。 2、算法按设计范型分,有分治、动态、贪心、线性、图论、简化等。

liujae 2019-12-02 01:18:02 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

回答

排序算法 所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 分类 在计算机科学所使用的排序算法通常被分类为: 计算的复杂度(最差、平均、和最好表现),依据串列(list)的大小(n)。一般而言,好的表现是O。(n log n),且坏的行为是Ω(n2)。对於一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要Ω(n log n)。 记忆体使用量(以及其他电脑资源的使用) 稳定度:稳定排序算法会依照相等的关键(换言之就是值)维持纪录的相对次序。也就是一个排序算法是稳定的,就是当有两个有相等关键的纪录R和S,且在原本的串列中R出现在S之前,在排序过的串列中R也将会是在S之前。 一般的方法:插入、交换、选择、合并等等。交换排序包含冒泡排序(bubble sort)和快速排序(quicksort)。选择排序包含shaker排序和堆排序(heapsort)。 当相等的元素是无法分辨的,比如像是整数,稳定度并不是一个问题。然而,假设以下的数对将要以他们的第一个数字来排序。 (4, 1) (3, 1) (3, 7) (5, 6) 在这个状况下,有可能产生两种不同的结果,一个是依照相等的键值维持相对的次序,而另外一个则没有: (3, 1) (3, 7) (4, 1) (5, 6) (维持次序) (3, 7) (3, 1) (4, 1) (5, 6) (次序被改变) 不稳定排序算法可能会在相等的键值中改变纪录的相对次序,但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地时作为稳定。作这件事情的一个方式是人工扩充键值的比较,如此在其他方面相同键值的两个物件间之比较,就会被决定使用在原先资料次序中的条目,当作一个同分决赛。然而,要记住这种次序通常牵涉到额外的空间负担。 排列算法列表 在这个表格中,n是要被排序的纪录数量以及k是不同键值的数量。 稳定的 冒泡排序(bubble sort) — O(n2) 鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2) 插入排序 (insertion sort)— O(n2) 桶排序 (bucket sort)— O(n); 需要 O(k) 额外 记忆体 计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体 归并排序 (merge sort)— O(n log n); 需要 O(n) 额外记忆体 原地归并排序 — O(n2) 二叉树排序 (Binary tree sort) — O(n log n); 需要 O(n) 额外记忆体 鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体 基数排序 (radix sort)— O(n·k); 需要 O(n) 额外记忆体 Gnome sort — O(n2) Library sort — O(n log n) with high probability, 需要 (1+ε)n 额外记忆体 不稳定 选择排序 (selection sort)— O(n2) 希尔排序 (shell sort)— O(n log n) 如果使用最佳的现在版本 Comb sort — O(n log n) 堆排序 (heapsort)— O(n log n) Smoothsort — O(n log n) 快速排序 (quicksort)— O(n log n) 期望时间, O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序 Introsort — O(n log n) Patience sorting — O(n log n + k) 最外情况时间, 需要 额外的 O(n + k) 空间, 也需要找到最长的递增子序列(longest increasing subsequence) 不实用的排序算法 Bogo排序 — O(n × n!) 期望时间, 无穷的最坏情况。 Stupid sort — O(n3); 递回版本需要 O(n2) 额外记忆体 Bead sort — O(n) or O(√n), 但需要特别的硬体 Pancake sorting — O(n), 但需要特别的硬体 排序的算法 排序的算法有很多,对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序,他们对空间的要求不高,但是时间效率却不稳定;而后面三种排序相对于简单排序对空间的要求稍高一点,但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。 插入排序 冒泡排序 选择排序 快速排序 堆排序 归并排序 基数排序 希尔排序 插入排序 插入排序是这样实现的: 首先新建一个空列表,用于保存已排序的有序数列(我们称之为"有序列表")。 从原数列中取出一个数,将其插入"有序列表"中,使其仍旧保持有序状态。 重复2号步骤,直至原数列为空。 插入排序的平均时间复杂度为平方级的,效率不高,但是容易实现。它借助了"逐步扩大成果"的思想,使有序列表的长度逐渐增加,直至其长度等于原列表的长度。 冒泡排序 冒泡排序是这样实现的: 首先将所有待排序的数字放入工作列表中。 从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换。 重复2号步骤,直至再也不能交换。 冒泡排序的平均时间复杂度与插入排序相同,也是平方级的,但也是非常容易实现的算法。 选择排序 选择排序是这样实现的: 设数组内存放了n个待排数字,数组下标从1开始,到n结束。 i=1 从数组的第i个元素开始到第n个元素,寻找最小的元素。 将上一步找到的最小元素和第i位元素交换。 如果i=n-1算法结束,否则回到第3步 选择排序的平均时间复杂度也是O(n²)的。 快速排序 现在开始,我们要接触高效排序算法了。实践证明,快速排序是所有排序算法中最高效的一种。它采用了分治的思想:先保证列表的前半部分都小于后半部分,然后分别对前半部分和后半部分排序,这样整个列表就有序了。这是一种先进的思想,也是它高效的原因。因为在排序算法中,算法的高效与否与列表中数字间的比较次数有直接的关系,而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了,大大减少了数字间不必要的比较。但查找数据得另当别论了。 堆排序 堆排序与前面的算法都不同,它是这样的: 首先新建一个空列表,作用与插入排序中的"有序列表"相同。 找到数列中最大的数字,将其加在"有序列表"的末尾,并将其从原数列中删除。 重复2号步骤,直至原数列为空。 堆排序的平均时间复杂度为nlogn,效率高(因为有堆这种数据结构以及它奇妙的特征,使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度,维护需要logn的时间复杂度),但是实现相对复杂(可以说是这里7种算法中比较难实现的)。 看起来似乎堆排序与插入排序有些相像,但他们其实是本质不同的算法。至少,他们的时间复杂度差了一个数量级,一个是平方级的,一个是对数级的。 平均时间复杂度 插入排序 O(n2) 冒泡排序 O(n2) 选择排序 O(n2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 基数排序 O(n) 希尔排序 O(n1.25) 冒泡排序 654 比如说这个,我想让它从小到大排序,怎么做呢。 第一步:6跟5比,发现比它大,则交换。564 第二步:5跟4比,发现比它大,则交换。465 第三步:6跟5比,发现比它大,则交换。456

聚小编 2019-12-02 01:17:59 0 浏览量 回答数 0

回答

排序算法 所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 分类 在计算机科学所使用的排序算法通常被分类为: 计算的复杂度(最差、平均、和最好表现),依据串列(list)的大小(n)。一般而言,好的表现是O。(n log n),且坏的行为是Ω(n2)。对於一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要Ω(n log n)。 记忆体使用量(以及其他电脑资源的使用) 稳定度:稳定排序算法会依照相等的关键(换言之就是值)维持纪录的相对次序。也就是一个排序算法是稳定的,就是当有两个有相等关键的纪录R和S,且在原本的串列中R出现在S之前,在排序过的串列中R也将会是在S之前。 一般的方法:插入、交换、选择、合并等等。交换排序包含冒泡排序(bubble sort)和快速排序(quicksort)。选择排序包含shaker排序和堆排序(heapsort)。 当相等的元素是无法分辨的,比如像是整数,稳定度并不是一个问题。然而,假设以下的数对将要以他们的第一个数字来排序。 (4, 1) (3, 1) (3, 7) (5, 6) 在这个状况下,有可能产生两种不同的结果,一个是依照相等的键值维持相对的次序,而另外一个则没有: (3, 1) (3, 7) (4, 1) (5, 6) (维持次序) (3, 7) (3, 1) (4, 1) (5, 6) (次序被改变) 不稳定排序算法可能会在相等的键值中改变纪录的相对次序,但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地时作为稳定。作这件事情的一个方式是人工扩充键值的比较,如此在其他方面相同键值的两个物件间之比较,就会被决定使用在原先资料次序中的条目,当作一个同分决赛。然而,要记住这种次序通常牵涉到额外的空间负担。 排列算法列表 在这个表格中,n是要被排序的纪录数量以及k是不同键值的数量。 稳定的 冒泡排序(bubble sort) — O(n2) 鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2) 插入排序 (insertion sort)— O(n2) 桶排序 (bucket sort)— O(n); 需要 O(k) 额外 记忆体 计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体 归并排序 (merge sort)— O(n log n); 需要 O(n) 额外记忆体 原地归并排序 — O(n2) 二叉树排序 (Binary tree sort) — O(n log n); 需要 O(n) 额外记忆体 鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体 基数排序 (radix sort)— O(n·k); 需要 O(n) 额外记忆体 Gnome sort — O(n2) Library sort — O(n log n) with high probability, 需要 (1+ε)n 额外记忆体 不稳定 选择排序 (selection sort)— O(n2) 希尔排序 (shell sort)— O(n log n) 如果使用最佳的现在版本 Comb sort — O(n log n) 堆排序 (heapsort)— O(n log n) Smoothsort — O(n log n) 快速排序 (quicksort)— O(n log n) 期望时间, O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序 Introsort — O(n log n) Patience sorting — O(n log n + k) 最外情况时间, 需要 额外的 O(n + k) 空间, 也需要找到最长的递增子序列(longest increasing subsequence) 不实用的排序算法 Bogo排序 — O(n × n!) 期望时间, 无穷的最坏情况。 Stupid sort — O(n3); 递回版本需要 O(n2) 额外记忆体 Bead sort — O(n) or O(√n), 但需要特别的硬体 Pancake sorting — O(n), 但需要特别的硬体 排序的算法 排序的算法有很多,对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序,他们对空间的要求不高,但是时间效率却不稳定;而后面三种排序相对于简单排序对空间的要求稍高一点,但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。 插入排序 冒泡排序 选择排序 快速排序 堆排序 归并排序 基数排序 希尔排序 插入排序 插入排序是这样实现的: 首先新建一个空列表,用于保存已排序的有序数列(我们称之为"有序列表")。 从原数列中取出一个数,将其插入"有序列表"中,使其仍旧保持有序状态。 重复2号步骤,直至原数列为空。 插入排序的平均时间复杂度为平方级的,效率不高,但是容易实现。它借助了"逐步扩大成果"的思想,使有序列表的长度逐渐增加,直至其长度等于原列表的长度。 冒泡排序 冒泡排序是这样实现的: 首先将所有待排序的数字放入工作列表中。 从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换。 重复2号步骤,直至再也不能交换。 冒泡排序的平均时间复杂度与插入排序相同,也是平方级的,但也是非常容易实现的算法。 选择排序 选择排序是这样实现的: 设数组内存放了n个待排数字,数组下标从1开始,到n结束。 i=1 从数组的第i个元素开始到第n个元素,寻找最小的元素。 将上一步找到的最小元素和第i位元素交换。 如果i=n-1算法结束,否则回到第3步 选择排序的平均时间复杂度也是O(n²)的。 快速排序 现在开始,我们要接触高效排序算法了。实践证明,快速排序是所有排序算法中最高效的一种。它采用了分治的思想:先保证列表的前半部分都小于后半部分,然后分别对前半部分和后半部分排序,这样整个列表就有序了。这是一种先进的思想,也是它高效的原因。因为在排序算法中,算法的高效与否与列表中数字间的比较次数有直接的关系,而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了,大大减少了数字间不必要的比较。但查找数据得另当别论了。 堆排序 堆排序与前面的算法都不同,它是这样的: 首先新建一个空列表,作用与插入排序中的"有序列表"相同。 找到数列中最大的数字,将其加在"有序列表"的末尾,并将其从原数列中删除。 重复2号步骤,直至原数列为空。 堆排序的平均时间复杂度为nlogn,效率高(因为有堆这种数据结构以及它奇妙的特征,使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度,维护需要logn的时间复杂度),但是实现相对复杂(可以说是这里7种算法中比较难实现的)。 看起来似乎堆排序与插入排序有些相像,但他们其实是本质不同的算法。至少,他们的时间复杂度差了一个数量级,一个是平方级的,一个是对数级的。 平均时间复杂度 插入排序 O(n2) 冒泡排序 O(n2) 选择排序 O(n2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 基数排序 O(n) 希尔排序 O(n1.25) 冒泡排序 654 比如说这个,我想让它从小到大排序,怎么做呢。 第一步:6跟5比,发现比它大,则交换。564 第二步:5跟4比,发现比它大,则交换。465 第三步:6跟5比,发现比它大,则交换。456

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

回答

排序算法 所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 分类 在计算机科学所使用的排序算法通常被分类为: 计算的复杂度(最差、平均、和最好表现),依据串列(list)的大小(n)。一般而言,好的表现是O。(n log n),且坏的行为是Ω(n2)。对於一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要Ω(n log n)。 记忆体使用量(以及其他电脑资源的使用) 稳定度:稳定排序算法会依照相等的关键(换言之就是值)维持纪录的相对次序。也就是一个排序算法是稳定的,就是当有两个有相等关键的纪录R和S,且在原本的串列中R出现在S之前,在排序过的串列中R也将会是在S之前。 一般的方法:插入、交换、选择、合并等等。交换排序包含冒泡排序(bubble sort)和快速排序(quicksort)。选择排序包含shaker排序和堆排序(heapsort)。 当相等的元素是无法分辨的,比如像是整数,稳定度并不是一个问题。然而,假设以下的数对将要以他们的第一个数字来排序。 (4, 1) (3, 1) (3, 7) (5, 6) 在这个状况下,有可能产生两种不同的结果,一个是依照相等的键值维持相对的次序,而另外一个则没有: (3, 1) (3, 7) (4, 1) (5, 6) (维持次序) (3, 7) (3, 1) (4, 1) (5, 6) (次序被改变) 不稳定排序算法可能会在相等的键值中改变纪录的相对次序,但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地时作为稳定。作这件事情的一个方式是人工扩充键值的比较,如此在其他方面相同键值的两个物件间之比较,就会被决定使用在原先资料次序中的条目,当作一个同分决赛。然而,要记住这种次序通常牵涉到额外的空间负担。 排列算法列表 在这个表格中,n是要被排序的纪录数量以及k是不同键值的数量。 稳定的 冒泡排序(bubble sort) — O(n2) 鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2) 插入排序 (insertion sort)— O(n2) 桶排序 (bucket sort)— O(n); 需要 O(k) 额外 记忆体 计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体 归并排序 (merge sort)— O(n log n); 需要 O(n) 额外记忆体 原地归并排序 — O(n2) 二叉树排序 (Binary tree sort) — O(n log n); 需要 O(n) 额外记忆体 鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体 基数排序 (radix sort)— O(n·k); 需要 O(n) 额外记忆体 Gnome sort — O(n2) Library sort — O(n log n) with high probability, 需要 (1+ε)n 额外记忆体 不稳定 选择排序 (selection sort)— O(n2) 希尔排序 (shell sort)— O(n log n) 如果使用最佳的现在版本 Comb sort — O(n log n) 堆排序 (heapsort)— O(n log n) Smoothsort — O(n log n) 快速排序 (quicksort)— O(n log n) 期望时间, O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序 Introsort — O(n log n) Patience sorting — O(n log n + k) 最外情况时间, 需要 额外的 O(n + k) 空间, 也需要找到最长的递增子序列(longest increasing subsequence) 不实用的排序算法 Bogo排序 — O(n × n!) 期望时间, 无穷的最坏情况。 Stupid sort — O(n3); 递回版本需要 O(n2) 额外记忆体 Bead sort — O(n) or O(√n), 但需要特别的硬体 Pancake sorting — O(n), 但需要特别的硬体 排序的算法 排序的算法有

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

回答

排序(Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个关键字有序的序列。稳定度(稳定性)一个排序算法是稳定的,就是当有两个相等记录的关键字R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前。当相等的元素是无法分辨的,比如像是整数,稳定度并不是一个问题。然而,假设以下的数对将要以他们的第一个数字来排序。(4,1)(3,1)(3,7)(5,6)在这个状况下,有可能产生两种不同的结果,一个是依照相等的键值维持相对的次序,而另外一个则没有:(3,1)(3,7)(4,1)(5,6) (维持次序)(3,7)(3,1)(4,1)(5,6) (次序被改变)不稳定排序算法可能会在相等的键值中改变纪录的相对次序,但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。作这件事情的一个方式是人工扩充键值的比较,如此在其他方面相同键值的两个对象间之比较,就会被决定使用在原先数据次序中的条目,当作一个同分决赛。然而,要记住这种次序通常牵涉到额外的空间负担。在计算机科学所使用的排序算法通常被分类为:(a)计算的复杂度(最差、平均、和最好性能),依据列表(list)的大小(n)。一般而言,好的性能是 O(nlogn),且坏的性能是 O(n^2)。对于一个排序理想的性能是 O(n)。而仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要 O(nlogn)。(b)存储器使用量(空间复杂度)(以及其他电脑资源的使用)(c)稳定度:稳定的排序算法会依照相等的关键(换言之就是值)维持纪录的相对次序。(d)一般的方法:插入、交换、选择、合并等等。交换排序包含冒泡排序和快速排序。插入排序包含希尔排序,选择排序包括堆排序等。

小哇 2019-12-02 01:17:19 0 浏览量 回答数 0

回答

一、算法应该具有的五个特征: 1.有穷性 算法的有穷性是指算法必须能在执行有限个步骤之后终止; 2.确切性 算法的每一步骤必须有确切的定义; 3.输入项 一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定出了初始条件; 4.输出项 一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的; 5.可行性 算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步,即每个计算步都可以在有限时间内完成(也称之为有效性)。 分类 算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法,厄米变形模型,随机森林算法。 二、算法可以宏泛的分为三类: 1.有限的,确定性算法 这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务,但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。 2.有限的,非确定算法 这类算法在有限的时间内终止。然而,对于一个(或一些)给定的数值,算法的结果并不是唯一的或确定的。 3.无限的算法 是那些由于没有定义终止定义条件,或定义的条件无法由输入的数据满足而不终止运行的算法。通常,无限算法的产生是由于未能确定的定义终止条件。 拓展资料: 算法的要素: 一,数据对象的运算和操作: 计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合,成为该计算机系统的指令系统。一个计算机的基本运算和操作有如下四类: 1,算术运算:加减乘除等运算 2,逻辑运算:或、且、非等运算 3,关系运算:大于、小于、等于、不等于等运算 4,数据传输:输入、输出、赋值等运算[1] 二,算法的控制结构: 一个算法的功能结构不仅取决于所选用的操作,而且还与各操作之间的执行顺序有关。

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

回答

下面是StuQ 发布的大数据工程师技能图谱(仅供参考)大数据通用处理平台SparkFlinkHadoop分布式存储HDFS资源调度YarnMesos机器学习工具MahoutSpark MlibTensorFlow (Google 系)Amazon Machine LearningDMTK (微软分布式机器学习工具)数据分析/数据仓库(SQL类)PigHivekylinSpark SQL,Spark DataFrameImpalaPhoenixELK8.1 ElasticSearch8.2Logstash8.3Kibana消息队列Kafka(纯日志类,大吞吐量)RocketMQZeroMQActiveMQRabbitMQ流式计算Storm/JStormSpark StreamingFlink日志收集ScribeFlume编程语言JavaPythonRRubyScala数据分析挖掘MATLABSPSSSAS数据可视化RD3.jsEChartsExclePython机器学习机器学习基础聚类时间序列推荐系统回归分析文本挖掘决策树支持向量机贝叶斯分类神经网络机器学习工具MahoutSpark MlibTensorFlow (Google 系)Amazon Machine LearningDMTK (微软分布式机器学习工具)算法一致性paxosraftgossip数据结构栈,队列,链表散列表二叉树,红黑树,B树图常用算法1.排序插入排序桶排序堆排序2.快速排序3,最大子数组4.最长公共子序列5.最小生成树最短路径6.矩阵的存储和运算云计算云服务SaaSPaaSIaaSOpenstackDockerEnd.掌握这些都差不多了。

51干警网 2019-12-02 00:17:52 0 浏览量 回答数 0

回答

基本术语: 假设记录集大小为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

回答

选择法的算法: 假设需要对10个数进行排序,那么首先找出10个数里面的最小数,并和这个10个数的第一个(下标0)交换位置,剩下9个数(这9个数都比刚才选出来那个数大),再选出这9个数中的最小的数,和第二个位置的数(下标1)交换,于是还剩8个数(这8个数都比刚才选出来的大).. 依次类推,当还剩两个数时,选出两个数的最小者放在第9个位置(下标8),于是就只剩下一个数了。这个数已经在最后一位(下标9),不用再选择了。所以10个数排序,一共需要选择9次(n个数排序就需要选择n-1次)。#include "Stdio.h"void main(){ void sa(int array[],int n); int array[10],i; printf("enter the array:\n"); for(i=0;i<10;i++) scanf("%d",&array[i]); sa(array,10); printf("the sorted array:\n"); for(i=0;i<10;i++) printf("%d\t",array[i]); getch();}void sa(int array[],int n){ int i,j,k,temp; for(i=0;i<10;i++) { k=i; for(j=i+1;j<n;j++) if(array[j]<array[k]) k=j; temp=array[k]; array[k]=array[i]; array[i]=temp; }} main() { int i,j,temp; int a[10]; for(i=0;i<10;i++) scanf ("%d,",&a[i]); for(j=0;j<=9;j++) { for (i=0;i<10-j;i++) if (a[i]>a[i+1]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp;} } for(i=1;i<11;i++) printf("%5d,",a[i] ); printf("\n"); }--------------冒泡算法冒泡排序的算法分析与改进 交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。 应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。 冒泡排序 1、排序方法 将被排序的记录数组R[1..n]垂直排列,每个记录R看作是重量为R.key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。 (1)初始 R[1..n]为无序区。 (2)第一趟扫描 从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者在上,则交换二者的位置。即依次比较(R[n],R[n-1]),(R[n-1],R[n-2]),…,(R[2],R[1]);对于每对气泡(R[j+1],R[j]),若R[j+1].key<R[j].key,则交换R[j+1]和R[j]的内容。 第一趟扫描完毕时,"最轻"的气泡就飘浮到该区间的顶部,即关键字最小的记录被放在最高位置R[1]上。 (3)第二趟扫描 扫描R[2..n]。扫描完毕时,"次轻"的气泡飘浮到R[2]的位置上…… 最后,经过n-1 趟扫描可得到有序区R[1..n] 注意: 第i趟扫描时,R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时,该区中最轻气泡飘浮到顶部位置R上,结果是R[1..i]变为新的有序区。 2、冒泡排序过程示例 对关键字序列为49 38 65 97 76 13 27 49的文件进行冒泡排序的过程 3、排序算法 (1)分析 因为每一趟排序都使有序区增加了一个气泡,在经过n-1趟排序之后,有序区中就有n-1个气泡,而无序区中气泡的重量总是大于等于有序区中气泡的重量,所以整个冒泡排序过程至多需要进行n-1趟排序。 若在某一趟排序中未发现气泡位置的交换,则说明待排序的无序区中所有气泡均满足轻者在上,重者在下的原则,因此,冒泡排序过程可在此趟排序后终止。为此,在下面给出的算法中,引入一个布尔量exchange,在每趟排序开始前,先将其置为FALSE。若排序过程中发生了交换,则将其置为TRUE。各趟排序结束时检查exchange,若未曾发生过交换则终止算法,不再进行下一趟排序。 (2)具体算法 void BubbleSort(SeqList R) { //R(l..n)是待排序的文件,采用自下向上扫描,对R做冒泡排序 int i,j; Boolean exchange; //交换标志 for(i=1;i<n;i++){ //最多做n-1趟排序 exchange=FALSE; //本趟排序开始前,交换标志应为假 for(j=n-1;j>=i;j--) //对当前无序区R[i..n]自下向上扫描 if(R[j+1].key<R[j].key){//交换记录 R[0]=R[j+1]; //R[0]不是哨兵,仅做暂存单元 R[j+1]=R[j]; R[j]=R[0]; exchange=TRUE; //发生了交换,故将交换标志置为真 } if(!exchange) //本趟排序未发生交换,提前终止算法 return; } //endfor(外循环) } //BubbleSort 4、算法分析 (1)算法的最好时间复杂度 若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值: Cmin=n-1 Mmin=0。 冒泡排序最好的时间复杂度为O(n)。 (2)算法的最坏时间复杂度 若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值: Cmax=n(n-1)/2=O(n2) Mmax=3n(n-1)/2=O(n2) 冒泡排序的最坏时间复杂度为O(n2)。 (3)算法的平均时间复杂度为O(n2) 虽然冒泡排序不一定要进行n-1趟,但由于它的记录移动次数较多,故平均时间性能比直接插入排序要差得多。 (4)算法稳定性 冒泡排序是就地排序,且它是稳定的。 5、算法改进 上述的冒泡排序还可做如下的改进: (1)记住最后一次交换发生位置lastExchange的冒泡排序 在每趟扫描中,记住最后一次交换发生的位置lastExchange,(该位置之前的相邻记录均已有序)。下一趟排序开始时,R[1..lastExchange-1]是有序区,R[lastExchange..n]是无序区。这样,一趟排序可能使当前有序区扩充多个记录,从而减少排序的趟数。具体算法【参见习题】。 (2) 改变扫描方向的冒泡排序 ①冒泡排序的不对称性 能一趟扫描完成排序的情况: 只有最轻的气泡位于R[n]的位置,其余的气泡均已排好序,那么也只需一趟扫描就可以完成排序。 【例】对初始关键字序列12,18,42,44,45,67,94,10就仅需一趟扫描。 需要n-1趟扫描完成排序情况: 当只有最重的气泡位于R[1]的位置,其余的气泡均已排好序时,则仍需做n-1趟扫描才能完成排序。 【例】对初始关键字序列:94,10,12,18,42,44,45,67就需七趟扫描。 ②造成不对称性的原因 每趟扫描仅能使最重气泡"下沉"一个位置,因此使位于顶端的最重气泡下沉到底部时,需做n-1趟扫描。 ③改进不对称性的方法 在排序过程中交替改变扫描方向,可改进不对称性。 勤奋一点网上都可找到,这是帮你拷的。祝你进步。

祁同伟 2019-12-02 01:17:20 0 浏览量 回答数 0

回答

Linux内核栈溢出(stack overflow)问题 最近一段时间在设计和开发一个Linux内核模块,进入到最后的正确性测试与稳定性测试阶段。在这个阶段发现了一个非常有意思的问题,堆栈溢出(stack overflow)。Linux内核堆栈溢出之后直接导致了系统kernel Panic。由于导致stack overflow的原因是递归调用导致的,所以,最后通过调试串口导出的kernel panic信息很快就定位问题所在了,否则这样的问题还真是很难调试和发现。通过这次bug,我们应该记住的是:Linux内核stack资源是有限的,而递归调用将大量消耗stack资源,因此在内核编程中尽量少用递归算法,否则将会导致出乎意料的一些问题。依次类推,为了减少stack资源的消耗,程序的局部变量定义的不要太大,否则也将会消耗大量stack资源,从而导致内核程序的不稳定。 为了解决递归调用导致的问题,我将递归算法改写成了非递归算法,解决了stack overflow的问题。在此介绍一下递归算法改写成非递归算法的一些思想。在项目实现过程中,需要对IO请求进行按顺序排队,因此采用了效率较高并且实现简单的快速排序算法,该算法是一种分治算法,即将排序队列进行切分,分解成一系列的小问题进行求解,针对这种问题,很容易采用递归的办法进行实现,伪代码描述如下: /* qs_sort实现从小到大的排序 */ Struct bio qs_sort(struct bio_list *list_head, struct bio *bio_tail) { Struct bio_list *less_list, *large_list; Struct bio *middle_bio; /* 递归调用结束点,小问题求解完毕,直接返回最后一个元素 */ If (!list_head) { Return bio_tail; } /* 对队列进行切分,选择一个middle_bio,并且按照middle_bio将其切分成less_list队列和large_list队列 */ Split_list(list_head, less_list, large_list, &middle_bio); /* 采用递归的方法实现大队列的排序操作 */ Middle_bio->bi_next = qs_sort(large_list, bio_tail); /* 采用递归的方法实现小队列的排序操作 */ Return qs_sort(less_list, middle_bio); }

liujae 2019-12-02 01:24:29 0 浏览量 回答数 0

回答

以下是我查到的资料   算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法。 算法可以宏泛的分为三类:   有限的,确定性算法 这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务,但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。   有限的,非确定算法 这类算法在有限的时间内终止。然而,对于一个(或一些)给定的数值,算法的结果并不是唯一的或确定的。   无限的算法 是那些由于没有定义终止定义条件,或定义的条件无法由输入的数据满足而不终止运行的算法。通常,无限算法的产生是由于未能确定的定义终止条件。 算法设计与分析的基本方法 1.递推法 2.递归递归指的是一个过程:函数不断引用自身,直到引用的对象已知 3.穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从众找出那些符合要求的候选解作为问题的解。 4.贪婪法贪婪法是一种不追求最优解,只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况,所以贪婪法不要回溯。 5.分治法把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 6.动态规划法 动态规划是一种在数学和计算机科学中使用的,用于求解包含重叠子问题的最优化问题的方法。其基本思想是,将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础,被广泛应用于计算机科学和工程领域。 7.迭代法迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题(一般是解方程或者方程组)的过程,为实现这一过程所使用的方法统称为迭代法。

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

回答

2.1基于词频统计——词位置加权的搜索引擎 利用关键词在文档中出现的频率和位置排序是搜索引擎最早期排序的主要思想,其技术发展也最为成熟,是第一阶段搜索引擎的主要排序技术,应用非常广泛,至今仍是许多搜索引擎的核心排序技术。其基本原理是:关键词在文档中词频越高,出现的位置越重要,则被认为和检索词的相关性越好。 1)词频统计 文档的词频是指查询关键词在文档中出现的频率。查询关键词词频在文档中出现的频率越高,其相关度越大。但当关键词为常用词时,使其对相关性判断的意义非常小。TF/IDF很好的解决了这个问题。TF/IDF算法被认为是信息检索中最重要的发明。TF(Term Frequency):单文本词汇频率,用关键词的次数除以网页的总字数,其商称为“关键词的频率”。IDF(Inverse Document Frequency):逆文本频率指数,其原理是,一个关键词在N个网页中出现过,那么N越大,此关键词的权重越小,反之亦然。当关键词为常用词时,其权重极小,从而解决词频统计的缺陷。 2)词位置加权 在搜索引擎中,主要针对网页进行词位置加权。所以,页面版式信息的分析至关重要。通过对检索关键词在Web页面中不同位置和版式,给予不同的权值,从而根据权值来确定所搜索结果与检索关键词相关程度。可以考虑的版式信息有:是否是标题,是否为关键词,是否是正文,字体大小,是否加粗等等。同时,锚文本的信息也是非常重要的,它一般能精确的描述所指向的页面的内容。 2.2基于链接分析排序的第二代搜索引擎 链接分析排序的思想起源于文献引文索引机制,即论文被引用的次数越多或被越权威的论文引用,其论文就越有价值。链接分析排序的思路与其相似,网页被别的网页引用的次数越多或被越权威的网页引用,其价值就越大。被别的网页引用的次数越多,说明该网页越受欢迎,被越权威的网页引用,说明该网页质量越高。链接分析排序算法大体可以分为以下几类:基于随机漫游模型的,比如PageRank和Repution算法;基于概率模型的,如SALSA、PHITS;基于Hub和Authority相互加强模型的,如HITS及其变种;基于贝叶斯模型的,如贝叶斯算法及其简化版本。所有的算法在实际应用中都结合传统的内容分析技术进行了优化。本文主要介绍以下几种经典排序算法: 1)PageRank算法 PageRank算法由斯坦福大学博士研究生Sergey Brin和Lwraence Page等提出的。PageRank算法是Google搜索引擎的核心排序算法,是Google成为全球最成功的搜索引擎的重要因素之一,同时开启了链接分析研究的热潮。 PageRank算法的基本思想是:页面的重要程度用PageRank值来衡量,PageRank值主要体现在两个方面:引用该页面的页面个数和引用该页面的页面重要程度。一个页面P(A)被另一个页面P(B)引用,可看成P(B)推荐P(A),P(B)将其重要程度(PageRank值)平均的分配P(B)所引用的所有页面,所以越多页面引用P(A),则越多的页面分配PageRank值给P(A),PageRank值也就越高,P(A)越重要。另外,P(B)越重要,它所引用的页面能分配到的PageRank值就越多,P(A)的PageRank值也就越高,也就越重要。 其计算公式为: PR(A):页面A的PageRank值; d:阻尼系数,由于某些页面没有入链接或者出链接,无法计算PageRank值,为避免这个问题(即LinkSink问题),而提出的。阻尼系数常指定为0.85。 R(Pi):页面Pi的PageRank值; C(Pi):页面链出的链接数量; PageRank值的计算初始值相同,为了不忽视被重要网页链接的网页也是重要的这一重要因素,需要反复迭代运算,据张映海撰文的计算结果,需要进行10次以上的迭代后链接评价值趋于稳定,如此经过多次迭代,系统的PR值达到收敛。 PageRank是一个与查询无关的静态算法,因此所有网页的PageRank值均可以通过离线计算获得。这样,减少了用户检索时需要的排序时间,极大地降低了查询响应时间。但是PageRank存在两个缺陷:首先PageRank算法严重歧视新加入的网页,因为新的网页的出链接和入链接通常都很少,PageRank值非常低。另外PageRank算法仅仅依靠外部链接数量和重要度来进行排名,而忽略了页面的主题相关性,以至于一些主题不相关的网页(如广告页面)获得较大的PageRank值,从而影响了搜索结果的准确性。为此,各种主题相关算法纷纷涌现,其中以以下几种算法最为典型。 2)Topic-Sensitive PageRank算法 由于最初PageRank算法中是没有考虑主题相关因素的,斯坦福大学计算机科学系Taher Haveli-wala提出了一种主题敏感(Topic-Sensitive)的PageRank算法解决了“主题漂流”问题。该算法考虑到有些页面在某些领域被认为是重要的,但并不表示它在其它领域也是重要的。 网页A链接网页B,可以看作网页A对网页B的评分,如果网页A与网页B属于相同主题,则可认为A对B的评分更可靠。因为A与B可形象的看作是同行,同行对同行的了解往往比不是同行的要多,所以同行的评分往往比不是同行的评分可靠。遗憾的是TSPR并没有利用主题的相关性来提高链接得分的准确性。 3)HillTop算法 HillTop是Google的一个工程师Bharat在2001年获得的专利。HillTop是一种查询相关性链接分析算法,克服了的PageRank的查询无关性的缺点。HillTop算法认为具有相同主题的相关文档链接对于搜索者会有更大的价值。在Hilltop中仅考虑那些用于引导人们浏览资源的专家页面(Export Sources)。Hilltop在收到一个查询请求时,首先根据查询的主题计算出一列相关性最强的专家页面,然后根据指向目标页面的非从属专家页面的数量和相关性来对目标页面进行排序。 HillTop算法确定网页与搜索关键词的匹配程度的基本排序过程取代了过分依靠PageRank的值去寻找那些权威页面的方法,避免了许多想通过增加许多无效链接来提高网页PageRank值的作弊方法。HillTop算法通过不同等级的评分确保了评价结果对关键词的相关性,通过不同位置的评分确保了主题(行业)的相关性,通过可区分短语数防止了关键词的堆砌。 但是,专家页面的搜索和确定对算法起关键作用,专家页面的质量对算法的准确性起着决定性作用,也就忽略了大多数非专家页面的影响。专家页面在互联网中占的比例非常低(1.79%),无法代表互联网全部网页,所以HillTop存在一定的局限性。同时,不同于PageRank算法,HillTop算法的运算是在线运行的,对系统的响应时间产生极大的压力。 4)HITS HITS(Hyperlink Induced Topic Search)算法是Kleinberg在1998年提出的,是基于超链接分析排序算法中另一个最著名的算法之一。该算法按照超链接的方向,将网页分成两种类型的页面:Authority页面和Hub页面。Authority页面又称权威页面,是指与某个查询关键词和组合最相近的页面,Hub页面又称目录页,该页面的内容主要是大量指向Authority页面的链接,它的主要功能就是把这些Authority页面联合在一起。对于Authority页面P,当指向P的Hub页面越多,质量越高,P的Authority值就越大;而对于Hub页面H,当H指向的Authority的页面越多,Authority页面质量越高,H的Hub值就越大。对整个Web集合而言,Authority和Hub是相互依赖、相互促进,相互加强的关系。Authority和Hub之间相互优化的关系,即为HITS算法的基础。 HITS基本思想是:算法根据一个网页的入度(指向此网页的超链接)和出度(从此网页指向别的网页)来衡量网页的重要性。在限定范围之后根据网页的出度和入度建立一个矩阵,通过矩阵的迭代运算和定义收敛的阈值不断对两个向量Authority和Hub值进行更新直至收敛。 实验数据表明,HITS的排名准确性要比PageRank高,HITS算法的设计符合网络用户评价网络资源质量的普遍标准,因此能够为用户更好的利用网络信息检索工具访问互联网资源带来便利。 但却存在以下缺陷:首先,HITS算法只计算主特征向量,处理不好主题漂移问题;其次,进行窄主题查询时,可能产生主题泛化问题;第三,HITS算法可以说一种实验性质的尝试。它必须在网络信息检索系统进行面向内容的检索操作之后,基于内容检索的结果页面及其直接相连的页面之间的链接关系进行计算。尽管有人尝试通过算法改进和专门设立链接结构计算服务器(Connectivity Server)等操作,可以实现一定程度的在线实时计算,但其计算代价仍然是不可接受的。 2.3基于智能化排序的第三代搜索引擎 排序算法在搜索引擎中具有特别重要的地位,目前许多搜索引擎都在进一步研究新的排序方法,来提升用户的满意度。但目前第二代搜索引擎有着两个不足之处,在此背景下,基于智能化排序的第三代搜索引擎也就应运而生。 1)相关性问题 相关性是指检索词和页面的相关程度。由于语言复杂,仅仅通过链接分析及网页的表面特征来判断检索词与页面的相关性是片面的。例如:检索“稻瘟病”,有网页是介绍水稻病虫害信息的,但文中没有“稻瘟病”这个词,搜索引擎根本无法检索到。正是以上原因,造成大量的搜索引擎作弊现象无法解决。解决相关性的的方法应该是增加语意理解,分析检索关键词与网页的相关程度,相关性分析越精准,用户的搜索效果就会越好。同时,相关性低的网页可以剔除,有效地防止搜索引擎作弊现象。检索关键词和网页的相关性是在线运行的,会给系统相应时间很大的压力,可以采用分布式体系结构可以提高系统规模和性能。 2)搜索结果的单一化问题 在搜索引擎上,任何人搜索同一个词的结果都是一样。这并不能满足用户的需求。不同的用户对检索的结果要求是不一样的。例如:普通的农民检索“稻瘟病”,只是想得到稻瘟病的相关信息以及防治方法,但农业专家或科技工作者可能会想得到稻瘟病相关的论文。 解决搜索结果单一的方法是提供个性化服务,实现智能搜索。通过Web数据挖掘,建立用户模型(如用户背景、兴趣、行为、风格),提供个性化服务。

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