算法学习
yunyu950908 / algo Goto Github PK
View Code? Open in Web Editor NEW算法学习
算法学习
reference: https://visualgo.net/en/sorting
由于本宝宝是第一次学习,一边学习一边记录,难免会有错误,还请大佬指出,不胜感激~
插入排序需要两个嵌套的循环。
�由上述说明,大致上一共有 5 个过程。
Tips: 插入排序每次只移动一个元素的位置, 不会改变同值元素之间的排序, 因此它是一种稳定排序。
先贴上可视化学习资料:https://visualgo.net/en/sorting
以及右下角的伪代码
mark first element as sorted
for each unsorted element X
'extract' the element X
for j = lastSortedIndex down to 0
if current element j > X
move sorted element to the right by 1
break loop and insert X here
// swap 函数交换元素
function swap(a, b, array) {
const temp = array[a];
array[a] = array[b];
array[b] = temp;
return null;
}
// insertionSort
function insertionSort(array) {
let lastSortedIndex = 0; // 最后一个已排序元素下标
for (let i = 1; i < array.length; i++) { // 外循环遍历未排序元素
const unsortedX = array[i]; // 存档当前外循环游标指定的未排序元素
for (let j = lastSortedIndex; j >= 0; j--) { // 内循环遍历已排序元素
if (array[j] > unsortedX) { // 如果已排序元素大于未排序元素,则交换位置
swap(j, j + 1, array);
array[j] = unsortedX;
} else {
break; // 否则代表已被交换到相对正确的位置,退出本轮内循环
}
}
lastSortedIndex++; // 最后一个已排序元素下标 + 1
}
return array;
}
emmmm... 看起来是没啥问题哦...
插入排序的复杂度分析
所以结果应该是
大概就酱啦~ 代码应该写的很清楚了,还有不明白的或者是写错了的,欢迎交流纠正~
源码和测试在这里 https://github.com/yunyu950908/algorithms/blob/master/test/sort_insertion.js
reference: https://visualgo.net/en/sorting
由于本宝宝是第一次学习,一边学习一边记录,难免会有错误,还请大佬指出,不胜感激~
冒泡排序需要两个嵌套的循环。
�由上述说明,大致上一共有 5 个过程。
Tips: 由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法.
先贴上可视化学习资料:https://visualgo.net/en/sorting
以及右下角的伪代码
do
swapped = false
for i = 1 to indexOfLastUnsortedElement-1
if leftElement > rightElement
swap(leftElement, rightElement)
swapped = true
while swapped
// swap 函数交换元素
function swap(a, b, array) {
const temp = array[a];
array[a] = array[b];
array[b] = temp;
return null;
}
// bubbleSort
function bubbleSrot(array) {
// 为方便比较,拷贝一份副本
const resultArr = [].concat(array);
// 判断是否交换的 flag
let swapped = false;
// 最后一个未排序元素的下标
let indexOfLastUnsortedElement = resultArr.length - 1;
do {
swapped = false;
// i 的范围 [0, indexOfLastUnsortedElement - 1]
for (let i = 0; i < indexOfLastUnsortedElement; i += 1) {
// 如果当前项比后一项大,交换位置
if (resultArr[i] > resultArr[i + 1]) {
swap(i, i + 1, resultArr);
swapped = true;
}
}
// 内循环结束后最后一项为数组最大的元素,之后的内循环元素无需与之比较
indexOfLastUnsortedElement -= 1;
} while (swapped);
return resultArr;
}
测试一下:
// 生成一个包含 10 个 [0, 99] 随机数的数组
function genArr() {
return Array.from(new Array(10), () => Math.random() * 100 >>> 0);
}
const newArr = genArr();
const sortedArr = bubbleSrot(newArr);
console.log('原数组:', newArr); //原数组: [ 62, 55, 92, 25, 68, 61, 3, 19, 79, 80 ]
console.log('bubbleSrot: ', sortedArr); // bubbleSrot: [ 3, 19, 25, 55, 61, 62, 68, 79, 80, 92 ]
未完待续...
2018-05-14 续
emmm,第一版看起来是没什么问题,不过我还是更喜欢写成 for
循环,毕竟平时撸项目代码基本都是直接用原生封装的 API,不然就是 for... 233333,说干就干,改写一下下。。。
do...while + for...
改成 for... + for...
function bubbleSort2(array) {
// 同样拷贝一份副本,为了后续对比方便
const resultArr = [].concat(array);
// 外循环,最多需要 n-1 次排完 n 个元素
for (let i = 0; i < resultArr.length - 1; i += 1) {
let isSwap = false;
// 内循环,最多比较 n - 1 -i 次能得到一个最大的元素
for (let j = 0; j < resultArr.length - 1 - i; j += 1) {
if (resultArr[j] > resultArr[j + 1]) {
swap(j, j + 1, resultArr);
isSwap = true;
}
}
if (!isSwap) break;
}
return resultArr;
}
测试一下下:
const newArr = genArr();
const sortedArr2 = bubbleSrot2(newArr);
console.log('原数组:', newArr); //原数组: [ 66, 5, 33, 35, 96, 83, 44, 6, 95, 49 ]
console.log('bubbleSrot2: ', sortedArr2); // bubbleSrot2: [ 5, 6, 33, 35, 44, 49, 66, 83, 95, 96 ]
冒泡排序是内外两重循环的比较排序,不同的遍历方向可以有 外正内正
外正内负
外负内负
外负内正
这四种写法,具体代码不贴了,一起学习的小伙伴阔以将自己的代码贴出来,一起讨论讨论,虽然对于科班童鞋来说可能都是基础中的基础,然而跟我野路子出生基础奇差的小伙伴阔以一起交流讨论哈~
function bubbleSort3(array) {
const resultArr = [].concat(array); // 没错,又是没用的拷贝副本
let len = resultArr.length;
for (let i = 0; i < resultArr.length >> 1;) {
let isSwap = false;
// 最小的冒泡到最前面
for (let j = len - 1; j > i; j -= 1) {
if (resultArr[j] < resultArr[j - 1]) {
swap(j, j - 1, resultArr);
isSwap = true;
}
}
if (!isSwap) break;
isSwap = false;
// 此时第 i 项已经排好,下一次正向冒泡游标向后移动一位
i += 1;
// 最大的冒泡到最后面
for (let k = i; k < len - 1; k += 1) {
if (resultArr[k] > resultArr[k + 1]) {
swap(k, k + 1, resultArr);
isSwap = true;
}
}
if (!isSwap) break;
// 此时第 len - 1 项已经排好,下一次负向冒泡起始游标向前移动一位
len -= 1;
}
return resultArr;
}
测试一下:
const newArr = genArr();
const sortedArr3 = bubbleSrot3(newArr);
console.log('原数组:', newArr); // 原数组: [ 30, 65, 27, 99, 50, 54, 67, 94, 19, 93 ]
console.log('bubbleSrot3: ', sortedArr3); // bubbleSrot3:[ 19, 27, 30, 50, 54, 65, 67, 93, 94, 99 ]
emmmm... 看起来是没啥问题哦...
冒泡排序的复杂度分析相对简单,不过也不太清楚这么想对不对(只看过大话数据结构的理解)
所以结果应该是
大概就酱啦~ 代码应该写的很清楚了,还有不明白的或者是写错了的,欢迎交流纠正~
源码和测试在这里 https://github.com/yunyu950908/algorithms/blob/master/test/sort_bubble.js
PS: 个人笔记,写的比较乱。有错误还请指出。
队列是一种列表,不同的是队列只能在队尾插入元素,在队首删除元素。
为了偷懒,继续使用之前的双向链表。
https://github.com/yunyu950908/algorithms/blob/master/data_structure/linked.js
当然,也可以使用数组作为队列的底层数据结构。
/**
* Node 定义一个节点
* @param element
* @param prev
* @param next
* */
class Node {
constructor(element, prev = null, next = null) {
this.element = element;
this.prev = prev;
this.next = next;
}
}
/**
* Linked 双向链表
*
* 属性
* head 表头
* tail 表尾
*
* 方法
* push 入队操作
* shift 出队操作
* */
class Linked {
constructor({ head = null, tail = null, size = 0 } = {}) {
this.head = head || new Node('Head');
this.tail = tail || this.head;
this.size = size;
}
push(element) {
const newNode = new Node(element);
if (this.tail === this.head) { // 空表
this.tail = newNode;
this.tail.prev = this.head;
this.head.next = this.tail;
} else { // 非空表
const tempTail = this.tail;
this.tail = newNode;
this.tail.prev = tempTail;
tempTail.next = this.tail;
}
this.size++;
return this.size;
}
shift() {
const targetNode = this.head.next;
if (!targetNode) return null;
if (targetNode === this.tail) {
this.tail = this.head;
} else {
this.head.next.prev = this.head;
}
this.head.next = targetNode.next;
targetNode.next = null;
targetNode.prev = null;
this.size--;
return targetNode;
}
}
/**
* Queue
*
* 属性
* head 队头
* tail 队尾
* size
*
* 方法
* push
* shift
* */
class Queue {
constructor() {
return new Linked();
}
}
基数排序:
function radixSort(array) {
const queues = Array.from(new Array(10), () => new Queue());
const maxLen = Math.max.apply(null, array).toString().length;
for (let i = 0; i < maxLen; i++) {
distribute(array, queues, i);
}
return array;
}
function distribute(array, queues, digit) {
let count = 0;
for (let i = 0; i < array.length; i++) {
const item = array[i];
const idx = Math.floor((item / Math.pow(10, digit)) % 10);
queues[idx].push(item);
}
for (let i = 0; i < queues.length; i++) {
const queue = queues[i];
while (queue.length > 0) {
array[count++] = queue.shift();
}
}
}
当然队列还有很多其他应用,比如排队挂号,特权插队,限制任务数量等等都可以用队列实现。
记住队列的特征:
reference: https://visualgo.net/en/sorting
由于本宝宝是第一次学习,一边学习一边记录,难免会有错误,还请大佬指出,不胜感激~
归并排序和前面的几种排序略有不同,前面的三个排序算法的时间复杂度度为O(n²),在处理大量数据的时候会有明显的性能下降,但归并排序性能不错,复杂度只有 O(nlogn)(PS: 本质上是空间换时间的一种做法)。
归并排序运用了分治**,将原始数组切分成较小的数组,直到每个小数组只有一个位置,接着将小数组归并成较大的数组,直到最后只有一个排序完毕的大数组。
这货步骤不太好用文字描述,直接看动画演示吧:https://visualgo.net/en/sorting
Tips: 归并排序严格按照从左往右(或从右往左)的顺序去合并子数组, 它并不会改变相同元素之间的相对顺序, 因此它也是一种稳定的排序算法.
function mergeSort(array) {
const length = array.length;
if (length === 1) return array; // 只剩一项,直接返回
const mid = length >> 1; // 二分
const left = array.slice(0, mid); // 前半段数组
const right = array.slice(mid); // 后半段数组
return merge(mergeSort(left), mergeSort(right)); // 递归调用
}
function merge(leftArray, rightArray) {
const result = [];
let l = 0, r = 0; // 两段数组的索引
// 从小到大的排序
while (l < leftArray.length && r < rightArray.length) {
if (leftArray[l] <= rightArray[r]) {
result.push(leftArray[l++]);
} else {
result.push(rightArray[r++]);
}
}
while (l < leftArray.length) {
result.push(leftArray[l++]);
}
while (r < rightArray.length) {
result.push(rightArray[r++]);
}
return result;
}
/**
* 实际上这里用 push 添加元素是不太好的,动态增加数组元素一旦达到某个量级之后,
* 实际上会偷偷执行一个拷贝的动作,将当前内存的数组拷贝到一个更大的内存中去,
* 所以会有一定的性能损耗,而且这个损耗会随着数组长度的增加而增加,
* 因此最好使用 new Array(initialLength) 直接申请一个确定长度的空间来初始化数组,
* 测试文件中已修改。
* */
测试一下,emmmm... 看起来是没啥问题...
源码及测试:https://github.com/yunyu950908/algorithms/blob/master/test/sort_merge.js
综上
大概就酱啦~ 还有不明白的或者是写错了的,欢迎交流纠正~
源码和测试在这里 https://github.com/yunyu950908/algorithms/blob/master/test/sort_merge.js
PS: 个人笔记,写的比较乱。有错误还请指出。
栈是一种高效的数据结构,因为数据只能在栈顶添加或删除,所以这样的操作很快,而且容易实现。栈的使用遍布程序语言实现的方方面面,从表达式求值到处理函数调用。
为了偷懒,直接用了之前写的链表,不过稍微改了改,改成了一个双向链表。
https://github.com/yunyu950908/algorithms/blob/master/data_structure/linked.js
当然你也可以用数组作为栈的底层数据结构。
/**
* Node 定义一个节点
* @param element
* @param prev
* @param next
* */
class Node {
constructor(element, prev = null, next = null) {
this.element = element;
this.prev = prev;
this.next = next;
}
}
/**
* Linked 双向链表
*
* 属性
* head 表头
* tail 表尾
*
* 方法
* push
* pop
* */
class Linked {
constructor({ head = null, tail = null, size = 0 } = {}) {
this.head = head || new Node('Head');
this.tail = tail || this.head;
this.size = size;
}
push(element) {
const newNode = new Node(element);
if (this.tail === this.head) { // 空表
this.tail = newNode;
this.tail.prev = this.head;
this.head.next = this.tail;
} else { // 非空表
const tempTail = this.tail;
this.tail = newNode;
this.tail.prev = tempTail;
tempTail.next = this.tail;
}
this.size++;
return this.size;
}
pop() {
if (this.tail === this.head) return null;
const tempTail = this.tail;
this.tail = tempTail.prev;
this.tail.next = null;
tempTail.prev = null;
this.size--;
return tempTail;
}
}
/**
* Stack
*
* 方法
* push
* pop
* */
class Stack {
constructor() {
return new Linked();
}
}
// 回文测试
function reverse(str) {
const stack = new Stack();
let result = '';
for (let i = 0; i < str.length; i++) {
stack.push(str[i]);
}
for (let i = 0; i < str.length; i++) {
result += stack.pop().element;
}
return result;
}
const str1 = 'hello world';
console.log(`original string: ${str1}`);
console.log(`reserve string: ${reverse(str1)}`);
// original string: hello world
// reserve string: dlrow olleh
// 递归测试
function factorial(n) {
if (n === 0) return 1;
else return n * factorial(n - 1);
}
console.log(`factorial: ${factorial(5)}`);
function fact(n) {
const stack = new Stack();
while (n > 1) {
stack.push(n--);
}
let result = 1;
while (stack.size > 0) {
result *= stack.pop().element;
}
return result;
}
console.log(`stack factorial: ${fact(5)}`);
// factorial: 120
// stack factorial: 120
// 括号匹配测试
function checkBrace(target) {
const result = {
left: [],
right: [],
};
const stack = new Stack();
for (let i = 0; i < target.length; i++) {
if (target[i] === '(') stack.push(i);
if (target[i] === ')') {
const flag = stack.pop();
if (!flag) result.right.push(i);
}
}
let curNode = stack.head;
while (curNode.next) {
curNode = curNode.next;
result.left.push(curNode.element);
}
return result;
}
console.log(checkBrace('(2.3 + 23) / (12 + (3.14159×0.24)'));
console.log(checkBrace('(2.3 + 23) / (12 + (3.14159×0.24))))'));
console.log(checkBrace('(2.3 + 23) / (((((12 + (3.14159×0.24))))'));
// { left: [ 13 ], right: [] }
// { left: [], right: [ 34, 35 ] }
// { left: [ 13, 14 ], right: [] }
/**
现实生活中栈的一个例子是佩兹糖果盒。想象一下你有一盒佩兹糖果,里面塞满了红
色、黄色和白色的糖果,但是你不喜欢黄色的糖果。使用栈(有可能用到多个栈)写一
段程序,在不改变盒内其他糖果叠放顺序的基础上,将黄色糖果移出。
* */
PS: 这里只是个人笔记。
数组:
链表:
下面的代码实际上还是有问题的,只用于提供思路 =。=
/**
* Node 定义一个节点
* @param element
* @param next
* */
class Node {
constructor(element, next) {
this.element = element;
this.next = next;
}
}
/**
* LinkedList 定义一个链表
*
* 属性
* head 表头
* tail 表尾
*
* 方法
* insert 插入一个节点
* remove 删除一个节点
* find 查找一个节点
* push 表尾添加一个节点
* shift 表头删除一个节点
* display 显示当前链表中的元素
* */
class LinkedList {
constructor() {
this.tail = null;
this.head = new Node(null, this.tail); // 表头的 element 始终占 null
this.size = 0;
}
push(element) {
const newNode = new Node(element, null);
if (!this.tail) { // 空表
this.tail = newNode;
this.head.next = this.tail;
} else { // 非空表
this.tail.next = newNode;
this.tail = newNode;
}
this.size++;
return this.size;
}
shift() {
const targetNode = this.head.next;
if (!targetNode) return null;
this.head.next = targetNode.next;
targetNode.next = null;
this.size--;
if (targetNode === this.tail) this.tail = null;
return targetNode;
}
insert(element, after) {
const newNode = new Node(element, null);
const afterEle = this.find(after);
if (!afterEle) return false;
newNode.next = afterEle.next;
afterEle.next = newNode;
this.size++;
return true;
}
remove(element) {
let curNode = this.head;
while (curNode.next) {
if (curNode.next.element === element) {
const prevNode = curNode;
const targetNode = curNode.next;
prevNode.next = targetNode.next;
targetNode.next = null;
this.size--;
}
curNode = curNode.next;
}
}
find(element) {
let curNode = this.head;
while (curNode.next !== null) {
curNode = curNode.next;
if (curNode.element === element) return curNode;
}
return null;
}
display() {
let curNode = this.head;
while (curNode.next !== null) {
curNode = curNode.next;
console.log(curNode);
}
}
}
代码地址:https://github.com/yunyu950908/algorithms/blob/master/data_structure/linked_list.js
function competingTest() {
console.time('generate a big Array from new Array');
const newArr = new Array(1e7);
for (let i = 0; i < newArr.length; i++) {
newArr[i] = i;
}
console.timeEnd('generate a big Array from new Array');
console.time('generate a big Array form Array.prototype.push');
const newArr2 = [];
for (let i = 0; i < 1e7; i++) {
newArr2.push(i);
}
console.timeEnd('generate a big Array form Array.prototype.push');
console.time('operate a big Array');
for (let i = 0; i < 100; i++) {
newArr.shift();
}
console.timeEnd('operate a big Array');
console.time('generate a big LinkedList');
const newLinkedList = new LinkedList();
for (let i = 0; i < 1e7; i++) {
newLinkedList.push(i);
}
console.timeEnd('generate a big LinkedList');
console.time('operate a big LinkedList');
for (let i = 0; i < 100; i++) {
newLinkedList.shift();
}
console.timeEnd('operate a big LinkedList');
}
competingTest();
generate a big Array from new Array: 80.954ms
generate a big Array form Array.prototype.push: 287.428ms
operate a big Array: 1457.407ms
generate a big LinkedList: 1678.951ms
operate a big LinkedList: 0.112ms
emmmmmmm,偷偷试了几次不同的操作数,数组大量的索引变动程线性增长。链表由于每次元素变动最多只改变目标元素和前后两个元素的索引,所以相对快很多。但在空间占用和初始化速度逊色于数组。
new Array(1e7)
直接申请了 1e7 的空间,后续直接用下标赋值。
[].push
在数组元素数量达到某个量级的时候会有一个拷贝的操作,将当前内存中的数组拷贝到一块更大的内存中去。
reference: https://visualgo.net/en/sorting
由于本宝宝是第一次学习,一边学习一边记录,难免会有错误,还请大佬指出,不胜感激~
选择排序和冒泡排序同样也是基于比较的排序,需要两个嵌套的循环。
�由上述说明,大致上一共有 5 个过程。
Tips: 选择排序交换元素时候会打破原来相同值得元素之间的顺序。比如
const arr = [2,2,1,3]
,正向排序时,arr[0]
将与arr[2]
交换, 那么两个数字2(arr[0] arr[1]
)之间的顺序将和原来的顺序不一致, 虽然它们的值相同, 但它们相对的顺序却发生了变化。这种现象称作不稳定性
。
先贴上可视化学习资料:https://visualgo.net/en/sorting
以及右下角的伪代码
repeat (numOfElements - 1) times
set the first unsorted element as the minimum
for each of the unsorted elements
if element < currentMinimum
set element as new minimum
swap minimum with first unsorted position
// swap 函数交换元素
function swap(a, b, array) {
const temp = array[a];
array[a] = array[b];
array[b] = temp;
return null;
}
// selectionSort
function selectionSort(array) {
// 外循环 n - 1 次操作排完 n 个元素
for (let i = 0; i < array.length - 1; i++) {
let minimum = i; // 记录下标
for (let j = i; j < array.length; j++) {
// 内循环遍历其他元素,替换正确的最小值下标
if (array[j] < array[minimum]) minimum = j;
}
// 内循环结束后交换 正确的最小值 到 最初记录的未排序元素的位置
swap(i, minimum, array);
}
return array;
}
测试一下,emmmm... 看起来是没啥问题...
源码及测试:https://github.com/yunyu950908/algorithms/blob/master/test/sort_selection.js
选择排序的复杂度分析跟冒泡差不多,不同之处在于即使最初的数组已经排好序,选择排序还是得自个儿确认一遍,有点蠢萌蠢萌的
结果应该是
大概就酱啦~ 代码应该写的很清楚了,还有不明白的或者是写错了的,欢迎交流纠正~
源码和测试在这里 https://github.com/yunyu950908/algorithms/blob/master/test/sort_selection.js
最一件事情最好的时期是十年前,其次是现在。
这个仓库主要用来记录一些算法学习的笔记(其余笔记以后可能会陆续整理出来),其次是对某些情况的吐槽,希望入行的新人能避坑。
先吐吐苦水。其实很久之前就想补计算机基础,尤其是算法这块儿。然而 996 的生活每天都很疲惫。
新人千万要看清 996 是什么样的 996,如果是在公司自主学习,可以有,如果是无意义的加班,钱给的再多,也还是走人吧,做程序员,生命和知识更重要。
我这 996 口怕的是每天都在重复劳作,每天修不完的bug,以及有从不按开发规范工作的 "我可是有 X 年工作经验的老员工,你得听我的。" 这样的老大,实力强就算了,然而写的代码是我有史以来见过的最丑的。
仔细想想离职原因大致有以下几点太不符合我的代码审美(三观不合):
aa
bb
cc
这样毫无意义的变量名。如果只是这样,宝宝其实还阔以忍。for (const b of a) {
for (const c of b) {
for (const d of c) {
if (xxx) {
for (const e of d) {
// do something
}
}
}
}
}
结果写出这代码的本人都看不懂自己写的什么玩意儿。这点几乎不能忍。(然而这并不是最不能忍受的)
callback hell
,明明 ES6+ 提供了很多便捷的语法糖,却还要我一层层抽丝剥茧阅读代码。'为什么不用新语法?', '不会。'
。23333333 ┑( ̄Д  ̄)┍ 无力反驳。X年工作经验
的 高级前端工程师
居然真的只会写前端,而且还写成这样的,真的是头一次见,虽然我也是毕业 ==> 宅家学习 ==> 转行 ==> 入行工作
,虽然入行工作没多久,但这 老大
实力也太差了点。绝对不能忍,离职闪人。哎呀,好像吐完苦水已经这么多字了,这篇就这样吧,总之,遇到这样的公司这样的老大,赶紧把能学的技能学差不多了闪人吧。。长此以往,基本上是学不到东西的,还搭上了自己的青春和生命,更现实的是还没多少钱给你2333333333。
2018-05-13,嘉定。
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.