（1）对于评述算法优劣术语的说明

稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

内排序 ：所有排序操作都在内存中完成；

外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

时间复杂度 : 一个算法执行所耗费的时间。

空间复杂度 : 运行完一个程序所需内存的大小。

(2)排序算法图片总结:

1.冒泡排序:

解析：1.比较相邻的两个元素，如果前一个比后一个大，则交换位置。

　2.第一轮的时候最后一个元素应该是最大的一个。

　3.按照步骤一的方法进行相邻两个元素的比较，这个时候由于最后一个元素已经是最大的了，所以最后一个元素不用比较。

2.快速排序:

解析：快速排序是对冒泡排序的一种改进，第一趟排序时将数据分成两部分，一部分比另一部分的所有数据都要小。然后递归调用，在两边都实行快速排序。

3.插入排序:

解析：

 （1） 从第一个元素开始，该元素可以认为已经被排序

 （2） 取出下一个元素，在已经排序的元素序列中从后向前扫描

 （3） 如果该元素（已排序）大于新元素，将该元素移到下一位置

 （4） 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

 （5）将新元素插入到下一位置中

 （6） 重复步骤2

2.二分查找:

解析：二分查找，也为折半查找。首先要找到一个中间值，通过与中间值比较，大的放又，小的放在左边。再在两边中寻找中间值，持续以上操作，直到找到所在位置为止。

（1）递归方法

（2）非递归方法

4.选择排序:

解析:首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

以此类推，直到所有元素均排序完毕。

5.希尔排序:

解析:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序

6.归并排序:

解析:归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

7.堆排序:

解析:堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是

小于（或者大于）它的父节点。

8.计数排序:

 解析:计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

9.桶排序:

解析:假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排

10.基数排序:

解析:基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优

先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶 计数排序：每个桶只存储单一键值 桶排序：每个桶存储一定范围的数值

冒泡排序是一次比较两个元素，如果顺序是错误的就把它们交换过来。，直到不需要再交换

快速排序的基本思想是通过一趟排序，将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序

从数列中挑出一个元素，称为 “基准”（pivot）；然后重新排序数列，所有元素比基准值小的摆放在基准前面、比基准值大的摆在基准的后面；在这个区分搞定之后，该基准就处于数列的中间位置；然后把小于基准值元素的子数列（left）和大于基准值元素的子数列（right）递归地调用 quick 方法排序完成，这就是快排的思路

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，从而达到排序的效果

插入排序的思路是基于数组本身进行调整的，首先循环遍历从 i 等于 1 开始，拿到当前的 current 的值，去和前面的值比较，如果前面的大于当前的值，就把前面的值和当前的那个值进行交换，通过这样不断循环达到了排序的目的

将最小的元素存放在序列的起始位置，再从剩余未排序元素中继续寻找最小元素，然后放到已排序的序列后面……以此类推，直到所有元素均排序完毕

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质，即子结点的键值或索引总是小于（或者大于）它的父节点。堆的底层实际上就是一棵完全二叉树，可以用数组实现

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

通过 mid 可以把该数组分成左右两个数组，分别对这两个进行递归调用排序方法，最后将两个数组按照顺序归并起来

function delRepeat(arr){

var newArray=new Array()

var len=arr.length

for(var i=0i

for(var j=i+1j

{

if(arr[i]==arr[j])

{

++i

}

}

newArray.push(arr[i])

}

return newArray

}

var arr=new Array("red","red","1","5","2")

alert(delRepeat(arr))

/*二分法*/

又称为折半查找算法，但是有缺陷就是要求数字是预先排序好的

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

}

/*十六进制颜色值的随机生成*/

function randomColor(){

var arrHex=["0","2","3","4","5","6","7","8","9","a","b","c","d"],

strHex="#",

index

for(var i=0i<6i++){

index=Math.round(Math.random()*15)

strHex+=arrHex[index]

}

return strHex

}

/*一个求字符串长度的方法*/

function GetBytes(str){

var len=str.length,

bytes=len

for(var i=0i

if(str.CharCodeAt>255){

bytes++

}

}

return bytes

}

/*插入排序*/

所谓的插入排序，就是将序列中的第一个元素看成一个有序的子序列，然后不段向后比较交换比较交换。

function insertSort(arr){

var key

for(var j = 1j <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

}

/*希尔排序*/

希尔排序 ，也称 递减增量排序算法

其实说到底也是插入排序的变种

function shellSort(array){

var stepArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]// reverse()在维基上看到这个最优的步长较小数组

var i = 0

var stepArrLength = stepArr.length

var len = array.length

var len2 =  parseInt(len/2)

for(i <stepArrLengthi++){

if(stepArr[i] >len2){

continue

}

stepSort(stepArr[i])

}

//排序一个步长

function stepSort(step){

//console.log(step)使用的步长统计

var i = 0, j = 0, f, tem, key

var stepLen = len%step >0 ?  parseInt(len/step) + 1 : len/step

for(i <stepi++){//依次循环列

for(j=1/*j <stepLen &&*/step * j + i <lenj++){//依次循环每列的每行

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

}

/*快速排序*/

快速排序算法就系对冒泡排序的一种改进，采用的就是算法理论中的分治递归的思想。

具体做法：通过一趟排序将待排序的纪录分割成两部分，其中一部分的纪录值比另外一部分的纪录值要小，就可以继续分别对这两部分纪录进行排序；不段的递归实施上面两个操作，从而实现纪录值的排序。

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均为游标

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=0i

for(var j=array.length-1j>ij--){

if(array[j]

temp = array[j]

array[j]=array[j-1]

array[j-1]=temp

}

}

}

return array

}

/*js递归实现方案*/

递归函数是在一个函数通过调用自身的情况下去解决的：

方式如下：

function factorial(num){

if(num<=1){

return 1

}else{

return num*factorial(num-1)

}

}

但是这在js里面可能会出现错误：

var anotherFactorial = factorial

factorial=null

alert(anoterFactorial(4))

因为在调用anoterFactorial时内部的factorial已经不存在了。

解决方法是通过arguments.callee来解决。

如下：

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=1i

this.length=this.length-1

return rs

}

if (Array.prototype.push==null)

Array.prototype.push = function (){

for (var i=0i

return this.length

}

var commandList = []

var nAction = 0//控制每次运行多少个动作

var functionConstructor = function(){}.constructor

function executeCommands(){

for (var i=0i

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》简单的选择排序：简单的前后交互。

/*简单选择法排序*/

其实基本的思想就是从待排序的数组中选择最小或者最大的，放在起始位置，然后从剩下的数组中选择最小或者最大的排在这公司数的后面。

function selectionSort(data)

{

var i, j, min, temp , count=data.length

for(i = 0i <count - 1i++) {

/* find the minimum */

min = i

for (j = i+1j <countj++)

{    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》树型排序：又称锦标赛排序，首先对n个元素进行两两比较，然后在其中[n/2]个较小者再进行两两比较如此重复直至选出最小的关键字的纪录为止。（可用完全二差树表示）。缺点：辅助空间需求过大，和“最大值”进行多余比较

《3》堆排序：（不适用于纪录数较少的文件）

堆排序算法的过程如下:

1)得到当前序列的最小(大)的元素

2)把这个元素和最后一个元素进行交换,这样当前的最小(大)的元素就放在了序列的最后,而原先的最后一个元素放到了序列的最前面

3)的交换可能会破坏堆序列的性质(注意此时的序列是除去已经放在最后面的元素),因此需要对序列进行调整,使之满足于上面堆的性质.

重复上面的过程,直到序列调整完毕为止.

js实现：

/**

*堆排序

* @param items数组

* @return排序后的数组

*/

function heapSort(items)

{

items = array2heap(items)//将数组转化为堆

for(var i = items.length - 1i >= 0i--)

{

items = swap(items, 0, i)//将根和位置i的数据交换(用于将最大值放在最后面)

items = moveDown(items, 0, i - 1)//数据交换后恢复堆的属性

}

return items

}

/**

*将数组转换为堆

* @param items数组

* @return堆

*/

function array2heap(items)

{

for(var i = Math.ceil(items.length / 2) - 1i >= 0i--)

{

items = moveDown(items, i, items.length - 1)//转换为堆属性

}

return items

}

/**

*转换为堆

* @param items数组

* @param first第一个元素

* @param last最后一个元素

* @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)//交换数据

first = largest  //往下移

largest = 2 * first + 1

}

else

{

largest = last + 1//跳出循环

}

}

return items

}

/**

*交换数据

* @param items数组

* @param index1索引1

* @param index2索引2

* @return数据交换后的数组

*/

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))

所谓归并就是将两个或者两个以上的有序表合成一个新的有序表。

递归形式的算法在形式上较为简洁但实用性较差，与快速排序和堆排序相比，归并排序的最大特点是，它是一种稳定的排序方法。

js实现归并：

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))

归并排序待续，先睡了：

归并排序：

//将有二个有序数列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 = 0i <ki++)

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) //再将二个有序数列合并

}

return  Arr

}

var Arr=new Array(1,65,45,98,56,78)

alert(mergesort(Arr,0,Arr.length-1))

/*比较两个字符串的相似性－Levenshtein算法简介*/

问题与描述：

近似字符串匹配问题

说明：设给定样本，对于任意文本串，样本P在文本T中的K-近似匹配（K-approximate match）是指P在T中包含最多K个差异的匹配，这里的差别指：

（1）修改：P与T中对应的字符不同

（2）删除：T中含有一个未出现在P中的字符

（3）插入：T中不包含出现在P中的一个字符

（也就是编辑距离问题）

例如：

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

经过1：插入2：删除3：修改

那么就是一个3-近似问题

事实上，两个字符串可能有不得出不同的差别数量，所以K-近似匹配要求：

（1）差别数最多为K个

（2）差别数为所有匹配方式下最少的称为编辑距离

（字符串T到P最少的差别数称为T和P的编辑距离）

试验要求：

（1）利用动态规划方法给出两个字符串编辑距离的算法

（2）分析复杂度

（3）考虑其它方法

Levenshtein Distance来文史特距离

goodzzp

LD也叫edit distance，它用来表示2个字符串的相似度，不同于Hamming Distance，它可以用来比较2个长度不同的字符串。LD定义为需要最少多少步基本操作才能让2个字符串相等，基本操作包含3个：

1，插入；

2，删除；

3，替换；

比如，kiteen和sitting之间的距离可以这么计算：

1，kitten – >sitten,替换k为s；

2，sitten – >sittin,替换e为i

3，sittin – >sitting,增加g；

所以，其LD为3；

计算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]；

这个算法其实就是一个矩阵的计算：

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

首先给定第一行和第一列，然后，每个值d[i,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))

最后一行，最后一列的那个值就是LD的结果。

LD(str1,str2) <= max(str1.len,str2.len)；

有人提出了Levenshtein automaton（Levenshtein自动机）来计算和某个字符串距离小于某个值的集合。这样能够加快近似字符串的计算过程。见文献：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 Matching GONZALONAVARRO

这篇文章里面对这个方面（字符串相似）进行了很多描述。其中，包含了动态规划法计算Edit distance的方法。

js实现：

//求两个字符串的相似度,返回差别字符数,Levenshtein Distance算法实现

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 = 0i <= ni++) {

d[i]=[]

d[i][0] = i

}

for (j = 0j <= mj++) {

d[0][j] = j

}

// Step 3

for (i = 1i <= ni++) {

s_i = s.charAt (i - 1)

// Step 4

for (j = 1j <= mj++) {

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]

}

//求两个字符串的相似度,返回相似度百分比

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)

}

//求三个数字中的最小值

function Minimum(a,b,c){

return a

}

var str1="ddsddf",str2="xdsfsx"

alert(Levenshtein_Distance_Percent(str1,str2))