发表于: 2018-07-02 22:05:01

1 343


今天完成的事情

看了排序算法的相关知识

开始学习vue

看了一点vue文档

明天计划的事情

继续学习vue

遇到的问题

Vue项目生成失败vue @cli 3.0.0

1新建项目(Vue.js)

2填写项目信息(下一步)

3启动Vue CLI ...

4Vue CLI错误

错误信息:Error:ERROR TypeError:Cannot read property 'proxy' of undefined

解决办法:

在终端使用命令创建项目vue create <prj>,然后通过File |在Webstorm中打开项目根文件夹 打开

收获

排序算法

在计算机科学中,排序算法是一个算法的是把一个元素列表中特定顺序。最常用的订单是数字顺序和字典顺序。有效的排序对于优化需要输入数据在排序列表中的其他算法(如搜索和合并算法)的效率非常重要。对于规范化数据和生成人类可读的输出,排序通常也很有用。

 

分类

排序算法通常按以下方式分类:

计算复杂性(最差,平均和最佳行为)以列表(n)的大小计算。对于典型的串行排序算法,好的行为是O(n log n),并行排序在O(log 2 n)中,而不良行为是O(n 2)。(请参见大O符号。)串行排序的理想行为是O(n),但在一般情况下这是不可能的。最佳平行排序是O(log n)。基于比较的排序算法至少需要Ω(n log n)对大多数输入进行比较。 交换的计算复杂性(用于“就地”算法)。 内存使用情况(以及使用其他计算机资源)。特别是,一些排序算法是“ 就地 ”的。严格地说,就地排序只需要排序的项目之外的O(1)内存; 有时O(log(n))附加内存被认为是“就地”。 递归。一些算法是递归的或非递归的,而其他算法可能都是(例如合并排序)。 稳定性:稳定的排序算法使用相等的键(即值)保持记录的相对顺序。 它们是否是比较类型。比较排序仅通过比较两个元素与比较运算符来检查数据。 一般方法:插入,交换,选择,合并等。交换排序包括冒泡排序和快速排序。选择种类包括振动筛分类和堆排序。 算法是串行还是并行。 适应性:输入的预分类是否影响运行时间。考虑到这一点的算法已知是自适应的。

 

稳定性

稳定的排序算法按照它们在输入中出现的顺序对相同的元素进行排序。在对某些种类的数据进行排序时,在确定排序顺序时仅检查部分数据。

 

流行的排序算法

虽然有大量的排序算法,但在实际实现中,一些算法占主导地位。插入排序广泛用于小型数据集,而对于大型数据集则使用渐进式高效排序,主要是堆排序,合并排序或快速排序。有效的实现通常使用混合算法,将整体排序的渐近有效算法与递归底部的小列表的插入排序相结合。高度优化的实现使用更复杂的变体,例如在Android,Java和Python中使用的Timsort(合并排序,插入排序和其他逻辑),以及在某些C ++中使用的内插(快速排序和堆排序)分类 实现和.NET。

对于更多受限制的数据,例如固定时间间隔内的数字,分布排序(如计数排序或基数排序)被广泛使用。实践中很少使用气泡排序和变体,但在教学和理论讨论中常见。

在对物体进行物理排序时,例如按字母顺序排列的纸张(例如测试或书籍),人们通常会直观地将插入排序用于小型集合。对于较大的集合,人们通常首先会像首字母一样分拣,而多个分组可以对大集合进行实际排序。通常空间相对便宜,比如通过将物体散布在地板上或大面积上,但操作费用昂贵,特别是将物体移动很远的距离 - 参考的地点很重要。合并排序对于物理对象也很实用,特别是可以使用两只手,每个列表要合并一个,而其他算法(如堆排序或快速排序)不适合人类使用。其他算法,如库排序,这是一种留下空间的插入排序的变体,对于物理使用也是实用的。

 

冒泡排序和变种

冒泡排序和诸如鸡尾酒排序等变体是简单但非常低效的排序。因此它们在介绍性文章中经常被看到,并且由于易于分析而具有一些理论上的兴趣,但是它们很少用于实践,主要是娱乐兴趣。

快速排序

Quicksort是一个分而治之的 算法,它依赖于一个分区操作:对一个数组进行分区,选择一个称为枢轴的元素。小于枢轴的所有元素在它之前移动,所有更大的元素在它之后移动。这可以在线性时间和原位有效地完成。然后递归排序较小和较大的子列表。这产生了平均时间复杂度O(n log n),开销较低,因此这是一种流行的算法。快速排序的高效实现(使用就地分区)通常是不稳定的排序并且有点复杂,但它们是实践中最快的排序算法。结合其适度的O(log n)空间使用情况,quicksort是最流行的排序算法之一,并且可用于许多标准编程库。

希尔排序

Shellsort是由Donald Shell于1959 年发明的。它通过一次移动多个位置的无序元素来改进插入排序。Shellsort背后的概念是插入排序在O(k n)时间内执行,其中k是两个非现场元素之间的最大距离。这意味着它们通常在O(n 2)中执行,但对于大多数排序的数据,只有少数元素不合适,它们执行得更快。因此,通过首先对元素进行远程排序,逐步缩小要排序的元素之间的差距,最终的排序计算速度要快得多。一种实现可以被描述为将数据序列布置在二维阵列中,然后使用插入排序对阵列的列进行排序。

Shellsort的最坏情况时间复杂度是一个开放的问题,取决于使用的间隙序列,已知的复杂度范围从O(n 2)到O(n 4/3)和Θ(n log 2 n)。希尔排序是就地,仅需要的代码相对小的量,并且不要求使用的调用栈,使得其中存储器是非常宝贵的,例如在它在这两个情况下是有用的,嵌入式系统和操作系统内核。

 

桶排序

桶排序是一种分而治之的排序算法,它通过将一个数组分割成有限数量的桶来统计排序。然后,使用不同的排序算法,或者通过递归地应用桶排序算法,对每个桶进行单独排序。当数据集的元素均匀分布在所有存储桶中时,存储桶排序效果最佳。

 

合并排序

合并排序利用将已排序的列表合并成新的排序列表的便利。它首先比较每两个元素(即1与2,然后3与4 ......)并交换它们,如果第一个应该在第二个之后。然后它将每个结果列表中的两个合并为四个列表,然后将这些列表合并为四个,依此类推; 直到最后两个列表被合并到最终的排序列表中。在这里描述的算法中,这是第一个可以很好地扩展到非常大的列表的算法,因为它的最坏情况运行时间是O(n log n)。它也很容易应用于列表,而不仅仅是阵列,因为它只需要顺序访问,而不是随机访问。但是,它有另外的O(n)空间复杂性,并且在简单的实现中涉及大量副本。

合并排序在实际实现中看到了相对最近的普及,因为它用于复杂算法Timsort中,该算法用于编程语言Python 和Java(如JDK7 [23]中的标准排序例程) 。合并排序本身就是Perl中的标准例程,等等,至少从2000年起在JDK1.3中用于Java。



返回列表 返回列表
评论

    分享到