//线性搜索(入门HelloWorld) //A为数组，x为要搜索的值 function linearSearch(A, x) { for (var i = 0; i < A.length; i++) { if (A[i] == x) { return i; } } return -1; }
二分查找(又称折半查找) - 适用于已排好序的线性结构 - 时间复杂度O(logN)
//二分搜索 //A为已按"升序排列"的数组，x为要查询的元素 //返回目标元素的下标 function binarySearch(A, x) { var low = 0, high = A.length - 1; while (low <= high) { var mid = Math.floor((low + high) / 2); //下取整 if (x == A[mid]) { return mid; } if (x < A[mid]) { high = mid - 1; } else { low = mid + 1; } } return -1; }
冒泡排序 -- 时间复杂度O(n^2)
//冒泡排序 function bubbleSort(A) { for (var i = 0; i < A.length; i++) { var sorted = true; //注意：内循环是倒着来的 for (var j = A.length - 1; j > i; j--) { if (A[j] < A[j - 1]) { swap(A, j, j - 1); sorted = false; } } if (sorted) { return; } } }
选择排序 -- 时间复杂度O(n^2)
//选择排序 //思路：找到最小值的下标记下来，再交换 function selectionSort(A) { for (var i = 0; i < A.length - 1; i++) { var k = i; for (var j = i + 1; j < A.length; j++) { if (A[j] < A[k]) { k = j; } } if (k != i) { var t = A[k]; A[k] = A[i]; A[i] = t; println(A); } } return A; }
插入排序 -- 时间复杂度O(n^2)
//插入排序 //假定当前元素之前的元素已经排好序，先把自己的位置空出来， //然后前面比自己大的元素依次向后移，直到空出一个"坑"， //然后把目标元素插入"坑"中 function insertSort(A) { for (var i = 1; i < A.length; i++) { var x = A[i]; for (var j = i - 1; j >= 0 && A[j] > x; j--) { A[j + 1] = A[j]; } if (A[j + 1] != x) { A[j + 1] = x; println(A); } } return A; }
字符串反转 -- 时间复杂度O(logN)
//字符串反转(比如：ABC -> CBA) function inverse(s) { var arr = s.split(''); var i = 0, j = arr.length - 1; while (i < j) { var t = arr[i]; arr[i] = arr[j]; arr[j] = t; i++; j--; } return arr.join(''); }
关于稳定性排序的一个结论：
基于比较的简单排序算法，即时间复杂度为O(N^2)的排序算法，通常可认为均是稳定排序
其它先进的排序算法，比如归并排序、堆排序、桶排序之类（通常这类算法的时间复杂度可优化为n*LogN），通常可认为均是不稳定排序
单链表实现
<script type="text/javascript"> function print(msg) { document.write(msg); } function println(msg) { print(msg + "<br/>"); } //节点类 var Node = function (v) { this.data = v; //节点值 this.next = null; //后继节点 } //单链表 var SingleLink = function () { this.head = new Node(null); //约定头节点仅占位，不存值 //插入节点 this.insert = function (v) { var p = this.head; while (p.next != null) { p = p.next; } p.next = new Node(v); } //删除指定位置的节点 this.removeAt = function (n) { if (n <= 0) { return; } var preNode = this.getNodeByIndex(n - 1); preNode.next = preNode.next.next; } //取第N个位置的节点(约定头节点为第0个位置) //N大于链表元素个数时，返回最后一个元素 this.getNodeByIndex = function (n) { var p = this.head; var i = 0; while (p.next != null && i < n) { p = p.next; i++; } return p; } //查询值为V的节点， //如果链表中有多个相同值的节点， //返回第一个找到的 this.getNodeByValue = function (v) { var p = this.head; while (p.next != null) { p = p.next; if (p.data == v) { return p; } } return null; } //打印输出所有节点 this.print = function () { var p = this.head; while (p.next != null) { p = p.next; print(p.data + " "); } println(""); } } //测试单链表L中是否有重复元素 function hasSameValueNode(singleLink) { var i = singleLink.head; while (i.next != null) { i = i.next; var j = i; while (j.next != null) { j = j.next; if (i.data == j.data) { return true; } } } return false; } //单链表元素反转 function reverseSingleLink(singleLink) { var arr = new Array(); var p = singleLink.head; //先跑一遍，把所有节点放入数组 while (p.next != null) { p = p.next; arr.push(p.data); } var newLink = new SingleLink(); //再从后向前遍历数组,加入新链表 for (var i = arr.length - 1; i >= 0; i--) { newLink.insert(arr[i]); } return newLink; } var linkTest = new SingleLink(); linkTest.insert('A'); linkTest.insert('B'); linkTest.insert('C'); linkTest.insert('D'); linkTest.print();//A B C D var newLink = reverseSingleLink(linkTest); newLink.print();//D C B A </script>
关于邻接矩阵、邻接表的选择：