数据结构
链表：是由一组节点组成的数据结构,这些节点一起,在最简单的形式下，每个节点由数据和到序列中下一个节点的引用组成。
image.png
双向链表：是由一组称为节点的顺序链接记录组成的链接数据结构。每个节点包含两个字段，称为链接，它们是对节点序列中上一个节点和下一个节点的引用。开始节点和结束节点的上一个链接和下一个链接分别指向某种终止节点，通常是前哨节点或null。
image.png
队列：是一种特殊类型的抽象数据类型或集合。集合中的实体按顺序保存。队列基本操作有两种: 向队列的后端位置添加实体，称为入队，并从队列的前端位置移除实体，称为出队.
image.png
栈: 是一种抽象数据类型,用作表示元素的集合，具有push（ 添加元素到栈的顶端(末尾)）和pop（移除栈最顶端(末尾)）操，可类比于一组物体的堆叠。
image.png
哈希表:是一种实现 关联数组(associative array) 的抽象数据类型, 该结构可以将键映射值。哈希表使用哈希函数/散列函数来计算一个值在数组或桶(buckets)中或槽(slots)中对应的索引,可使用该索引找到所需的值。
image.png
堆: 是一种特殊的基于树的数据结构，堆“顶部”的没有父级节点的节点,被称之为根节点。堆分为“最大堆”和“最小堆”。在一个最小堆中, 如果 P是C的一个父级节点, 那么P的key(或value)应小于或等于C的对应值.
image.png
在一个 最大堆中，P的key(或value)大于 的对应值。
image.png
优先级队列:是一种抽象数据类型, 它类似于常规的队列或栈, 但每个元素都有与之关联的“优先级”。在优先队列中, 低优先级的元素之前前面应该是高优先级的元素。如果两个元素具有相同的优先级, 则根据它们在队列中的顺序是它们的出现顺序即可。字典树: 也称为数字树,有时候也被称为前缀树（因为它们可以通过前缀搜索）,它是一种搜索树--一种已排序的数据结构,通常用于存储动态集或键为字符串的关联数组。节点在树上的位置定义了与之关联的键。一个节点的全部后代节点都有一个与该节点关联的通用的字符串前缀, 与根节点关联的是空字符串。
image.png
树：是一种广泛使用的模拟分层树结构, 具有根节点和有父节点的子树,表示为一组链接节点。树可以被递归定义为一个(始于一个根节点的)节点集, 每个节点都是一个包含了值的数据结构, 除了值,还有该节点的节点引用列表(子节点)一起。 树的节点之间没有引用重复的约束。
image.png
二叉树：是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。
image.png
算法
1、冒泡排序
解释：两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。
bubbleSort = (list) = > {
let temp = 0; // 用来交换的临时数
// 要遍历的次数
for (let i = 0; i < list.length - 1; i++) {
// 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
for (let j = list.length - 1; j > i; j--) {
// 比较相邻的元素，如果前面的数大于后面的数，则交换
if (list[j - 1] > list[j]) {
temp = list[j - 1];
list[j - 1] = list[j];
list[j] = temp;
}
}
}
}
冒泡排序算法的性能
若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：Cmin = N - 1。所以，冒泡排序最好时间复杂度为O(N)。
若初始文件是反序的，需要进行 N -1 趟排序。每趟排序要进行 N - i 次关键字的比较(1 ≤ i ≤ N - 1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
Cmax = N(N-1)/2 = O(N2)
Mmax = 3N(N-1)/2 = O(N2)
冒泡排序的最坏时间复杂度为O(N2)。
因此，冒泡排序的平均时间复杂度为O(N2)。
算法稳定性：相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
2、选择排序
解释：两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。
function selectSort(nums){
let n = nums.length;
let minIndex,temp;
for(let i=0;i<n-1;i++){
minIndex = i;
for(let j=i+1;j<n;j++){
if(nums[minIndex]>nums[j]){
minIndex = j;
}
}
temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
}
return nums;
}
选择排序算法的性能
需要遍历数组才能找到峰值元素，所以复杂度与原始序列是否有序无关：
Cmax = n + n-1 + n-2 + … + 2 + 1 = n * (n+1) / 2 = O(N2)
冒泡排序的时间复杂度为O(N2)。
因此，冒泡排序的平均时间复杂度为O(N2)。
算法稳定性：无序部分最大元素和有序部分第一个元素相等的时候，可以将无序部分最大元素放在前面，所以选择排序是稳定的。
3、插入排序
解释：将未排序数据，对已排序数据序列从后向前扫描，找到对应的位置并插入。在从后向前扫描的过程中，需要反复的把已排序的元素逐步向后挪位，为新插入元素提供插入的位置。
function insertSort(arr) {
var len =arr.length;
for (var i=1;i<len; i++) {
var temp=arr[i];
var j=i-1;//默认已排序的元素
while (j>=0 && arr[j]>temp) { //在已排序好的队列中从后向前扫描
arr[j+1]=arr[j]; //已排序的元素大于新元素，将该元素移到一下个位置
j--;
}
arr[j+1]=temp;
}
return arr；
}
插入排序算法的性能
如果目标是升序排序，那么插入排序有最好情况和最坏情况两种。最好情况是，序列已经是升序排列，那么只需要比较n-1次，当序列是降序排列，那么比较次数是n(n-1)/2,赋值操作是比较次数减去（n-1）次。平均来说，插入算法时间复杂度是O(n^2)，空间复杂度是O（1）。
算法稳定性：无序部分最大元素和有序部分第一个元素相等的时候，可以将无序部分最大元素放在前面，所以插入排序是稳定的。
4、快速排序
解释：数组中指定一个元素作为标尺，比它大的放到该元素后面，比它小的放到该元素前面，如此重复直至全部正序排列。它利用了“分治”思想——把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
let QuickSort = (arr, low, high) => {
let temp;
let i = low;
let j = high;
if (low < high) {
temp = R[low]; //设置枢轴
while (i !== j) {
while (j > i && R[j] >= temp) {
--j;
}
if (i < j) {
R[i] = R[j];
++i;
}
while(i < j && R[i] < temp) {
++i;
}
if (i < j) {
R[j] = R[i];
--j;
}
}
R[i] = temp;
QuickSort(R, low, i-1);
QuickSort(R, i+1, high);
}
}
快速排序算法的性能
时间复杂度： 快速排序最优的情况就是每一次取到的元素都刚好平分整个数组，根据递归算法的时间复杂度公式：T[n] = aT[n/b] + f(n) ，得到快速排序最优的情况下时间复杂度为：O( nlogn ) ；最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了，所以时间复杂度为O(n2)，平均时间复杂度为O(nlog2n)。快速排序不是稳定排序。
网友评论