/*去重*/
function delRepeat(arr){
var newArray=new Array();
var len=arr.length;
for(var i=0;i
for(var j=i+1;j
{
if(arr[i]==arr[j])
{
++i;
}
}
newArray.push(arr[i]);
}
return newArray;
}
var arr=new Array("red","red","1","5","2");
alert(delRepeat(arr));
/*二分法*/
又稱(chēng)為折半查找算法银萍，但是有缺陷就是要求數(shù)字是預(yù)先排序好的
function binary(items,value){
var startIndex=0,
stopIndex=items.length-1,
midlleIndex=(startIndex+stopIndex)>>>1;
while(items[middleIndex]!=value && startIndex
if(items[middleIndex]>value){
stopIndex=middleIndex-1;
}else{
startIndex=middleIndex+1;
}
middleIndex=(startIndex+stopIndex)>>>1;
}
return items[middleIndex]!=value ? false:true;
}
/*十六進(jìn)制顏色值的隨機(jī)生成*/
function randomColor(){
var arrHex=["0","2","3","4","5","6","7","8","9","a","b","c","d"],
strHex="#",
index;
for(var i=0;i<6;i++){
index=Math.round(Math.random()*15);
strHex+=arrHex[index];
}
return strHex;
}
/*一個(gè)求字符串長(zhǎng)度的方法*/
function GetBytes(str){
var len=str.length,
bytes=len;
for(var i=0;i
if(str.CharCodeAt>255){
bytes++;
}
}
return bytes;
}
/*插入排序*/
所謂的插入排序，就是將序列中的第一個(gè)元素看成一個(gè)有序的子序列很魂，然后不段向后比較交換比較交換。
function insertSort(arr){
var key;
for(var j = 1; j < arr.length ; j++){
//排好序的
var i = j - 1;
key = arr[j];
while(i >= 0 && arr[i] > key){
arr[i + 1] = arr[i];
i --;
}
arr[i + 1] = key;
}
return arr;
}
/*希爾排序*/
希爾排序诗箍，也稱(chēng)遞減增量排序算法
其實(shí)說(shuō)到底也是插入排序的變種
function shellSort(array){
var stepArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]; // reverse()在維基上看到這個(gè)最優(yōu)的步長(zhǎng)較小數(shù)組
var i = 0;
var stepArrLength = stepArr.length;
var len = array.length;
var len2 = ?parseInt(len/2);
for(;i < stepArrLength; i++){
if(stepArr[i] > len2){
continue;
}
stepSort(stepArr[i]);
}
//排序一個(gè)步長(zhǎng)
function stepSort(step){
//console.log(step)使用的步長(zhǎng)統(tǒng)計(jì)
var i = 0, j = 0, f, tem, key;
var stepLen = len%step > 0 ? ?parseInt(len/step) + 1 : len/step;
for(;i < step; i++){//依次循環(huán)列
for(j=1;/*j < stepLen && */step * j + i < len; j++){//依次循環(huán)每列的每行
tem = f = step * j + i;
key = array[f];
while((tem-=step) >= 0){//依次向上查找
if(array[tem] > key){
array[tem+step] = array[tem];
}else{
break;
}
}
array[tem + step ] = key;
}
}
}
return array;
}
/*快速排序*/
快速排序算法就系對(duì)冒泡排序的一種改進(jìn)伏伐，采用的就是算法理論中的分治遞歸的思想。
具體做法：通過(guò)一趟排序?qū)⒋判虻募o(jì)錄分割成兩部分可训，其中一部分的紀(jì)錄值比另外一部分的紀(jì)錄值要小膘滨，就可以繼續(xù)分別對(duì)這兩部分紀(jì)錄進(jìn)行排序甘凭；不段的遞歸實(shí)施上面兩個(gè)操作，從而實(shí)現(xiàn)紀(jì)錄值的排序火邓。
function sort(arr){
return quickSort(arr,0,arr.length-1);
function quickSort(arr,l,r){
if(l
var mid=arr[parseInt((l+r)/2)],i=l-1,j=r+1;
while(true){
//大的放到右邊丹弱，小的放到左邊, i與j均為游標(biāo)
while(arr[++i]
while(arr[--j]>mid);
if(i>=j)break;//判斷條件
var temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
quickSort(arr,l,i-1);
quickSort(arr,j+1,r);
}
return arr;
}
}
function main(){
var list=new Array(49,38,65,97,76,13,27);
document.write(sort(list).valueOf());
}
main();
/*冒泡法*/
function bullSort(array){
var temp;
for(var i=0;i
for(var j=array.length-1;j>i;j--){
if(array[j]
temp = array[j];
array[j]=array[j-1];
array[j-1]=temp;
}
}
}
return array;
}
/*js遞歸實(shí)現(xiàn)方案*/
遞歸函數(shù)是在一個(gè)函數(shù)通過(guò)調(diào)用自身的情況下去解決的：
方式如下：
function factorial(num){
if(num<=1){
return 1;
}else{
return num*factorial(num-1);
}
}
但是這在js里面可能會(huì)出現(xiàn)錯(cuò)誤：
var anotherFactorial = factorial;
factorial=null;
alert(anoterFactorial(4));
因?yàn)樵谡{(diào)用anoterFactorial時(shí)內(nèi)部的factorial已經(jīng)不存在了。
解決方法是通過(guò)arguments.callee來(lái)解決铲咨。
如下：
function factorial(num){
if(num<=1){
return 1;
}else{
return num*arguments.callee(num-1);
}
var anotherFactorial = factorial;
factorial = null;
alert(anotherFactorial(4));
成功６愀臁！Ｏ死铡坯苹！
}
/**js模擬多線程**/
if (Array.prototype.shift==null)
Array.prototype.shift = function (){
var rs = this[0];
for (var i=1;i
this.length=this.length-1
return rs;
}
if (Array.prototype.push==null)
Array.prototype.push = function (){
for (var i=0;i
return this.length;
}
var commandList = [];
var nAction = 0;//控制每次運(yùn)行多少個(gè)動(dòng)作
var functionConstructor = function(){}.constructor;
function executeCommands(){
for (var i=0;i
if (commandList.length>0){
var command = commandList.shift();
if (command.constructor == functionConstructor)
if (command.scheduleTime == null || new Date()-command.scheduleTime>0)
command();
else
commandList.push(command);
}
}
function startNewTask(){
var resultTemp = document.getElementById("sampleResult").cloneNode(true);
with (resultTemp){
id="";style.display="block";style.color=(Math.floor(Math.random()* (1<<23)).toString(16)+"00000").substring(0,6);
}
document.body.insertBefore(resultTemp,document.body.lastChild);
commandList.push(function(){simThread(resultTemp,1);});
nAction++;
}
function ?simThread(temp,n){
if (temp.stop) n--;
else temp.innerHTML = temp.innerHTML - (-n);
if (n<1000)
commandList.push(function(){simThread(temp,++n)});
else{
var command = function(){document.body.removeChild(temp);;nAction--;};
command.scheduleTime = new Date()-(-2000);
commandList.push(command);
}
}
window.onload = function(){setInterval("executeCommands()",1);}
/
/*選擇法排序*/
選擇法主要有三種：
《1》簡(jiǎn)單的選擇排序：簡(jiǎn)單的前后交互。
/*簡(jiǎn)單選擇法排序*/
其實(shí)基本的思想就是從待排序的數(shù)組中選擇最小或者最大的摇天，放在起始位置粹湃，然后從剩下的數(shù)組中選擇最小或者最大的排在這公司數(shù)的后面恐仑。
function selectionSort(data)
{
var i, j, min, temp , count=data.length;
for(i = 0; i < count - 1; i++) {
/* find the minimum */
min = i;
for (j = i+1; j < count; j++)
{ ? ?if (data[j] < data[min])
{ min = j;}
}
/* swap data[i] and data[min] */
temp = data[i];
data[i] = data[min];
data[min] = temp;
}
return data;
}
《2》樹(shù)型排序：又稱(chēng)錦標(biāo)賽排序，首先對(duì)n個(gè)元素進(jìn)行兩兩比較为鳄，然后在其中[n/2]個(gè)較小者再進(jìn)行兩兩比較如此重復(fù)直至選出最小的關(guān)鍵字的紀(jì)錄為止裳仆。（可用完全二差樹(shù)表示）。缺點(diǎn)：輔助空間需求過(guò)大孤钦，和“最大值”進(jìn)行多余比較
《3》堆排序：（不適用于紀(jì)錄數(shù)較少的文件）
堆排序算法的過(guò)程如下:
1)得到當(dāng)前序列的最小(大)的元素
2)把這個(gè)元素和最后一個(gè)元素進(jìn)行交換,這樣當(dāng)前的最小(大)的元素就放在了序列的最后,而原先的最后一個(gè)元素放到了序列的最前面
3)的交換可能會(huì)破壞堆序列的性質(zhì)(注意此時(shí)的序列是除去已經(jīng)放在最后面的元素),因此需要對(duì)序列進(jìn)行調(diào)整,使之滿(mǎn)足于上面堆的性質(zhì).
重復(fù)上面的過(guò)程,直到序列調(diào)整完畢為止.
js實(shí)現(xiàn)：
/**
*堆排序
* @param items數(shù)組
* @return排序后的數(shù)組
*/
function heapSort(items)
{
items = array2heap(items); //將數(shù)組轉(zhuǎn)化為堆
for(var i = items.length - 1; i >= 0; i--)
{
items = swap(items, 0, i); //將根和位置i的數(shù)據(jù)交換(用于將最大值放在最后面)
items = moveDown(items, 0, i - 1); //數(shù)據(jù)交換后恢復(fù)堆的屬性
}
return items;
}
/**
*將數(shù)組轉(zhuǎn)換為堆
* @param items數(shù)組
* @return堆
*/
function array2heap(items)
{
for(var i = Math.ceil(items.length / 2) - 1; i >= 0; i--)
{
items = moveDown(items, i, items.length - 1); //轉(zhuǎn)換為堆屬性
}
return items;
}
/**
*轉(zhuǎn)換為堆
* @param items數(shù)組
* @param first第一個(gè)元素
* @param last最后一個(gè)元素
* @return堆
*/
function moveDown(items, first, last)
{
var largest = 2 * first + 1;
while(largest <= last)
{
if(largest < last && items[largest] < items[largest + 1])
{
largest++;
}
if(items[first] < items[largest])
{
items = swap(items, first, largest); //交換數(shù)據(jù)
first = largest; ? //往下移
largest = 2 * first + 1;
}
else
{
largest = last + 1; //跳出循環(huán)
}
}
return items;
}
/**
*交換數(shù)據(jù)
* @param items數(shù)組
* @param index1索引1
* @param index2索引2
* @return數(shù)據(jù)交換后的數(shù)組
*/
function swap(items, index1, index2)
{
var tmp = items[index1];
items[index1] = items[index2];
items[index2] = tmp;
return items;
}
var a = [345,44,6,454,10,154,3,12,11,4,78,9,0,47,88,9453,4,65,1,5];
document.write(heapSort(a));
所謂歸并就是將兩個(gè)或者兩個(gè)以上的有序表合成一個(gè)新的有序表歧斟。
遞歸形式的算法在形式上較為簡(jiǎn)潔但實(shí)用性較差，與快速排序和堆排序相比偏形，歸并排序的最大特點(diǎn)是静袖，它是一種穩(wěn)定的排序方法。
js實(shí)現(xiàn)歸并：
function MemeryArray(Arr,n, Brr, m)
{ ? ?? var i, j, k;
var Crr=new Array();
i = j = k = 0;
while (i < n && j < m)
{
if (Arr[i] < Brr[j])
Crr[k++] = Arr[i++];
else
Crr[k++] = Brr[j++];
}
while (i < n)
Crr[k++] = Arr[i++];
while (j < m)
Crr[k++] = Brr[j++];
return Crr;
}
var Arr=new Array(45,36,89,75,65);
var Brr=new Array(48,76,59,49,25);
alert(MemeryArray(Arr , Arr.length , Brr , Brr.length));
歸并排序待續(xù)壳猜，先睡了：
歸并排序：
//將有二個(gè)有序數(shù)列a[first...mid]和a[mid...last]合并勾徽。
function mergearray(Arr,first,mid,last,tempArr)
{
var i = first, j = mid + 1;
var m = mid, ? n = last;
var k = 0;
while (i <= m && j <= n)
{
if (Arr[i] < Arr[j])
tempArr[k++] = Arr[i++];
else
tempArr[k++] = Arr[j++];
}
while (i <= m)
tempArr[k++] = Arr[i++];
while (j <= n)
tempArr[k++] = Arr[j++];
for (i = 0; i < k; i++)
Arr[first + i] = tempArr[i];
}
function mergesort(Arr,first,last)
{
var tempArr=new Array();
if (first < last)
{
var mid = (first + last)>>>1;
mergesort(Arr, first, mid, tempArr); ? ?//左邊有序
mergesort(Arr, mid + 1, last, tempArr); ?//右邊有序
mergearray(Arr, first, mid, last, tempArr); ?//再將二個(gè)有序數(shù)列合并
}
return ?Arr;
}
var Arr=new Array(1,65,45,98,56,78);
alert(mergesort(Arr,0,Arr.length-1));
/*比較兩個(gè)字符串的相似性－Levenshtein算法簡(jiǎn)介*/
問(wèn)題與描述：
近似字符串匹配問(wèn)題
說(shuō)明：設(shè)給定樣本，對(duì)于任意文本串统扳，樣本P在文本T中的K-近似匹配（K-approximate match）是指P在T中包含最多K個(gè)差異的匹配，這里的差別指：
（1）修改：P與T中對(duì)應(yīng)的字符不同
（2）刪除：T中含有一個(gè)未出現(xiàn)在P中的字符
（3）插入：T中不包含出現(xiàn)在P中的一個(gè)字符
（也就是編輯距離問(wèn)題）
例如：
T: a p r o x i o m a l l y
P: a p p r o x i m a t l y
經(jīng)過(guò)1：插入2：刪除3：修改
那么就是一個(gè)3-近似問(wèn)題
事實(shí)上畅姊，兩個(gè)字符串可能有不得出不同的差別數(shù)量咒钟，所以K-近似匹配要求：
（1）差別數(shù)最多為K個(gè)
（2）差別數(shù)為所有匹配方式下最少的稱(chēng)為編輯距離
（字符串T到P最少的差別數(shù)稱(chēng)為T(mén)和P的編輯距離）
試驗(yàn)要求：
（1）利用動(dòng)態(tài)規(guī)劃方法給出兩個(gè)字符串編輯距離的算法
（2）分析復(fù)雜度
（3）考慮其它方法
Levenshtein Distance來(lái)文史特距離
goodzzp
LD也叫edit distance，它用來(lái)表示2個(gè)字符串的相似度若未，不同于Hamming Distance朱嘴，它可以用來(lái)比較2個(gè)長(zhǎng)度不同的字符串。LD定義為需要最少多少步基本操作才能讓2個(gè)字符串相等粗合，基本操作包含3個(gè)：
1萍嬉，插入；
2隙疚，刪除壤追；
3，替換供屉；
比如行冰，kiteen和sitting之間的距離可以這么計(jì)算：
1，kitten – > sitten,替換k為s伶丐；
2悼做，sitten – > sittin,替換e為i;
3，sittin – > sitting,增加g哗魂；
所以肛走，其LD為3；
計(jì)算LD的算法表示為：
int LevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
// d is a table with lenStr1+1 rows and lenStr2+1 columns
declare int d[0..lenStr1, 0..lenStr2]
// i and j are used to iterate over str1 and str2
declare int i, j, cost
for i from 0 to lenStr1
d[i, 0] := i
for j from 0 to lenStr2
d[0, j] := j
for i from 1 to lenStr1
for j from 1 to lenStr2
if str1[i] = str2[j] then cost := 0
else cost := 1
d[i, j] := minimum(
d[i-1, j ] + 1,// deletion
d[i , j-1] + 1,// insertion
d[i-1, j-1] + cost// substitution
)
return d[lenStr1, lenStr2]录别；
這個(gè)算法其實(shí)就是一個(gè)矩陣的計(jì)算：
k i t t e n
0 1 2 3 4 5 6
s 1 1 2 3 4 5 6
i 2 2 1 2 3 4 5
t 3 3 2 1 2 3 4
t 4 4 3 2 1 2 3
i 5 5 4 3 2 2 3
n 6 6 5 4 3 3 2
g 7 7 6 5 4 4 3
首先給定第一行和第一列朽色，然后故硅，每個(gè)值d[i,j]這樣計(jì)算：d[i,j] = min(d[i-1,j]+ 1,d[i,j-1] +1,d[i-1,j-1]+(str1[i] == str2[j]?0:1));
最后一行，最后一列的那個(gè)值就是LD的結(jié)果纵搁。
LD(str1,str2) <= max(str1.len,str2.len)吃衅；
有人提出了Levenshtein automaton（Levenshtein自動(dòng)機(jī)）來(lái)計(jì)算和某個(gè)字符串距離小于某個(gè)值的集合。這樣能夠加快近似字符串的計(jì)算過(guò)程腾誉。見(jiàn)文獻(xiàn)：Klaus U. Schulz, Stoyan Mihov, Fast String Correction with Levenshtein-Automata. International Journal of Document Analysis and Recognition, 5(1):67--85, 2002.
A Guided Tour to Approximate String MatchingGONZALONAVARRO
這篇文章里面對(duì)這個(gè)方面（字符串相似）進(jìn)行了很多描述徘层。其中，包含了動(dòng)態(tài)規(guī)劃法計(jì)算Edit distance的方法利职。
js實(shí)現(xiàn)：
//求兩個(gè)字符串的相似度,返回差別字符數(shù),Levenshtein Distance算法實(shí)現(xiàn)
function Levenshtein_Distance(s,t){
var n=s.length;// length of s
var m=t.length;// length of t
var d=[];// matrix
var i;// iterates through s
var j;// iterates through t
var s_i;// ith character of s
var t_j;// jth character of t
var cost;// cost
// Step 1
if (n == 0) return m;
if (m == 0) return n;
// Step 2
for (i = 0; i <= n; i++) {
d[i]=[];
d[i][0] = i;
}
for (j = 0; j <= m; j++) {
d[0][j] = j;
}
// Step 3
for (i = 1; i <= n; i++) {
s_i = s.charAt (i - 1);
// Step 4
for (j = 1; j <= m; j++) {
t_j = t.charAt (j - 1);
// Step 5
if (s_i == t_j) {
cost = 0;
}else{
cost = 1;
}
// Step 6
d[i][j] = Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);
}
}
// Step 7
return d[n][m];
}
//求兩個(gè)字符串的相似度,返回相似度百分比
function Levenshtein_Distance_Percent(s,t){
var l=s.length>t.length?s.length:t.length;
var d=Levenshtein_Distance(s,t);
return (1-d/l).toFixed(4);
}
//求三個(gè)數(shù)字中的最小值
function Minimum(a,b,c){
return a
}
var str1="ddsddf",str2="xdsfsx";
alert(Levenshtein_Distance_Percent(str1,str2));
