一.二叉树的遍历
二叉搜索树插入结点
function insertval(node,newnode){
if(newnode.val<node.val){
if(!node.left){
node.left=newnode;
}else{
insertval(node.left,newnode);
}
}
else{
if(!node.right){
node.right=newnode;
}else{
insertval(node.right,newnode);
}
}
}
中序遍历
function inorder(node,callback){
if(!node){
inorder(node.left,callback);
callback(node.value);
inorder(node.right,callback);
}
}
先序遍历(递归)
function preorder(node,callback){
if(node){
callback(node.value);
preorder(node.left,callback);
preorder(node.right,callback);
}
}
先序遍历（非递归）
function preorder(node,callback){
var stack=[];
if(node) stack.push(node);
while(stack){
var temp=satck.pop();
callback(temp.value);
if(temp.right) stack.push(temp.right);
if(temp.left) stack.push(temp.left);
}
}
中序遍历（非递归）
function inorder(node,callback){
var arr=[];
while(true){
while(node){
arr.push(node);
node=node.left;
}
if(！arr.length) break;
var temp=arr.pop();
callback(temp.value());
node=temp.right;
}
}
后序遍历
function postorder(node,callback){
if(node){
postorder(node.left,callback);
postorder(node.right,callback);
callback(node.value);
}
}
后序遍历（非递归）
function afterorder(node,callback){
var arr=[];
var res=[];
if(node) arr.push(node);
while(arr.length){
var temp=arr.pop();
res.push(temp);
if(temp.left) arr.push(temp.left);
if(temp.right) arr.push(temp.right);
}
res.reverse();
res.forEach(item=>callback(item.value));
}
层序遍历
function fromtoptobottom(root,callback){
var arr=[];
var data=[];
if(root){
arr.push(root);
}
while(arr.length){
var node=arr.shift();
if(node.left){
arr.push(node.left);
}
if(node.right){
arr.push(node.right);
}
data.push(node.val);
}
return data;
}
寻找搜索树最小值
function minval(node){
if(node){
while(node&&node.left!==null){
node=node.left
}
return node.value;
}
return null
}
寻找搜索树最大值
function maxvalue(node){
if(node){
while(node&&node.right){
node=node.right;
}
return node.value;
}
return null;
}
寻找搜索树特定值
function selectval(node,text){
if(!node) return false;
if(text<node.val){
return select(node.left,text);
}
else if(text>node.val){
return select(node.right,text);
}
else{
return true;
}
}
搜索树移除一个节点
function removenode(node,text){
if(!node) return null;
if(text<node.val){
node.left=removenode(node.left,text);
return node;
}
else if(text>node.val){
node.right=removenode(node.right,text);
return node;
}
else{
//第一种情况删除一个叶节点
if(node.left===null&&node.right===null){
node=null;
return node;
}
//第二种情况删除有一个子节点的结点
if(node.left===null){
node=node.right;
return node;
}else if(node.right===null){
node=node.left;
return node;
}
//第三种情况删除有两个子节点的结点
var aux=minval(node.right);
node.val=aux.val;
node.right= removenode(node.right,aux.val);
return node;
}
}
二.排序
1.冒泡排序
思想：相邻数据相比较，较大者放在后面，从前往后比较，共进行n-1轮。
function buble(arr){
for(var i=0;i<arr.length;i++){
for(var j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
[arr[j],arr[j+1]]=[arr[j+1],arr[j]];//交换两者的值
}
}
}
console.log(arr);
}
2.选择排序
思想:选出数组中最小值放在第一位，第二小放在第二位，以此类推。
function selectsort(A){
for(var i=0;i<arr.length;i++){
var min=i;
for(var j=i+1;j<arr.length;j++){
if(arr[j]<arr[min]){
min=j;
}
}
if(min!==i){
[arr[i],arr[min]]=[arr[min],arr[i]];
}
}
console.log(arr);
}
3． 插入排序：
输入：N个自然数序列
输出：满足a1<=a2<=…<=an的排序
计算时间是n*n 原地排序
对近乎有序的序列排序性能更好
function insertsort(A){
for(var i=1;i<A.length;i++){
var key=A[i];
for(var j=i-1;j>=0 ;j--){
if(A[j]>key){
A[j+1]=A[j];
}
else{
break;
}
}
A[j+1]=key;
}
return A
}
4.希尔排序
5.归并排序（求逆对数）
分治问题
要求解问题P：
分：将问题P分解为规模更小的子问题P1,P2,…,PK.
治：递归求解这些子问题。
合并：将子问题P1,P2,…,PK的解合并为问题P的解。
利用分治策略：
分：将n个元素分为两个n/2大小的子序列。
治：分别将两个子序列排序。
合并：将两个有序子序列合并，得到完整的有序序列。
输入：存放在数组A中的n个数
输出：输入n个数的有序序列
计算时间是nlogn 需要的存储空间是n
归并排序（自顶向下递归）
function mergesort(A,p,r){
if(p<r){
var q=Math.floor((p+r)/2);
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r)
}
}
function merge(A,p,q,r){
var n1=q-p+1;
var n2=r-q;
var arr=[];
var arr1=[];
for(var i=0;i<n1;i++){
arr[i]=A[p+i];
}
for(var j=0;j<n2;j++){
arr1[j]=A[q+1+j];
}
arr[arr.length]=Infinity;
arr1[arr1.length]=Infinity;
var i=0;
var j=0;
for(var k=p;k<=r;k++){
if(arr[i]<=arr1[j]){
A[k]=arr[i];
i=i+1;
}
else{
A[k]=arr1[j];
j=j+1;
}
}
console.log(A);
}
归并排序（自底向上）
function mergesortl(A){
for(var sz=1;sz<=A.length;sz+=sz){
for(var i=0;i+sz<A.length;i+=sz+sz){
merge(A,i,i+sz-1,Math.min(i+sz+sz-1,A.length-1))
}
}
console.log(A);
}
求逆序数：
var xulie=0;//全局变量，用于统计逆序列数
mergesortxulie([2,4,3,1,4,12,6],0,6)；
function mergesortxulie(A,l,r){
if(l<r){
var p=Math.floor((l+r)/2);
mergesortxulie(A,l,p);
mergesortxulie(A,p+1,r);
mergexulie(A,l,p,r);
}
console.log(A);
}
function mergexulie(A,p,q,r){
var temp=[];
var i=p;
var j=q+1;
var k=0;
while(i<=q && j<=r){
if(A[i]<=A[j]){
temp[k++]=A[i++];
}
else{
temp[k++]=A[j++];
xulie=xulie+(q-i+1);
}
}
while(i<=q){
temp[k++]=A[i++];
}
while(j<=r){
temp[k++]=A[j++];
}
for(var i=0;i<k;i++){
A[p+i]=temp[i];
}
console.log(xulie);
}
6.快排（求数组中第n大的元素）
分治算法计算时间是nlogn 原地排序
分：将原数组围绕某划分元素X划分为两个子数组，使得前面子数组中元素<=X<=后面子数组中元素
治：递归对子数组进行排序
合并：不需要任何工作
关键：线性时间的划分过程
快排的最坏情况：输入数据是有序或者逆序的，基于最小或者最大元素进行划分，划分的一侧总是没有元素。
最好情况下划分的结果总是平均划分为对等的两侧
function quicksort(A,p,r){
if(p<r){
var q=partion(A,p,r)
}
if(p<q-1){
quicksort(A,p,q-1);
}
if(q+1<r){
quicksort(A,q+1,r);
}
console.log(A);
}
function partion(A,p,r){
var x=A[r];
var i=p-1;
for(var j=p;j<r;j++){
if(A[j]<=x){
i=i+1;
[A[i],A[j]]=[A[j],A[i]];
}
}
[A[i+1],A[r]]=[A[r],A[i+1]];
return i+1;
}
//快排实现寻找数组第几大元素
function quicksortfind(A,low,high,th){
var lows=low;
var highs=high;
var number=A[low];
while(low<high){
while(A[high]>=number&&low<high){
high--;
}
if(low<high){
A[low]=A[high];
}
while(A[low]<=number&&low<high){
low++;
}
if(low<high){
A[high]=A[low];
}
}
A[low]=number;
if(th==low){
return A[low];
}
else if(th>low){
return quicksortfind(A,low+1,highs,th);
}
else{
return quicksortfind(A,lows,low-1,th);
}
}
7．堆排序
计算时间为nlogn 原地排序 不稳定
MAX-HEAPIFY调整堆使其满足大顶堆的性质
BUILD-MAX-HEAP基于无序数组构建大顶堆
//堆排序
var len;
function maxheap(A,i){
var l=A[2*i+1];
var r=A[2*i+2];
var largest=i;
if(2*i+1<len && l>A[i]){
largest=2*i+1;
}
if(2*i+2<len && r>A[largest]){
largest=2*i+2;
}
if(largest!=i){
[A[largest],A[i]]=[A[i],A[largest]];
maxheap(A,largest);
}
}
function buildheap(A){
for(var i=Math.floor(len/2);i>=0;i--){
maxheap(A,i);
console.log(A);
}
}
function heapsort(A){
len=A.length;
buildheap(A);
for(var i=len;i>1;i--){
[A[0],A[i-1]]=[A[i-1],A[0]];
len--;
maxheap(A,0);
}
console.log(A);
}
8．基于堆实现的优先级队列
9．线性时间排序
计数排序：不做元素间的比较
输入:A[1…n],其中A[j]是{1,2,…,k}
输出;B[1..n],有序
辅助存储空间:C[1..k] 计算时间是k+n 是稳定的排序方法
//计数排序
function countsort(A,k){
varc=[];
for(vari=0;i<=k;i++){
c[i]=0;
console.log(c);
}
for(varj=0;j
varq=A[j];
c[q]=c[q]+1;
console.log(c);
}
for(vari=1;i<=k;i++){
c[i]+=c[i-1];
console.log(c);
}
varB=[];
for(varm=A.length-1;m>=0;m--){
varr=A[m];
vard=c[r];
B[d-1]=r;
c[r]=c[r]-1;
}
console.log(B);
returnB;
}
10．基数排序
一位一位地排序
正确思想：首先按照最低位排序，并且需使用稳定的辅助排序算法。
11．桶排序
假设所有输入由一个随机过程产生，且输入元素在[0,1）上均匀分布。
（1）为每个关键字值分配一个桶 即将A[i]插入到B[A[i]]中
（2）利用插入排序算法将B[i]排序
（3）将B[0],B[1],…,B[n-1]中的元素按顺序拼接在一起。
12.排序算法小结
排序算法 最坏情况 最好情况 平均 应用场合 原地排序 稳定性
插入排序 n*n n n*n n<50时 原地排序 稳定
冒泡排序 n*n n n*n n<50时 原地排序 稳定
归并排序 nlogn nlogn nlogn 需要辅助存储空间，适用于外部排序 不是原地排序 稳定
堆排序 nlogn nlogn nlogn 适用于实时应用 原地排序 不稳定
快排 n*n nlogn nlogn 实用的通用排序算法 原地排序 不稳定
计数排序 k+n k+n k+n 固定小区间内的输入，需要辅助存储空间 不是原地排序 稳定
基数排序 d(k+n) d(k+n) d(k+n) 固定范围内的输入，需要辅助存储空间 不是原地排序 稳定
桶排序 n n n 均匀分布 不是原地排序 稳定
