几个常用的检索排序算法的JavaScript实现

近期工作需要，开始复习相关的检索排序算法。对常用的几个算法，自行进行了JavaScript实现：

• 顺序查找

     最朴素的查询

/**
@data  目标元素所在的数组
@target  目标查询元素
@return  目标查询元素所在的下标
*/
function sequenceSearch(data,target){
    var resultIndex=-1;
    for(var i=0;i<data.length;i++){
        if(target==data[i]){
             resultIndex=i;
             break;
        }
    }
    return resultIndex;
} 

• 折半查找

     注意，适合有序数组中的查找

/**
@data  目标元素所在的数组
@target  目标查询元素
@return  目标查询元素所在的下标
*/
function halfSearch(data,target){
    var resultIndex=-1;
    //将有序数组分为两部分，使用start,middle与end
    var start=0,end=data.length,middle=-1;
    while(start<end){
        middle=Math.floor((start+end)/2);
        if(target>data[middle]){
            start=middle+1;
        }else if(target<data[middle]){
            end=middle-1;
        }else{
           resultIndex=middle;
           break;
        }
    }
    return resultIndex;
 } 

•  顺序插入排序

    注意：核心是由前往后，在逐渐排好的前段部分逆向插入元素

/**
@data  目标排序数组
*/
function insertSort(data){
    for(var i=1;i<data.length;i++){
       var temp=data[i];
       if(data[i-1]>temp){
           //每次在已经排好序的部分进行插入
           for(var j=i-1;j>=0;j--){
                if(data[j]>temp){
                    //向后进行移位，以便当前目标元素可以插入
                    data[j+1]=data[j];
                    data[j]=temp;
                }
           }
       }
    }
 }

•  冒泡排序

    注意：逐次将大数向后移，第i个元素需要比较n-i-1次，嵌套循环实现

/**
@data  目标排序数组
*/
 

function bubbleSort(data){
    for(var i=0;i<data.length;i++){
        //大数自动向数组大下标处移动
        for(var j=0;j<data.length-i;j++){
             if(data[j]>data[j+1]){
                 var temp=data[j+1];
                 data[j+1]=data[j];
                 data[j]=temp;
             }
        }
    }
 }

•  快速排序

    注意，使用分段，结合递归

/**
@data  目标排序数组
@start  分段开始
@end   分段结束
 */
function quickSort(data,start,end){
    if(start<end){
         var i=quickSortPartation(data,start,end);
         //递归处理每一段
         quickSort(data,start,i-1);
         quickSort(data,i+1,end);
    }
} 

//进行一次快排
function quickSortPartation(data,start,end){
     //定义第一个元素为快排标志位
     var key=data[start];
     while(start<end){
        while(start<end  && data[end]>=key){
             end--;
        }
        //当小于标志位的元素向前置换
        if(start<end){
             data[start]=data[end];
             start++;
        }
        while(start<end && data[start]<key){
             start++;
        }
        if(start<end){
            data[end]=data[start];
            end--;
        }
     }
     data[start]=key;
     return start;
}

 

评论

1 楼 lliiqiang 2014-05-05  

首先要有条件，算法只是提升系统而已。如果小范围变化基本可以尝试出错也无关紧要