# 前端工作中遇到的数据结构和算法

## 一、数据结构及查找算法的实现

### 1.递归大法

``````function getElementById(node, id){
if(!node) return null;
console.log(node.id);
if(node.id === id) return node;
for(var i = 0; i < node.childNodes.length; i++){
var found = getElementById(node.childNodes[i], id);
if(found) return found;
}
return null;
}
getElementById(document, "id-data-structure");
``````

### 2、非递归：另一种深度优先算法

``````<div id="id-data-structure">
我是 body
</div>
``````
``````function getElementById(node, id){
while (node) {
if(node.id === id) return node;
node = nextNode(node);
}
}

function nextNode(node) {
if(node.children.length) {
return node.children(0)
}
if(node.nextElementSibling) {
return node.nextElementSibling;
}
while (node.parentNode) {
if(node.parentNode.nextElementSibling) {
return  node.parentNode.nextElementSibling;
}
}
return null;
}

getElementById(document, "id-data-structure");
``````

``````Map::iterator it = m_map.begin();
while(it != m_map.end()){
LOG(INFO) << it->key << " " << it->value->element->tagName();
++it;
}
``````

（1）本体函数：

``````NodeType* currentNode = collection.traverseToFirst();
unsigned currentIndex = 0;
while (currentNode) {
m_cachedList.push_back(currentNode);
currentNode = collection.traverseForwardToOffset(
currentIndex + 1, *currentNode, currentIndex);
}
``````

（2）nextNode函数实现下一个节点的查找

``````ElementType* element = Traversal<ElementType>::firstWithin(current);
while (element && !isMatch(*element))
element = Traversal<ElementType>::next(*element, &current, isMatch);
return element;
``````

Traversal :: next 函数， 即上面使用javacript实现的nextNode方法。

``````if (current.hasChildren())
return current.firstChild();
if (current == stayWithin)
return 0;
if (current.nextSibling())
return current.nextSibling();
return nextAncestorSibling(current, stayWithin);
``````

### 3、哈希结构及相关算法

（1）遍历查找

``````function sequentialSearch(sTable, targetPic) {
for (var i = sTable.length - 1; i >= 0 && sTable[i].id !== targetPic.id; --i);
return sTable[i];
}
``````

（2）使用javascript实现Hash查找

Hashtable是最常用的数据结构之一，然而，Javascript中并没有这种数据结构。通过使用Javascript的动态添加属性可以实现基于Hashtable的hash查询。

``````const picArray = [
{
picId : '123',
src : 'hhh'
},
{
picId : '456',
src : 'mmm'
}
];
``````

``````function Hashtable() {
this._hashValue = {};
}

Hashtable.prototype.add = function (inputArray) { //处理接口数据
for(let i = 0; i < inputArray.length; i++) {
this._hashValue[inputArray[i]['key']] = inputArray[i]['value'];
}
return this._hashValue;
}

Hashtable.prototype.get = function (key) { //根据id获得src
if(typeof key === 'string' && this._hashValue[key]) {
return this._hashValue[key];
}
}

const createHash = new Hashtable();

console.log(createHash._hashValue);
console.log(createHash.get('123')); // hhh
``````

• 使用哈希函数将被查找的键转换为数组的索引。在理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以哈希查找的第二个步骤就是处理冲突。
• 处理哈希碰撞冲突。

## 二、排序算法及javascript实现

（图一）

### 3.快速排序实现sort方法

• 先从数列中去除一个数作为“基准”（理论上可以随便选取一个数）
• 实现数组分区：将比这个”基准数“大的数放到“基准”的右边，小于或等于“基准数”的数放到“基准”的左边；
• 再对左右区间重复第二步，直到各区间只有一个数 算法实现：
``````/**
* Created by majie on 17-7-9.
*/

//经典 快速排序 的 实现

const quickSort = arr => {
if(arr.length <= 1) {
return arr;
}
const pivotIndex = Math.floor(arr.length / 2); //重要！！   算法思路中第一步 基准为位置 理论上可以任选
const pivot = arr.splice(pivotIndex, 1)[0];
const left = [];
const right = [];
arr.forEach((item, idx) => {
if(arr[idx] < pivot) {
left.push(arr[idx])
}else {
right.push(arr[idx])
}
})
return quickSort(left).concat([pivot], quickSort(right)); //连接 左数组、基准数和右数组
}

//  const getSort = quickSort([20,44,23,55,77,19]);
// console.log(getSort);

function testTime() {
console.time('经典排序时间');
quickSort([20,44,23,55,77,19]);
console.timeEnd('经典排序时间');
}
testTime(); // 0.173ms;
``````

``````/**
* Created by majie on 17-7-10.
*/
function quickSort(arr) {
function swap(arr, a, b) {
const temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
function partition(arr, low, high) {

let pivot = arr[low]; //选取固定 基准 为 arr[low]

let i = low, j = high;
while (i !== j) {
while (arr[j] >= pivot && i < j) {
j--;
}
while (arr[i] <= pivot && i < j) {
i++
}
if(i < j) {
swap(arr, i, j);
}
}
swap(arr, low, i); //将基准数归位
return i; //返回基准点
}
function Qsort(arr, low, high) {
let pivot;
if(low < high) {
pivot = partition(arr, low, high); //获得 基准的 位置
Qsort(arr, low, pivot - 1); // 对基准位置左边的元素进行排序
Qsort(arr, pivot + 1, high); // 对基准位置右边的元素进行排序
}
}
Qsort(arr, 0, arr.length - 1);
return arr;
}

function testTime() {
console.time('worst-case-quickSort排序时间');
quickSort([20,44,23,55,77,19]);
console.timeEnd('worst-case-quickSort排序时间');
}

const getSort = quickSort([20,44,23,55,77,19]);
console.log(getSort); [19, 20, 23, 44, 55, 77]

testTime(); //0.0193ms
``````

``````/**
* Created by majie on 17-7-10.
*/
function quickSort(arr) {
function swap(arr, a, b) {
const temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
function partition(arr, low, high) {
let middle = low + Math.ceil((high- low) / 2);
if(arr[low] > arr[high]) {
swap(arr, low, high)
}
if(arr[middle] > arr[high]) {
swap(arr, high, middle)
}
if(arr[middle] > arr[low]) {
swap(arr, middle, low)
}
let pivot = arr[low]; //这时 arr[low] 为左中右三个关键字的中间值

let i = low, j = high;
while (i <= j) { //从序列的两端交替和中间元素比较
while (arr[j] > pivot) {
j--;
}
while (arr[i] < pivot) {
i++
}
if(i <= j) {
swap(arr, i, j);
i++;
j--;
}
}
// swap(arr, low, i);
return i;
}
function Qsort(arr, low, high) {
let pivot;
if(arr.length > 1) {
pivot = partition(arr, low, high);
if(low < pivot - 1) {
Qsort(arr, low, pivot - 1);
}
if(pivot < high) {
Qsort(arr, pivot, high);
}

}
}
Qsort(arr, 0, arr.length - 1);
return arr;
}

function testTime() {
console.time('worst-case-quickSort排序时间');
quickSort([20,44,23,55,77,19]);
console.timeEnd('worst-case-quickSort排序时间');
}

const getSort = quickSort([20,44,23,55,77,19]);
console.log(getSort);  //[19,20,23,44,55,77]

testTime(); //0.022ms
``````

### 4.归并排序实现sort方法

（图二）

``````/**
* Created by majie on 2017/7/12.
*/
function merge(leftArr, rightArr){
const result = [];
while (leftArr.length > 0 && rightArr.length > 0){
//取出最小值，放到结果集中
if (leftArr[0] < rightArr[0])
result.push(leftArr.shift());
else
result.push(rightArr.shift());
}
return result.concat(leftArr).concat(rightArr); //合并，即“二路归并”
}

function mergeSort(array){
if (array.length === 1) return array; //设定 递归结束的标志

//将数组分成两部分
const middle = Math.floor(array.length / 2);
const left = array.slice(0, middle);
const right = array.slice(middle);

//递归调用并合并
return merge(mergeSort(left), mergeSort(right));
}

const arr = mergeSort([32,12,56,78,76,45,36]);
console.log(arr);   // [12, 32, 36, 45, 56, 76, 78]
function testTime() {
console.time('mergeSort排序时间');
mergeSort([32,12,56,78,76,45,36]);
console.timeEnd('mergeSort排序时间');
}
testTime(); //0.0249ms
``````

1 篇文章1 人订阅

0 条评论

## 相关文章

1982

1122

1985

1083

3407

3219

### 【JAVA零基础入门系列】Day3 Java基本数据类型

前两篇已经将开发环境搭建完成，如果你已经按之前的教程按部就班的完成了部署，那么世界上最优秀的编程语言之一和世界上最优秀的IDE之一已经出现在你的电脑上（此处...

1998

### flv格式详解+实例剖析

FLV（Flash Video）是现在非常流行的流媒体格式，由于其视频文件体积轻巧、封装播放简单等特点，使其很适合在网络上进行应用，目前主流的视频网站无一例外地...

1692

993

### 文本数字拆分技巧

Excel处理人员呢，最喜欢的就是规范化的表，那什么样子的表是规范的呢？给大家个图片感受一下！ ? 今天的要和大家分享的就是和规范化图表格格不入的，需要由不规...

3036