常见数据结构与排序算法之JavaScript实现

文章目录

1. 1. 常见数据结构
   1. 1.1. 数组
   2. 1.2. 列表
   3. 1.3. 栈
   4. 1.4. 队列
   5. 1.5. 链表
   6. 1.6. 字典
   7. 1.7. 散列
   8. 1.8. 集合
   9. 1.9. 二叉树和二叉查找树
   10. 1.10. 图和图算法
2. 2. 常见排序算法
   1. 2.1. 冒泡排序
   2. 2.2. 选择排序
   3. 2.3. 插入排序
   4. 2.4. 希尔排序
   5. 2.5. 归并排序
   6. 2.6. 快速排序

常见数据结构

数组

1) 简介

一个存储元素的线性集合，元素可以通过索引来任意存取。索引是该对象的属性，因为JS中对象的属性名必须是字符串，所以数字索引在内部被转换为字符串类型。

• Array是JavaScript 内置对象，同时也是一个构造函数，可以用它生成新数组。
• js中数组中的元素不必是同一种数据类型。用 Array.isArray() 来判断一个对象是否为数组。它可以弥补typeof运算符的不足 2) 实现

1. 数组的存取函数：(返回目标数组的某种变体)–Array.indexOf()、Array.lastIdexOf() 、Array.join() 、 Array.toString()、Array.concat() 、Array.slice()
2. 可变函数：(数组本身发生变化)–Array.push()、Array.unshift()、Array.pop()、Array.shift()、Array.splice()、Array.reverse() 、 Array.sort()
3. 迭代器方法：(对数组中的每个元素应用一个函数，可以返回一个值、一组值、或者一个数组)–不生成新数组：(执行某种操作，或返回一个值)Array.forEach(callback)、Array.every() 、Array.some() 、Array.reduce() 、Array.reduceRight() 。–生成新数组：Array.map()、Array.filter()。

列表

1) 简介

列表是一组有序的数据，每个列表中的数据项称为元素。在 JavaScript 中，列表中的元素 可以是任意数据类型。列表的抽象数据类型并未指明列表的存储结构，可使用一个数组 dataStore 来存储元素。

2) 实现列表类

function List() {    
	this.listSize = 0; //（属性） 列表的元素个数    
	this.pos = 0;  //（属性） 列表的当前位置 
	this.dataStore = []; // 初始化一个空数组来保存列表元素    
	this.clear = clear;  //（方法） 清空列表中的所有元素   
	this.find = find;    
	this.toString = toString; //（方法） 返回列表的字符串形式    
	this.insert = insert; //（方法） 在现有元素后插入新元素    
	this.append = append;  //（方法） 在列表的末尾添加新元素 
	this.remove = remove;  //（方法） 从列表中删除元素 
	this.front = front; //（方法） 将列表的当前位置设移动到第一个元素 
	this.end = end;   //（方法） 将列表的当前位置移动到最后一个元素 
	this.prev = prev;  //（方法） 将当前位置后移一位 
	this.next = next;  //（方法） 将当前位置前移一位 
	this.length = length;  //（属性） 返回列表中元素的个数 
	this.currPos = currPos; // （方法） 返回列表的当前位置 
	this.moveTo = moveTo;  //（方法） 将当前位置移动到指定位置
	this.getElement = getElement;   //（方法） 返回当前位置的元素 
}

栈

1) 简介

栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。栈被称为一种后入先出（LIFO，last-in-first-out）的数据结构。实现一个栈，当务之急是决定存储数据的底层数据结构。这里采用的是数组。

2) 实现栈类

function Stack() {    
	this.dataStore = [];    
	this.top = 0;    
	this.push = push;    //（方法）是将一个元素压入栈
	this.pop = pop;    //（方法）将一个元素弹出栈，pop() 方法虽然可以访问栈顶的元素，但是调用该方 法后，栈顶元素也从栈中被永久性地删除了
	this.peek = peek; //（方法）只返回栈顶元素，而不删除它   
	this.clear = clear;   //（方法）清除栈内所有元素 
	this.length = length;//（属性）记录栈内元素的个数
 }

队列

1) 简介

队列是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。队列是一种先进先出（First-In-First-Out，FIFO）的数据结构。

2) 实现栈类

function Queue() {    
	this.dataStore = [];    //
	this.enqueue = enqueue;    //方法向队尾添加一个元素
	this.dequeue = dequeue;    //方法删除队首的元素
	this.front = front;    //方法读取队首元素：
	this.back = back; //方法读取队尾的元素：
	this.toString = toString;   //方法显示队列内的所有元素：
	this.empty = empty; //方法判断队列是否为空：
}

链表

1) 简介

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一 个节点的引用叫做链。数组元素靠它们的位置进行引用，链表元素则是靠相互之间的关系进行引用。链表的尾元素指向一个 null 节点。许多链表的实现都在链表最前面有一个特殊节 点，叫做头节点(Header)。设计的链表包含两个类。Node 类用来表示节点，LinkedList 类提供了插入节点、删除 节点、显示列表元素的方法，以及其他一些辅助方法。

2) 实现栈类
Node类

//我们使用一个构造函数来创建节点，该构造函数设置了这两个属性的值：
function Node(element) {    
	this.element = element;  //属性 保存节点上的数据  
	this.next = null; //属性 保存指向下一个节点的 链接
}

LinkedList类 :提供了对链表进行操作的方法

function LList() {    
	this.head = new Node("head");  //属性 一个 Node 对象来保存该 链表的头节点。  
	this.find = find;    //方法 查找给定的值
	this.insert = insert;    //方法 插入节点
	this.remove = remove;    //方法 删除节点
	this.display = display; 
}

head 节点的 next 属性被初始化为 null，当有新元素插入时，next 会指向新的元素，所以在这里我们没有修改 next 的值。

字典

1) 简介

字典是一种以键 - 值对形式存储数据的数据结构。JavaScript 的 Object 类就是以字典的形式设计的。Dictionay 类的基础是 Array 类，而不是 Object 类。

2) 实现 Dictionary类

function Dictionary() {    
	this.add = add;    //法接受两个参数：键和值
	this.datastore = new Array();  //  
	this.find = find;    //方法以键作为参数，返回和其关联的值
	this.remove = remove;    //数同时删掉键和与其关联的值
	this.showAll = showAll; //显示字典中所有的键 - 值对
}

散列

1) 简介

散列是一种常用的数据存储技术，散列后的数据可以快速地插入或取用。散列使用的数据 结构叫做散列表。JS的散列表是基于数组进行设计的。使用散列表存储数据时，通过一个散列函数将键映射为一个数 字，这个数字的范围是 0 到散列表的长度。理想情况下，散列函数会将每个键值映射为一个唯一的数组索引。然而，键的数量是无限的，数组的长度是有限的（理论上，在 JavaScript 中是这样），一个更现实的目标是让散列函数尽量将键均匀地映射到数组中。即使使用一个高效的散列函数，仍然存在将两个键映射成同一个值的可能，这种现象称为 碰撞（collision），当碰撞发生时，我们需要有方案去解决。

2) 实现HashTable类

function HashTable() {    
	this.table = new Array(137);    this.simpleHash = simpleHash;    //散列函数
	this.showDistro = showDistro;  //用来显示散列表中的数据  
	this.put = put;    //将数据存入散列表， 
	//this.get = get; 
}

集合

1) 简介

集合（set）是一种包含不同元素的数据结构。集合中的元素称为成员。集合的两个最重要特性是：首先，集合中的成员是无序的；其次，集合中不允许相同成员存在。集合是由一组无序但彼此之间又有一定相关性的成员构成的，每个成员在集合中只能出现一次。Set类的实现基于数组，数组用来存储数据。

2) 实现HashTable类

function Set() {    
	this.dataStore = [];    
	this.add = add;    
	this.remove = remove;    
	this.size = size;    
	this.union = union;   //并集 
	this.intersect = intersect;  //交集  
	this.subset = subset;    //是否子集
	this.difference = difference;  //补集  
	this.show = show; 
}

二叉树和二叉查找树

1) 简介

树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构，以分层的方式 存储数据。树被用来存储具有层级关系的数据，比如文件系统中的文件；树还被用来存储有序列表。树由一组以边连接的节点组成。二叉树每个节点的子节点不允许超过两个。通过将子节点的个数限 定为 2，可以写出高效的程序在树中插入、查找和删除数据。二叉查找树由节点组成，所以我们要定义的第一个对象就是 Node。

2) 实现二叉查找树

function Node(data, left, right) {   
	this.data = data;    //保存数据
	this.left = left;    //也保存和其他节点的链接
	this.right = right;    
	this.show = show; //显示 保存在节点中的数据。
}  
function BST() {    
	this.root = null;//	将根节点初始化为 null，以此创建 一个空节点。
	this.insert = insert; //用来向树中加入新节点
	this.inOrder = inOrder; // 中序遍历
}

图和图算法

1) 简介

树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构，以分层的方式 存储数据。树被用来存储具有层级关系的数据，比如文件系统中的文件；树还被用来存储有序列表。树由一组以边连接的节点组成。二叉树每个节点的子节点不允许超过两个。通过将子节点的个数限 定为 2，可以写出高效的程序在树中插入、查找和删除数据。二叉查找树由节点组成，所以我们要定义的第一个对象就是 Node。

2) 实现二叉查找树

function Node(data, left, right) {   
	this.data = data;    //保存数据
	this.left = left;    //也保存和其他节点的链接
	this.right = right;    
	this.show = show; //显示 保存在节点中的数据。
}  
function BST() {    
	this.root = null;//	将根节点初始化为 null，以此创建 一个空节点。
	this.insert = insert; //用来向树中加入新节点
	this.inOrder = inOrder; // 中序遍历
}

常见排序算法

冒泡排序

1) 算法简介

冒泡排序是最慢的排序算法之一，使用这种排序算法排序时，数据值会像气泡一样从数组的一端漂 浮到另一端。假设正在将一组数字按照升序排列，较大的值会浮动到数组的右侧，而较小 的值则会浮动到数组的左侧。之所以会产生这种现象是因为算法会多次在数组中移动，比 较相邻的数据，当左侧值大于右侧值时将它们进行互换。

2) 算法描述和实现
具体算法描述如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤1~3，直到排序完成。

function bubbleSort(array) {
    if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {//”[object Array]”
        var len = array.length, temp;
        for (var i = 0; i < len - 1; i++) {
            for (var j = len - 1; j >= i; j--) {
                if (array[j] < array[j - 1]) {
                    temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                }
            }
        }
        return array;
    } else {
        return 'array is not an Array!';
    }
}

3) 算法时间复杂度分析

• 最佳情况 T(n) = O(n)
• 最坏情况 T(n) = O(n^2)
• 平均情况 T(n) = O(n^2)

  选择排序

  1) 算法简介

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2) 算法描述和实现
具体算法描述如下：

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

1. 初始状态：无序区为R[1..n]，有序区为空；
2. 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
3. n-1趟结束，数组有序化了。

function selectionSort(array) {
    if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
        var len = array.length, temp;
        for (var i = 0; i < len - 1; i++) {
            var min = array[i];
            for (var j = i + 1; j < len; j++) {
                if (array[j] < min) {
                    temp = min;
                    min = array[j];
                    array[j] = temp;
                }
            }
            array[i] = min;
        }
        return array;
    } else {
        return 'array is not an Array!';
    }
}

3) 算法时间复杂度分析

• T(n) = O(n^2)

  插入排序

  1) 算法简介

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

2) 算法描述和实现
具体算法描述如下：

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

function insertionSort(array) {
    if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
        for (var i = 1; i < array.length; i++) {
            var key = array[i];
            var j = i - 1;
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
        return array;
    } else {
        return 'array is not an Array!';
    }
}

3) 算法时间复杂度分析

• 最佳情况：输入数组按升序排列。T(n) = O(n)
• 最坏情况：输入数组按降序排列。T(n) = O(n^2)
• 平均情况：T(n) = O(n^2)

  希尔排序

  1) 算法简介

这个算法在插入排序的基础上做了很大的改善。希尔排序的核心理念与插入排序 不同，它会首先比较距离较远的元素，而非相邻的元素。和简单地比较相邻元素相比，使用这种方案可以使离正确位置很远的元素更快地回到合适的位置。当开始用这个算法遍历数据集时，所有元素之间的距离会不断减小，直到处理到数据集的末尾，这时算法比较的 就是相邻元素了。

2) 算法描述和实现
具体算法描述如下：

通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔。我们可以动态定义间隔序列，不过对于大部分的实际应用场景，算法 要用到的间隔序列可以提前定义好。有一些公开定义的间隔序列，使用它们会得到不同 的结果。这个间隔序列 是：701, 301, 132, 57, 23, 10, 4, 1。

function shellsort() {    
	for (var g = 0; g < this.gaps.length; ++g) {       
		for (var i = this.gaps[g]; i < this.dataStore.length; ++i) {          
			var temp = this.dataStore[i];          
			for (var j = i; j >= this.gaps[g] && this.dataStore[j-this.gaps[g]] > temp; j -= this.gaps[g]) {
				this.dataStore[j] = this.dataStore[j - this.gaps[g]];
			}                      
			this.dataStore[j] = temp;       
		}          
	} 
}

3) 算法时间复杂度分析

• 归并排序

  1) 算法简介

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。自顶向下的归并排序 、自底向上的归并排序 。

2) 算法描述和实现
具体算法描述如下：

1. 把长度为n的输入序列分成两个长度为n/2的子序列；
2. 对这两个子序列分别采用归并排序；
3. 将两个排序好的子序列合并成一个最终的排序序列。

function mergeSort(array, p, r) {
    if (p < r) {
        var q = Math.floor((p + r) / 2);
        mergeSort(array, p, q);
        mergeSort(array, q + 1, r);
        merge(array, p, q, r);
    }
}
function merge(array, p, q, r) {
    var n1 = q - p + 1, n2 = r - q, left = [], right = [], m = n = 0;
    for (var i = 0; i < n1; i++) {
        left[i] = array[p + i];
    }
    for (var j = 0; j < n2; j++) {
        right[j] = array[q + 1 + j];
    }
    left[n1] = right[n2] = Number.MAX_VALUE;
    for (var k = p; k <= r; k++) {
        if (left[m] <= right[n]) {
            array[k] = left[m];
            m++;
        } else {
            array[k] = right[n];
            n++;
        }
    }
}

3) 算法时间复杂度分析

• 最佳情况：T(n) = O(n)
• 最差情况：T(n) = O(nlogn)
• 平均情况：T(n) = O(nlogn)

快速排序

1) 算法简介

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

2) 算法描述和实现
具体算法描述如下：

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

1. 从数列中挑出一个元素，称为 “基准”（pivot）；
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
   3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

//方法一
function quickSort(array, left, right) {
    if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' && typeof left === 'number' && typeof right === 'number') {
        if (left < right) {
            var x = array[right], i = left - 1, temp;
            for (var j = left; j <= right; j++) {
                if (array[j] <= x) {
                    i++;
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
            quickSort(array, left, i - 1);
            quickSort(array, i + 1, right);
        };
    } else {
        return 'array is not an Array or left or right is not a number!';
    }
}  
var aaa = [3, 5, 2, 9, 1];
quickSort(aaa, 0, aaa.length - 1);
console.log(aaa);


//方法二
var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};

3) 算法时间复杂度分析

• 最佳情况：T(n) = O(nlogn)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(nlogn)
  参考:

• 数据结构与算法
• 常用排序算法之JavaScript实现