算法
算法的特征
- 可以没有输入量
- 必须有输出量
- 有限时间
- 明确性，算法描述无歧义
- 有效性，可行的
几个简单的排序算法
关于数组，数组也是一种数据结构。
关于数组的一些运算，要注意：length≠'length' 。length是一个容器，而'length'是一个字符串，容器可以容纳字符串，容器、字符串可以赋值。
假设，length=0，此时a[length]=a['length']，因为 toString(n) 可以把数字转换为字符串，如 toString(0) 结果为 '0'
冒泡排序（Bubble Sort）
每次循环里相邻两个数值两两对比，按大小排序，大的继续与下一位数值进相对比。每一次循环可以确定一个最大值。
选择排序（Selection sort）
每次循环选定一个数值a与其他数值进行对比，若大于a，则继续对比，若小于a，则交换位置，假设这个数值为b，拿b与剩下的数值进行对比。每一次循环可以确认最小值。
插入排序（Insertion Sort）
每次循环新的数值与循环内的每个数值进行对比排序，插入循环内。每次循环结束，循环内的数值已排序好。
快排（Quicksort）
每次循环以某个数为基准，大的排右面，小的排左边。快排的循环效率会比以上的排序算法更高。
桶排序（Bucket sort）
设定有限的桶，将相同规律的数值依次放在相同的桶里。
数据结构
数据结构是指数据的结构，即是对象组成的各个要素是以什么样的额方式构建或组织起来。结构实际上是一种关系。
下面是几个基本的数据结构：
1.哈希（hash）
哈希的组成： （key:value）
哈希的应用例子有：计数排序、桶排序、基数排序。
- 计数排序
跟算法里冒泡排序、插入排序、选择排序、快排的原理都不同，他们是用比较法进行排序的，复杂度O(n²)；而计数排序是以哈希为工具进行排序，它的复杂度是O(n+max)。
将计数排序分为入桶、出桶两个大步骤。下面是计数排序的流程图：
计数排序流程图.png
-
基数排序（Radix sort）
将整数按“位数”切割，然后每个位数分别对比放入不同的桶内，多次入桶出桶。
这里是基数排序的动画演示（选择Radix sort） -
关于这几种排序的优缺点
① 计数排序比一般的比较类型排序效率会更高。
② 这几个排序一般都是针对正整数进行排序。
③关于桶排序，一般入桶后，桶内需配合其他排序进行。如果设定的桶太少，那么排序时间相应会更高，更消耗CPU。若设定的桶太多，效率会更高，但是会消耗内存。
④ 基数排序的桶是固定的，一共十个桶，需要多次入桶出桶，如果数值较大，用基数排序会更快。
2. 队列（Queue）
- 先进先出
- 可以用数组实现
- 类似生活中的排队
3.栈（Stack）
- 先进后出
- 可以用数组实现
- 类似盗梦空间
4.链表（Linked list）
let a = {
value:1,
next:{
value:2,
next:{
value:3
}
}
}
- 链表也是哈希，head:第一个哈希对象。node：链表分节点
- 与数组相比较，链表可以轻松地删除一组数据内随机一项，数组不可以。但是数组可以随机查询某个值。
5.树（tree）
- <html>也是一个树结构（DOM树）
-
层数、深度、节点
示例
这个树结构有3层，深度为2（根节点的深度为0），每一个点都是节点。
- 二叉树：每个节点最多只有2个分节点（左子树、右子树）。
假设二叉树的深度为n，则它的第k层最多可有2ᵏ个节点，一共最多可有（2ⁿ⁺¹-1）个节点。（n₀=0） -
满二叉树：除了最后一层没有任何子节点外，每层节点数都有2个子节点。
满二叉树
- 完全二叉树：除了最后一层外，每层节点都有两个子节点，且最后一层所有节点都连续集中在最左边。
完全二叉树
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树 - 可以用数值存二叉树，例子：堆（最大堆/最小堆/堆排序）
堆排序动画演示
网友评论