精华内容
下载资源
问答
  • 基本数据结构中各种排序比较(时间复杂度,空间复杂度和稳定性) 插入排序   插入类的排序就好像是军训时来了一个迟到的同学,整个同学会“插入”到队伍的合适位置。 1.直接插入排序   每趟将一个新的关键字按照...

    基本数据结构中各种内部排序比较(时间复杂度,空间复杂度和稳定性)

    插入排序

      插入类的排序就好像是军训时来了一个迟到的同学,这个同学会“插入”到队伍的合适位置。
    1.直接插入排序
      每趟将一个新的关键字按照值的大小比较插入到已经有序的队伍中,直到所有的关键字都被插入有序序列。
    2.折半插入排序
      这里的插入方式和直接插入排序一样,区别在比较方法不一样,这里是用折半查找法来查找插入位置。与直接插入相比较,查找位置的效率大大增加,插入时移动次数都是一样的。
    3.希尔排序
      又叫做缩小增量排序,是将待排序列按照某种规则(增量)分成几个子序列,分别对这几个子序列进行直接插入排序,然后将增量减半,再分为几个子序列进行直接插入排序,当增量减少为1时,可以直接将其理解为直接插入排序,这时所得序列为有序序列。
      那直接用直接插入排序不就好了吗,为什么会用到希尔排序,举这样一个例子:7 9 8 5 4 0 6 2 3 1
    以增量5分割序列,我们将这个序列分为5个子序列:
    子1:7       0
    子2: 9       6
    子3:  8       2
    子4:   5       3
    子5:    4       1
    将子序列分别进行直接插入排序:
    子1:0       7
    子2: 6       9
    子3:  2       8
    子4:   3       5
    子5:    1       4
    得到序列:0 6 2 3 1 7 9 8 5 4
      不难看出大一点的数基本被排在了后面,虽然这是一个特例,但是每趟希尔排序都会使整个序列变得更有序,整体上是减少了直接插入排序移动次数,使排序效率增高。
    增量的选取注意:增量序列的最后一个值一定取1,增量序列中的值应尽量们没有除1之外的公因子。

    选择排序

      选择类排序的核心是“选择”,即每一趟排序都会选择出最大或最小的来放到队头或者队尾,就像军训中会让个子最小的站到队头,然后在其他人中再找到最小的,放在队头,直到最后一个,就得到一个有序序列。
    1.简单选择排序
      就像例子中讲的那样,简单选择排序就是选择其中最小(最大)的值,选择的关键就是和所有的值进行比较,比任何其他值都小的就是最小值(最大也一样),将其插入有序队列的队尾就可以了。
    2.堆排序
      堆是一种数据结构,可以将其看作是一棵完全二叉树,满足:任何一个非叶子结点的值都不大于(或不小于)其左右孩子结点的值。若父亲大孩子小,叫做大顶堆(大根堆),反之,叫做小顶堆(小根堆)。一次堆排序就是将无序序列调整为符合堆定义的完全二叉树,然后将“最大”或者“最小”值与最后一个值交换位置,再进行下一次堆排序。这样每次堆排序的目的就是将无序序列中断最大(最小)值找出来。

    交换排序

      交换类排序的核心是“交换”,就像是军训时刚来的时候,队伍都是随便站的,这时教官会要求同学按身高排序,一个个子高的同学就会不停的和他身边的同学进行比较,交换位置直至合适他自己的位置。
      交换类排序和插入类排序的区别在于交换类排序每趟执行都会将一个元素放置到它最终的位置上去,而插入类排序一趟排序并不能确保一个关键字到达其最终位置,对于1,2,3,0,这样的最小元素最后插入的情况,整个序列没有任何一个关键字在最后一趟排序前到达其最终位置。
    1.冒泡排序
      冒泡就好像它自己的名字,在冒泡排序过程里,大元素好像石头一样逐渐沉底,小元素像气泡一样逐渐向上,但是每一次冒泡都会使一个元素放到它最终位置上去,冒泡排序的结束条件是一趟排序里面没有发生关键字的交换。
    冒泡排序就是两两比较和交换,以非递减排序为例,首先第一个元素和第二个比较,前面的大,就交换,否则不交换;接着比较第二个和第三个元素,以此类推,到最后一个元素为完成了一趟冒泡排序。
    2.快速排序
      快速排序是通过多次“划分”操作实现。和冒泡排序一样,快速排序的一次划分会将一个元素放在它最终位置上,虽然时间复杂度也有和其一样的排序算法,但同级别算法的基本操作执行次数多项式为X*nlog2n(X是系数),快速排序的X是最小的,所以是同级别中最好的,因此得名。快速排序是典型的以空间为代价减少时间,在其递归算法中需要用到栈的辅助。
      

    二路归并排序

      归并类排序就是将两个或者两个以上的有序序列合并成一个新的有序序列,这个例子不太好举,如果硬是拿之前的例子套的话,就像是队伍中前后两个人一组先排序,然后四个,然后八个,直到全部排好。算法上这是一种分而治之的过程,从宏观上看就是将队伍分成两部分,每部分再进行分治,这样每次总和时都会认为时两个有序序列的排序,但是微观上就是例子所举的那样,其实是子序列从多到少。这部分有疑问,建议看看算法书中的分治法。

    基数排序

      上面几种排序都是基于比较和交换,而基数排序是不基于比较的,它的思想是“多关键字排序”。就好像扑克牌有花色和数字,先按花色分堆,再按照A到K的顺序摘出来,就会得到有序序列。
      基数主要有两种实现方式:最高位优先(MSD)和最低位优先(LSD),最高位优先是先按最高位排成若干子序列,再对每个子序列按次高位排序;最低位优先不必分子序列,每次排序全体都会参与,不基于比较的,而是通过“分配”和“收集”,原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

    稳定性

      稳定性是指当待排序序列中有两个或两个以上相同的关键字时,排序前和排序后这些关键字的相对位置有没有改变,如果改变就说它不稳定,如果不改变就说它是稳定的。稳定性只是一个算法性质,并不能衡量一个算法的优劣。

    排序类型 平均时间复杂度 平均空间复杂度 稳定性 是否支持顺序存储和链式存储
    直接插入法 O(n2) O(1) 稳定 都支持
    折半插入法 O(n2) O(1) 稳定 顺序存储
    希尔排序 O(n2) O(1) 不稳定 顺序存储
    简单选择排序 O(n2) O(1) 不稳定 都支持
    堆排序 O(nlog2n) O(1) 不稳定 都支持
    冒泡排序 O(n2) O(1) 稳定 都支持
    快速排序 O(nlog2n) O(log2n) 不稳定 都支持
    二路归并排序 O(nlog2n) O(n) 稳定 都支持
    基数排序 O(d(n+rd)) O(rd) 稳定 都支持

    复习时部分总结,有错误欢迎指正,立改,谢谢!

    展开全文
  • 在这只是归纳总结一下,便于记忆:内部排序法的性能比较排序算法时间复杂度(平均情况)时间复杂度(最坏情况)空间复杂度稳定性选择排序法O(n^2)O(n^2)O(1)不稳定插入排序法O(n^2)O(n^2)O(1)稳定折半插入排序法O(n^...

    基于最近笔试遇到很多求解复杂度的问题,在这只是归纳总结一下,便于记忆:

    内部排序法的性能比较
    排序算法时间复杂度(平均情况)

    时间复杂度(最坏情况)

    空间复杂度稳定性
    选择排序法O(n^2)O(n^2)O(1)不稳定
    插入排序法O(n^2)O(n^2)O(1)稳定
    折半插入排序法O(n^2)O(n^2)O(1)不稳定
    希尔排序法O(n^1.25)O(n^1.25)O(1)不稳定
    冒泡排序法O(n^2)O(n^2)O(1)稳定
    快速排序法O(nlog2n)O(n^2)O(nlog2n)不稳定
    堆排序法O(nlog2n)O(n^2)O(1)不稳定
    归并排序法O(nlog2n)O(n^2)O(n)稳定
    基数排序法O(n×d)O(n×d)O(n)稳定
    快速排序法的平均执行时间较少,但是在最坏的情况下它的性能会发生退化,这时不如用堆排序和归并排序法效率高。当序列长度较短时,可采用容易实现的选择排序、插入排序或者冒泡排序法。当序列长度较长时,宜采用快速排序、堆排序或者归并排序。
    展开全文
  • 时间复杂度 顺序查找 O(n) 算法简单,适应面广,稳定算法 折半查找 O(log2n) 针对有序的序列表,不稳定 分块查找 介于顺序查找和折半查找之间 针对有序表,不稳定算法 平衡二叉树查找 ...
    查找算法 时间复杂度  
    顺序查找 O(n) 算法简单,适应面广,稳定算法
    折半查找 O(log2n) 针对有序的序列表,不稳定
    分块查找 介于顺序查找和折半查找之间 针对有序表,不稳定算法
    平衡二叉树查找 O(log2n) 插入与删除的复杂度也相同


    排序法

    平均时间

    最差情形

    稳定度

    额外空间

    冒泡

    O(n2)    

    O(n2) 

    稳定

    O(1)

    n小时较好

    交换 O(n2) O(n2) 

    不稳定 O(1)

    n小时较好

    选择

    O(n2)  

    O(n2)

    不稳定 O(1)

    n小时较好

    插入 O(n2)

    O(n2)

    稳定 O(1) 大部分已排序时较好
    Shell

    O(nlogn)

    O(ns)1<s<2

    不稳定 O(1) s是所选分组 
    快速 O(nlogn) 

    O(n2)

    不稳定 O(nlogn)

    n大时较好

    归并 O(nlogn) 

    O(nlogn)

    稳定 O(1) n大时较好
    O(nlogn) 

    O(nlogn)

    不稳定 O(1) n大时较好
    基数 O(logRB)

    O(nlogRB)

    稳定 O(n) B是真数(0-9),R是基数(个十百)

    树图

    时间复杂度
    克鲁斯卡尔 O(eloge)
    普里姆 O(n2)
    迪杰斯特拉 O(n2)
    拓扑排序 O(n+e)
    关键路径

    O(n+e)


    转载于:https://www.cnblogs.com/bishi/p/5699018.html

    展开全文
  • 之前的文章介绍了简单插入排序法。我们知道插入排序的核心操作是在子序列中找到要插入的位置并插入。其实子序列本身是有序的,所以在有序的子序列中,我们完全可以使用折半查找,而不是粗暴的遍历,进而达到降低时间...

    之前的文章介绍了简单插入排序法。我们知道插入排序的核心操作是在子序列中找到要插入的位置并插入。其实子序列本身是有序的,所以在有序的子序列中,我们完全可以使用折半查找,而不是粗暴的遍历,进而达到降低时间复杂度的目的。
    在这里插入图片描述
    首先简单介绍下折半查找。折半查找的用途非常广泛,可以高效的解决很多实际问题。而且时间复杂度仅有O(log2n)O(\log_2n)
    在这里插入图片描述
    既然已经明白了原理,下面我就直接贴代码了,使用JS来实现,过程可以参考代码中的注释

    function binIntertSort(seq) {
    	let low, mid, high, i, j, temp;
    	// 从第二个元素开始,第一个本身就是有序的。
    	for(i=1;i<seq.length;i++) {
    		temp = seq[i]; // 待插入的元素
    		low = 0; // low 在每一趟查找中都是0
    		high = i - 1; // high 就是当前需要插入的元素的前一个位置
    		while(low <= high) { // 若low不再小于high了,那么就找到了待插入的位置
    			mid = Math.floor((low + high) / 2) // 中间位置
    			if(temp < seq[mid]) {
    				high -= 1; // 下一趟再找前半序列
    			} else {
    				low += 1; // 否则找后半序列
    			}
    		}
    		// 在即将插入的位置后边的所有元素依次前移一个位置,最终会空出要插入的位置。
    		for (j=i;j>low;j--) {
    			seq[j] = seq[j-1];
    		}
    		// 插入!
    		seq[j] = temp;
    	}
    }
    binIntertSort(seq)
    console.log(seq)
    // [1, 2, 3, 4, 5, 6, 6, 7, 9 ]
    

    相较于前文的简单插入排序法,折半查找插入排序,时间复杂度由原来的O(n2)O(n^{2}) 降低到了O(nlog2n)O(n\log_2n),当然这是最好的情况下。在实践中,如果需要稳定的低时间复杂度的算法。可以考虑后边介绍的堆积排序。

    展开全文
  • 时间复杂度

    2020-03-16 22:20:44
    时间复杂度 时间复杂度定义说是基本语句的实现次数(if ...在折半插入排序里面 def Bsearch(arr, low, high, k): # 二分查找 while low <= high: mid = (low + high) // 2 if arr[mid] == k: return mid ...
  • 折半插入排序

    千次阅读 2016-06-08 22:03:31
    折半插入排序与直接插入排序相比,紧减少了关键字之间的比较次数,而数据元素的移动次数不变,折半插入排序时间复杂度仍未O(n2).public class InsertSort { /*使用折半插入进行排序*/ public static v
  • 查找时间复杂度总结

    千次阅读 2020-07-13 16:19:23
    1.二叉排序树 如果二叉排序树是平衡的,则n个节点的二叉排序树的高度为,其查找效率... 排序法 最好时间分析 最差时间分析 平均时间复杂度 稳定度 空间复杂度 ...
  • 1-时间复杂度分析

    2020-07-20 00:32:44
    文章目录概念函数渐进增长大O记最坏情况时间复杂度排序非函数调用函数调用计算方法循环主体中的变量参与循环条件的判断运算时间中的对数折半查找欧几里得算法幂运算循环主体中的变量与循环条件无关非递归程序递归...
  • 最近学习了一下排序算法,写篇文章记录一下,详细讲解网上有很多,可以自己去查 折半插入排序Binary Insert Sort 折半插入排序是在插入...折半插入排序时间复杂度是O(n²),是稳定排序。 1 2 3 4 5 6 [ 18 22 ...
  • python-算法时间复杂度和空间复杂度

    千次阅读 2018-08-06 17:08:08
    大O表示 O 名称 举例 1 常量时间 一次赋值 logn 对数时间 折半查找 n 线性时间 线性查找 nlogn 对数线性时间 快速排序 n**2 平方 两重循环 n**3 立方 三重循环 2**n ...
  • 编写函数:(1)用选择将数组排成降序的函数----SUB1;(2)用折半查找查找某数是否在给定的数组当中的函数----SUB2。...选择与冒泡排序时间复杂度都是O(n2),在编写降序排列函数时,最后两数组
  • 时间复杂度折半插入排序仅仅是减少了比较元素的次数,约为O(nlogn),而且该比较次数与待排序表的初始状态无关,仅取决于表中的元素个数n;而元素的移动次数没有改变,它依赖于待排序表的初始状态。因
  • 插入类排序可以分为三种:直接插入、折半...时间复杂度: 直接插入排序:O(n^2)、折半插入排序:O(n^2)、希尔排序:O(n^3/2); 下面是相关的示例: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2
  • 由于插入排序的基本操作是在一个有序表中...时间复杂度为O(n^2)。理解:依次将每个待排序的记录插入到一个有序序列的合适位置。插入的位置是采用折半查找确定的。 void CInsertionSort::BinaryInsertion(void...
  • 常用的时间复杂度 1: 常量时间 一次赋值 2 log n: 对数时间 折半查找 n: 线性时间 线性查找 nlong n: 对数线性时间 快速排序 n方: 平方 两重循环 n三次方: 立方 三重循环 2的n次方: 指数 递归球菲波...
  • 折半查找(C语言实现)递归

    千次阅读 2019-11-25 16:31:10
    二分查找(又称为折半查找)是在有序序列中查找比较多的查找算法,...时间复杂度为O(lgn),查找速度相对顺序查找要快很多,但是查找的数据序列必须是有序序列(即数据是从小到大或从大到小排序的). 第一种方法 ...
  • 主要用于已经做了排序的数字,时间复杂度:log2n  直接贴代码 #include <stdio.h>#include <stdlib.h>int search(int search_num, int a[], int right){ int left = 0; int ret = -1; int mid; while...
  • 1 /*折半插入查找思想:每趟将一个带排序的元素作为关键字插入到已经排好的部分序列的适当位置上,查找适当位置的方法用折半查找 2 * 适合记录数较多的场景 3 * 在查找插入位置时节省了时间 4 * 在记录移动...
  • 这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。...
  • 算法 之 快速排序法

    2016-05-27 15:19:00
    快速排序算法:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此...时间复杂度 平均 n*logn function sort_half($a){ if(count($a)>1){ ...
  • 时间复杂度O(log2n),比较次数<=树的深度=log2n 顺序储存有序表 分块查找 块间有序,块内无序 因此块间可以用折半查找确定在哪一个块,再用顺序查找一个个看在块中哪个位置 二叉排序树 if左
  • //它的时间复杂度为O(n^2),虽然不及堆排序、快速排序的O(nlogn,底数为2),但是有两个优点:1.“编程复杂度”很低,很容易写出代码;2.具有稳定性,这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序...
  • //它的时间复杂度为O(n^2),虽然不及堆排序、快速排序的O(nlogn,底数为2),但是有两个优点:1.“编程复杂度”很低,很容易写出代码;2.具有稳定性,这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序...
  • 转自:... #include iostream>  using namespace std;.../**冒泡排序法**/  ...//它的时间复杂度为O(n^2),虽然不及堆排序、快速排序的O(nlogn,底数为2),但是有两个优点:1.“编程复杂度”
  • 数据结构之排序

    2019-12-18 17:27:10
    北航软件工程专业考研991数据结构...2.插入排序法(含折半插入排序法); 3.选择排序法; 4.(起)泡排序法; 5.谢尔(Shell)排序法; 6.快速排序法; 7.堆积(Heap)排序法,包括堆积的定义与构造; 1、插入排序法...

空空如也

空空如也

1 2 3 4
收藏数 79
精华内容 31
关键字:

折半排序法时间复杂度