数据结构与算法

缘由:复习总结一下常用数据结构与算法,长期更新

一、数据结构

1-1、基础知识

物理存储结构:线性存储,链式存储

逻辑结构:线性表,二叉树,图

时间复杂度计算,空间复杂度计算

1-2、队列,栈,优先队列(堆)

1-2-1、List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
function List() {
this.listSize = 0;
this.pos = 0;
this.dataStore = [];
this.clearList = clearList;
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.nextElement = nextElement;
// this.lengthList = List;
// this.currPos = currPos;
// this.moveTo = moveTo;
// this.getElement = getElement;
}
function append(element) {
this.dataStore[this.listSize++] = element;
}
function find(element) {
for(var i = 0; i < this.dataStore.length; ++i) {
if (this.dataStore[i] == element) {
return i;
}
}
return -1;
}
function remove(element) {
var foundAt = this.find(element);
if (foundAt > -1) {
this.dataStore.splice(foundAt,1);
--this.listSize;
return true;
}
return false;
}
function lengthlist() {
return this.listSize;
}
function toString() {
return this.dataStore;
}
function insert(element,after) {
var insertPos = this.find(after);
if (insertPos > -1) {
this.dataStore.splice(insertPos + 1,0,element);
--this.listSize;
return true;
}
return false;
}
function clearList() {
delete this.dataStore;
this.dataStore = [];
this.pos = this.listSize = 0;
}
var names = new List();
names.append('jacob');
names.append('raistlin');
names.append('jetty');
names.append('bruce');
// print(names.toString());
console.log(names.toString());
names.remove('raistlin');
// print(names.toString());
console.log(names.toString());
names.insert('raist','bruce');
console.log(names.toString());
names.clearList();
console.log(names.toString());

1-2-2、单向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
function Node(element) {
this.element = element;
this.next = null;
}
function LList() {
this.head = new Node('head');
this.find = find;
this.findPre = findPre;
this.insert = insert;
this.remove = remove;
this.display = display;
}
function find(item) {
var currentNode = this.head;
while (currentNode.element != item) {
currentNode = currentNode.next;
}
return currentNode;
}
function insert(newElement,item) {
var newNode = new Node(newElement);
var currentNode = this.find(item);
newNode.next = currentNode.next;
currentNode.next = newNode;
}
function display() {
var currentNode = this.head;
while (!(currentNode.next == null)) {
console.log(currentNode.element);
currentNode = currentNode.next;
}
}
function findPre(item) {
var currentNode = this.head;
while (currentNode.next.element != item) {
currentNode = currentNode.next;
}
return currentNode;
}
function remove(item) {
var currentNode = this.head;
while (currentNode.element != item) {
currentNode = currentNode.next;
}
if (currentNode.element == item) {
this.findPre(item).next = currentNode.next;
currentNode.next = null;
return;
}
}
var names = new LList();
names.insert('jacob','head');
names.insert('jetty','jacob');
names.insert('raistlin','jetty');
names.insert('bruce','raistlin');
names.insert('raistlin','bruce');
names.remove('raistlin');
names.display();

1-2-3、双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
function Node (element) {
this.element = element;
this.next = null;
this.previous = null;
}
function LList (item) {
this.head = new Node('head');
this.disReverse = disReverse;
this.display = display;
this.findLast = findLast;
this.find = find;
this.insert = insert;
this.remove = remove;
}
function disReverse () {
var currentNode = this.head;
currentNode = this.findLast();
while (!(currentNode.previous == null)) {
console.log(currentNode);
currentNode = currentNode.previous;
}
}
function findLast () {
var currentNode = this.head;
while (!(currentNode.next==null)) {
currentNode = currentNode.next;
}
return currentNode;
}
function find (item) {
var currentNode = this.head;
while (!(currentNode.element == item)) {
currentNode = currentNode.next;
}
return currentNode;
}
function insert (newElement,item) {
var currentNode = this.find(item);
newNode = new Node(newElement);
if (currentNode.next == null) {
currentNode.next = newNode;
newNode.previous = currentNode;
newNode.next = null;
} else {
newNode.next = currentNode.next;
currentNode.next.previous = newNode;
currentNode.next = newNode;
newNode.previous = currentNode;
}
}
function remove (item) {
var currentNode = this.find(item);
var previousNode = currentNode.previous;
var nextNode = currentNode.next;
nextNode.previous = previousNode;
previousNode.next = nextNode;
}
function display () {
var currentNode = this.head;
while (currentNode.next != null) {
console.log(currentNode.element);
currentNode = currentNode.next;
}
}
var names = new LList()
names.insert('jacob','head');
names.insert('bruce','jacob');
names.insert('jetty','bruce');
names.insert('raistlin','jacob');
names.remove('jacob');
names.display();

1-2-3、queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
function Queue() {
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
}
function enqueue(element) {
this.dataStore.push(element);
}
function dequeue () {
return this.dataStore.shift();
}
function front () {
return this.dataStore[0];
}
function back () {
return this.dataStore[this.dataStore.length - 1];
}
function toString() {
var restr = '';
for (var i = 0; i < this.dataStore.length; i++) {
restr += this.dataStore[i] + '\n';
}
return restr;
}
function empty () {
if (this.dataStore.length == 0) {
return true;
} else {
return false;
}
}
var queue = new Queue();
queue.enqueue('jacob');
queue.enqueue('bruce');
queue.enqueue('jetty');
console.log(queue.front());
console.log(queue.back());
console.log(queue.toString());
queue.dequeue();
console.log(queue.toString());

1-2-4、stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function Stack(){
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.length = length;
this.clear = clear;
}
function push(element) {
this.dataStore[this.top++] = element;
}
function pop() {
return this.dataStore[--this.top];
}
function peek() {
return this.dataStore[this.top - 1];
}
function length() {
return this.top;
}
function clear() {
this.top = 0;
}
var instanceStack = new Stack();
instanceStack.push('jacob');
instanceStack.push('jetty');
instanceStack.push('bruce');
instanceStack.push('raistlin');
console.log(instanceStack.peek());
instanceStack.pop();
console.log(instanceStack.peek());
instanceStack.pop();
console.log(instanceStack.peek());

1-3、二叉树

1-3-1、背景知识

树是一种比较重要的数据结构,尤其是二叉树。二叉树是一种特殊的树,在二叉树中每个节点最多有两个子节点,一般称为左子节点和右子节点(或左孩子和右孩子),并且二叉树的子树有左右之分,其次序不能任意颠倒。二叉树是递归定义的,因此,与二叉树有关的题目基本都可以用递归思想解决。

1-3-2、基本概念

二叉树概念:每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点。二叉树中每一个节点都是一个对象,每一个数据节点都有三个指针,分别是指向父母、左孩子和右孩子的指针。每一个节点都是通过指针相互连接的。相连指针的关系都是父子关系。

满二叉树:在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。

完全二叉树:完全二叉树是指最后一层左边是满的,右边可能满也可能不满,然后其余层都是满的。一个深度为k,节点个数为 2^k - 1 的二叉树为满二叉树(完全二叉树)。满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树。

二叉树的遍历:前序遍历,中序遍历,后序遍历

1
2
3
(1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树。简记根-左-右。
(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树。简记左-根-右。
(3)后序遍历(LRD),首先遍历左子树,然后遍历右子树,最后访问根结点。简记左-右-根。

【规律:左右不变,根移位】

实现的代码主要使用递归:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void PreOrderTraverse(BinaryTreeNode * pRoot)
{
if(pRoot == NULL)
return;
Visit(pRoot); // 访问根节点
PreOrderTraverse(pRoot->m_pLeft); // 前序遍历左子树
PreOrderTraverse(pRoot->m_pRight); // 前序遍历右子树
}
void InOrderTraverse(BinaryTreeNode * pRoot)
{
if(pRoot == NULL)
return;
InOrderTraverse(pRoot->m_pLeft); // 中序遍历左子树
Visit(pRoot); // 访问根节点
InOrderTraverse(pRoot->m_pRight); // 中序遍历右子树
}
void PostOrderTraverse(BinaryTreeNode * pRoot)
{
if(pRoot == NULL)
return;
PostOrderTraverse(pRoot->m_pLeft); // 后序遍历左子树
PostOrderTraverse(pRoot->m_pRight); // 后序遍历右子树
Visit(pRoot); // 访问根节点
}

1-3-3、参考资料

轻松搞定二叉树面试题

js算法与数据结构

学习JavaScript数据结构与算法:栈与队列

1-4、查找二叉树(BST),二叉堆,图

1-4-1、查找二叉树

二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

  • 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  • 任意节点的左、右子树也分别为二叉查找树;
  • 没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合、multiset、关联数组等。

二叉查找树的查找过程和次优二叉树类似,通常采取二叉链表作为二叉查找树的存储结构。中序遍历二叉查找树可得到一个关键字的有序序列,一个无序序列可以通过构造一棵二叉查找树变成一个有序序列,构造树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点,在进行插入操作时,不必移动其它结点,只需改动某个结点的指针,由空变为非空即可。搜索、插入、删除的复杂度等于树高,期望O(log n)最坏O(n)(数列有序,树退化成线性表)。

虽然二叉查找树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉查找树可以使树高为O(log n),如SBT,AVL树,红黑树等。故不失为一种好的动态查找方法。

1-4-2、查找二叉树的js实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
function Node(data,left,right) {
this.data = data;
this.left = left;
this.right = right;
this.show = show;
}
function show() {
return this.data;
}
function BST() {
this.root = null;
this.insert = insert;
this.inOrder = inOrder;
}
function insert(data) {
var n = new Node(data,null,null);
if (this.root == null) {
this.root = n;
} else {
var current = this.root;
while(1) {
if (data < current.data) {
if (current.left == null) {
current.left = n;
break;
}
current = current.left;
} else {
if (current.right == null) {
current.right = n;
break;
}
current = current.right
}
}
}
}
function inOrder(node) {
if (node != null) {
inOrder(node.left);
console.log(node.show());
inOrder(node.right);
}
}
var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(110);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
inOrder(nums.root);

二、排序算法

2-1、冒泡排序(bubble sort)

2-1-1、bubble概述【o(n2)】

冒泡排序的算法时间复杂度为n^2,是最基础的排序算法,基本思想:对于一个长度为N的数组,从左往右,依次找到数组中最大项,第二大项….,最小项,依次排序到数组最右侧,第一次比较的次数为N-1,找到最大项后,将其移至最右侧,第二次找第二大项,比较次数为N-2,找到第二大项后,将其移至倒数第二位,依次重复上述操作。

2-1-2、bubble排序实现(js)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// bubble排序
// 可视化演示过程可参考:https://visualgo.net/sorting
// 理解:时间复杂度为O(n2);进行2个for循环,原则是每一个子循环进行后,最大数值被放置最右侧
var array = [12,23,45,2,45,3,464,29];
function bubbleSort() {
var numElements = this.array;
for (var outer = numElements.length; outer >=2; --outer) {
for (var inner = 0; inner <= outer - 1; ++inner) {
if (this.array[inner] > this.array[inner + 1]) {
var b = this.array[inner];
this.array[inner] = this.array[inner + 1];
this.array[inner + 1] = b;
}
}
}
console.log(this.array);
}
bubbleSort();

2-2、选择排序(selected sort)

2-2-1、selected sort概述【O(n2)】

选择排序和冒泡排序基本思想是一致的,都是找出数组中,最大元素,第二大元素,第三大元素….最小元素,依次放置在数组的最右侧,选择排序比冒泡排序算法好在,其元素交换的次数没有那么多。核心体现在[哨兵]的使用上。

2-2-2、selected sort算法实现(js)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//理解:选择排序的时间复杂度还是O(n2),和冒泡排序不同在于,减少数据交换次数,以下实现为找到最小元素,然后找到第二小元素,直接放置合适位置
var swap = function(array, firstIndex, secondIndex){
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
};
var array = [2,1];
swap(array, 0, 1)
console.log('swap should return [1,2] -->', array);
var selectionSort = function(array){
for(var i = 0; i < array.length; i++){
//set min to the current iteration of i
var min = i;
for(var j = i+1; j < array.length; j++){
if(array[j] < array[min]){
min = j;
}
}
swap(array, i, min);
}
return array;
};
var array = [12,23,45,2,45,3,464,29]
console.log('selectionSort should return [2, 3, 12, 23, 29, 45, 45, 464]-->',selectionSort(array));

2-3、插入排序(insert sort)

2-3-1、insert sort概述【O(n2)】

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

2-3-2、insert sort算法实现(js)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//理解:插入算法简而言之,将一个新元素插入不断增长的有序数列中,插入完成之后,有序数列增加一个元素。
function insertionSort(inputArray){
var holePosition
var valueToInsert
for(var i = 1; i< inputArray.length; i++){
/* select value to be inserted */
valueToInsert = inputArray[i]
holePosition = i
/* Notice I used the while as opposed to the for*/
while ( holePosition > 0 && inputArray[holePosition-1] > valueToInsert){
inputArray[holePosition] = inputArray[holePosition-1]
holePosition = holePosition -1
}
/* insert the number at hole position */
inputArray[holePosition] = valueToInsert
}
return inputArray;
}
var result =insertionSort([12,23,45,2,45,3,464,29]);
console.log(result);

2-4、希尔排序(shell sort)

2-4-1、shell sort概览【O(n log2 n)】

希尔排序需要着重注意一下,这是排序算法的一个里程碑,在希尔算法之前,人们都认为排序的算法复杂度没有办法突破,O(n2),希尔算法之后,人们相续发明诸多可以突破时间复杂度O(n2)的算法,其实希尔算法是插入算法的一种变形。具体的解释摘抄自维基百科:

1
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(此时插入排序较快)。

上述的解释不够直观,下面用一个例子描述:

例如,假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:

1
2
3
4
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序:

1
2
3
4
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了,然后再以3为步长进行排序:

1
2
3
4
5
6
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为:

1
2
3
4
5
6
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以1步长进行排序(此时就是简单的插入排序了)

2-4-2、shell sort算法实现(js)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//理解:shell sort 算法是对插入算法的一个改进,从下面的代码中也可以看出来,for循环的部分和插入算法实现是一样的,shell sort算法实现较为容易,但是理解并计算其时间复杂度还是比较困难的。
function shellSort(arr) {
var increment = arr.length / 2;
while (increment > 0) {
for (i = increment; i < arr.length; i++) {
var j = i;
var temp = arr[i];
while (j >= increment && arr[j-increment] > temp) {
arr[j] = arr[j-increment];
j = j - increment;
}
arr[j] = temp;
}
if (increment == 2) {
increment = 1;
} else {
increment = parseInt(increment*5 / 11);
}
}
return arr;
}
console.log(shellSort([12,23,45,2,45,3,464,29]));

2-5、归并排序(merge sort)

2-5-1、merge sort概览【O(n log n)】

归并排序,看着英文名字是不是很熟悉,是的,merge,就是git操作中合并分支的语法,所以你应该能明白这个算法的大概了,而且这个算法是大神,冯洛伊曼给出的,官方给的说明太过简洁,反而不好理解,下面是啰嗦版本。

首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。

可以看出合并有序数列的效率是比较高的,可以达到O(n)。

解决了上面的合并有序数列问题,再来看归并排序,其的基本思路就是将数组分成二组A,B,如果这二组组内的数据都是有序的,那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了?

可以将A,B组各自再分成二组。依次类推,当分出来的小组只有一个数据时,可以认为这个小组组内已经达到了有序,然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列,再合并数列就完成了归并排序。

归并排序的效率是比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是一个合并有序数列的过程,时间复杂度可以记为O(N),故一共为O(NlogN)。因为归并排序每次都是在相邻的数据中进行操作,所以归并排序在O(NlogN)的几种排序方法(快速排序,归并排序,希尔排序,堆排序)也是效率比较高的。

归并排序参考的网页

我的理解:2个有序的数列【1,3,6,12】、【2,4,5,10】
现在将2个数列合并为一个数列,
第一步,比较a[0]和b[0],所以c[0]=a[0]=1 ,c[1]=b[0]=2
第二步,比较a[1]和b[1],所以c[2]=a[1]=3 ,c[3]=b[1]=4
第三步,比较a[2]和b[2],所以c[4]=b[2]=5,c[5]=a[2]=6
第四步,比较a[3]和b[3],所以c[6]=b[3]=10,c[7]=a[3]=12
最后合并的数组为var c = [1,2,3,4,5,6,10,12]

所以合并2个有序数组是很容易,但是怎样才能保证合并的是有序数组呢,最小的有序数组是【单个元素】,所以可以不断递归直至最后一个元素,下面看算法实现吧。

2-5-2、merge sort算法实现(js)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//理解:归并算法其实是递归算法的一个应用.
var a = [34, 203, 3, 746, 200, 984, 198, 764, 9];
function mergeSort(arr)
{
if (arr.length < 2)
return arr;
var middle = parseInt(arr.length / 2);
var left = arr.slice(0, middle);
var right = arr.slice(middle, arr.length);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
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;
}
console.log(mergeSort(a));

It’s interesting to see what happens in the Firebug’s console:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[34, 203, 3, 746] [200, 984, 198, 764, 9]
[34, 203] [3, 746]
[34] [203]
[3] [746]
[200, 984] [198, 764, 9]
[200] [984]
[198] [764, 9]
[764] [9]
[3, 9, 34, 198, 200, 203, 746, 764, 984]

2-6、堆排序(heap sort)

2-6-1、heap sort概览【O(nlogn)】

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

2-6-2、heap sort算法实现[js]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//思想:
Array.prototype.heap_sort = function() {
var arr = this.slice(0);
function swap(i, j) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
function max_heapify(start, end) {
//建立父節點指標和子節點指標
var dad = start;
var son = dad * 2 + 1;
if (son >= end)//若子節點指標超過範圍直接跳出函數
return;
if (son + 1 < end && arr[son] < arr[son + 1])//先比較兩個子節點大小,選擇最大的
son++;
if (arr[dad] <= arr[son]) {//如果父節點小於子節點時,交換父子內容再繼續子節點和孫節點比較
swap(dad, son);
max_heapify(son, end);
}
}
var len = arr.length;
//初始化,i從最後一個父節點開始調整
for (var i = Math.floor(len / 2) - 1; i >= 0; i--)
max_heapify(i, len);
//先將第一個元素和已排好元素前一位做交換,再從新調整,直到排序完畢
for (var i = len - 1; i > 0; i--) {
swap(0, i);
max_heapify(0, i);
}
return arr;
};
var a = [3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6];
console.log(a.heap_sort());

2-7、快速排序(quick sort)

2-7-1、quick sort算法概览[O(nlogn)]

快速排序算法是以上7中算法中最快的,主要的想法是,随机在数列中选择一个作为参考,然后大于这个元素的发在右侧,小于这个元素的放在左侧,然后在左侧数列中在选择一个元素,重复上述操作,右侧也这样操作,直至最后数列元素只有一个。这样讲述可能不容易理解,可以参考维基百科中的动态图

2-7-2、quick sort算法实现[js]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//思想:随机选取数列中一个元素,然后基于该元素,分左右2组数列
function swap(arr, i, j){
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function partition(arr, pivot, left, right){
var pivotValue = arr[pivot],
partitionIndex = left;
for(var i = left; i < right; i++){
if(arr[i] < pivotValue){
swap(arr, i, partitionIndex);
partitionIndex++;
}
}
swap(arr, right, partitionIndex);
return partitionIndex;
}
function quickSort(arr, left, right){
var len = arr.length,
pivot,
partitionIndex;
if(left < right){
pivot = right;
partitionIndex = partition(arr, pivot, left, right);
//sort left and right
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}

2-8、总结

国外友人写的不过的排序总结

三、查找算法

3-1、二分查找

四、参考

《数据结构与算法Javascript描述》

《数据结构与算法C语言描述》

《大话数据结构》

算法与数据结构资源推荐

可视化的算法和数据结构网站

javascript数据结构实现——我的github

浙大数据结构与算法-视频

坚持原创技术分享,您的支持将鼓励我继续创作!