Javascript实现常用数据结构与算法（二）
1.排序算法
常见的排序算法可以分为两类，基本排序算法和高级排序算法。本文前三个是基本排序算法，后三个是高级排序算法。高级排序算法适用于数据集较大的情况。其他的算法诸如基数排序、堆排序等随后补充。
需要仔细掌握每种算法的思想，并且能够手撕代码，在不同情况下熟练运用。
1.1 冒泡排序
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { //相邻元素两两对比
var temp = arr[j+1]; //元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
1.2 选择排序
function selectionSort(arr) {
var len = arr.length;
var min, temp;
for (var i = 0; i < len - 1; i++) {
min = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[min]) { //寻找最小的数
min = j; //将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
return arr;
}
1.3 插入排序
function insertionSort(array) {
for (var i = 1; i < array.length; i++) {
var temp = array[i];
var j = i - 1;
while ( j>=0 && array[j] > temp) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
return array;
}
1.4 希尔排序
function shellSort(arr) {
for(let gap = Math.floor(arr.length/6); gap > 0; gap = Math.floor(gap/6)) {
// 内层循环与插入排序的写法基本一致，只是每次移动的步长变为 gap
for(let i = gap; i < arr.length; i++) {
let j = i;
let temp = arr[j];
for(; j> 0; j -= gap) {
if(temp >= arr[j-gap]) {
break;
}
arr[j] = arr[j-gap];
}
arr[j] = temp;
}
}
return arr;
}
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) { //动态定义间隔序列
gap = gap*3+1;
}
for (gap; gap> 0; gap = Math.floor(gap/3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j > 0 && arr[j]> temp; j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
1.5 归并排序
自顶向下的归并排序（使用了递归）：
function mergeSort(arr) {
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length>0 && right.length>0) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
自底向上的归并排序：
function mergeSort1(arr){
if(arr.length < 2){
return;
}
//设置子序列的大小
var step=1;
var left,right;
while(step < arr.length){
left = 0;
right = step;
while(right+step <= arr.length){
mergeArrays(arr,left,left+step,right,right+step);
left = right + step;
right = left + step;
}
if(right < arr.length){
mergeArrays(arr,left,left+step,right,arr.length);
}
step *= 2;
}
}
//对左右序列进行排序
function mergeArrays(arr,startLeft,stopLeft,startRight,stopRight){
// 建立一个左、右数组
var rightArr = new Array(stopRight - startRight + 1);
var leftArr = new Array(stopLeft - startLeft + 1);
//给右数组赋值
k = startRight;
for(var i=0;i<(rightArr.length-1);++i){
rightArr[i] = arr[k];
++k;
}
//给左数组赋值
k = startLeft;
for(var i=0;i<(leftArr.length-1);++i){
leftArr[i] = arr[k];
++k;
}
//设置哨兵值，当左子列或右子列读取到最后一位时，即Infinity，可以让另一个剩下的列中的值直接插入到数组中
rightArr[rightArr.length-1] = Infinity;
leftArr[leftArr.length-1] = Infinity;
var m = 0;
var n = 0;
//比较左子列和右子列第一个值的大小，小的先填入数组，接着再进行比较
for(var k = startLeft; k < stopRight; ++k){
if(leftArr[m] <= rightArr[n]){
arr[k] = leftArr[m];
m++;
}
else{
arr[k] = rightArr[n];
n++;
}
}
}
// 测试数据
var nums = [6,10,1,9,4,8,2,7,3,5];
mergeSort1(nums);
print(nums);
1.6 快速排序
function quickSort(arr, left, right) {
var len = arr.length,
partitionIndex,
left = typeof left != 'number' ? 0 : left,
right = typeof right != 'number' ? len - 1 : right;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex-1);
quickSort(arr, partitionIndex+1, right);
}
return arr;
}
function partition(arr, left ,right) { //分区操作
var pivot = left, //设定基准值（pivot）
index = pivot + 1;
for (var i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index-1;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
简化版实现快速排序：
(1) 选择一个基准元素， 将列表分隔成两个子序列；
(2) 对列表重新排序， 将所有小于基准值的元素放在基准值的前面， 所有大于基准值的元
素放在基准值的后面；
(3) 分别对较小元素的子序列和较大元素的子序列重复步骤 1 和 2。
function quickSort(list){
if (list.length == 0) {
return [];
}
var lesser = [];
var greater = [];
var middle = list[0];
for (var i = 1; i < list.length; i++) {
if (list[i] < middle) {
lesser.push(list[i]);
} else {
greater.push(list[i]);
}
}
return quickSort(lesser).concat(middle, quickSort(greater));
}
var num = [5,2,5,9,2,45,78,14,16];
print(quickSort(num));
各类排序算法的对比图：
2 链表
2.1 定义链表
JavaScript 中数组的主要问题是， 它们被实现成了对象， 与其他语言（ 比如 C++ 和 Java）的数组相比， 效率很低。可以考虑使用链表来替代它。 除了对数据的随机访问， 链表几乎可以用在任何可以使用一维数组的情况中。
js中没有封装好的链表类，需要我们去实现链表对象。
链表的尾元素指向一个 null 节点。链表最前面有一个特殊节点， 叫做头节点（head）。
首先，我们需要创建一个Node类，用来处理节点数据的保存和节点移动。再定义链表类LList，实现相应的查找、插入、删除和遍历元素的方法。
//Node类，包含两个属性： element 用来保存节点上的数据， next 用来保存指向下一个节点的链接。
function Node(element) {
this.element = element;
this.next = null;
}
//head 节点的 next 属性被初始化为 null，当有新元素插入时，next 会指向新的元素
function LList() {
this.head = new Node("head");
this.find = find;
this.insert = insert;
this.findPrevious = findPrevious;
this.remove = remove;
this.display = display;
}
//查询节点
function find(item) {
var currNode = this.head;
while (currNode.element != item) {
currNode = currNode.next;
}
return currNode;
}
//插入节点，在item的后面插入元素
function insert(newElement, item) {
var newNode = new Node(newElement);
var current = this.find(item);
newNode.next = current.next;
current.next = newNode;
}
//显示链表中所有元素
function display() {
var currNode = this.head;
while (!(currNode.next == null)) {
print(currNode.next.element);
currNode = currNode.next;
}
}
/* 从链表中删除节点时， 需要先找到待删除节点前面的节点。 找到这个节点后， 修改它的next 属性， 使其不再指向待删除节点，
而是指向待删除节点的下一个节点。 我们可以定义一个方法 findPrevious()， 来做这件事.
该方法遍历链表中的元素， 检查每一个节点的下一个节点中是否存储着待删除数据。 如果找到， 返回该节点（ 即“ 前一个” 节点），
这样就可以修改它的 next 属性了。 */
function findPrevious(item) {
var currNode = this.head;
while (!(currNode.next == null) && (currNode.next.element != item)) {
currNode = currNode.next;
}
return currNode;
}
//删除元素的方法
function remove(item) {
var prevNode = this.findPrevious(item);
if (!(prevNode.next == null)) {
prevNode.next = prevNode.next.next;
}
}
2.2 双向链表
通过给 Node 对象增加一个属性previous， 该属性存储指向前驱节点的链接，可以实现从后往前遍历。 此时向链表插入一个节点需要指出该节点正确的前驱和后继。
注意：
- 双向链表的 insert() 方法和单向链表的类似， 但是需要设置新节点的 previous 属性， 使
其指向该节点的前驱。 - 双向链表的 remove() 方法比单向链表的效率更高， 因为不需要再查找前驱节点了。 首先需
要在链表中找出存储待删除数据的节点， 然后设置该节点前驱的 next 属性， 使其指向待删
除节点的后继； 设置该节点后继的 previous 属性， 使其指向待删除节点的前驱。
/* 双向链表类 */
function Node(element) {
this.element = element;
this.next = null;
this.previous = null;
}
function LList() {
this.head = new Node("head");
this.find = find;
this.insert = insert;
this.display = display;
this.remove = remove;
this.findLast = findLast;
this.dispReverse = dispReverse;
}
//反序显示双向链表中的元素
function dispReverse() {
var currNode = this.head;
currNode = this.findLast(); //定位到最后的元素
while (!(currNode.previous == null)) {
print(currNode.element);
currNode = currNode.previous;
}
}
//找出了链表中的最后一个节点
function findLast() {
var currNode = this.head;
while (!(currNode.next == null)) {
currNode = currNode.next;
}
return currNode;
}
//移除元素
function remove(item) {
var currNode = this.find(item);
if (!(currNode.next == null)) {
currNode.previous.next = currNode.next;
currNode.next.previous = currNode.previous;
currNode.next = null;
currNode.previous = null;
}
}
//显示所有元素
function display() {
var currNode = this.head;
while (!(currNode.next == null)) {
print(currNode.next.element);
currNode = currNode.next;
}
}
function find(item) {
var currNode = this.head;
while (currNode.element != item) {
currNode = currNode.next;
}
return currNode;
}
function insert(newElement, item) {
var newNode = new Node(newElement);
var current = this.find(item);
newNode.next = current.next;
newNode.previous = current;
current.next = newNode;
}