入門級算法-線性查找-時間復雜度O(n)–相當於算法界中的HelloWorld
//線性搜索(入門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 + "
");
}
//節點類
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
