首页 > 代码库 > javascript常用排序算法实现

javascript常用排序算法实现

毕业后,由于工作中很少需要自已去写一些排序,所以那些排序算法都忘得差不多了,不过排序是最基础的算法,还是不能落下啦,于是找了一些资料,然后用Javascript实现了一些常用的算法,具体代码如下:

<!DOCTYPE html>
<html>
<head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    <title>javascript常用排序算法实现</title>
    <script type="text/javascript" src="js/jquery-1.8.3.min.js"></script>
</head>
<body>

<script>

/* 将以下序列从大到小进行排序 */
var arr = [54,23,12,56,433,112,995,226,331,43,64,87,43,24,57,68,45,33,77,98,23,432,432,654,345,23,123,765,432,889];

/* 插入排序  */
function  insertionSort(arr) {
    for( var i = 1; i < arr.length ; i++ ) {
        for( var j = i ; j >= 0 ; j-- ) {
            if(arr[j] > arr[j - 1]) {
                arr[j] = [ arr[j -1] , arr[j - 1] = arr[j] ][0]; // 交换变量
            }
        }
    }
    return arr; 
}
//console.log(insertionSort(arr));

/* 
 *快速排序 
 *
 * 该方法的基本思想是:
 * 1.先从数列中取出一个数作为基准数。
 * 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
 * 3.再对左右区间重复第二步,直到各区间只有一个数。
 * 参考 :http://blog.csdn.net/morewindows/article/details/6684558
 */

function quickSort(arr){
    (function(l,r){
        if(l < r ){
            var from = l,
                to = r,
                x = arr[from];//在第一个地方挖一个坑
        
            while( from < to  ) {
                
                //从右向左查找小于x的数来填 arr[from]
                while( x >= arr[to] && from < to  ) { 
                    to --;
                }
                if(from < to){
                    arr[from] = arr[to]; //将arr[to]中的数填到arr[from],这里arr[to]形成了一个新坑
                    from ++;             
                }
                
                //从左向右查找小于x的数来填 arr[to]
                while( x <= arr[from]  && from < to) {
                    from ++;
                }
                if(from < to){
                    arr[to] = arr[from]; //将aar[from]中的数填到arr[to],这里arr[from]形成了一个新坑
                    to --;
                }    
            }

            arr[from] = x;

            arguments.callee(l , from - 1 ) ;
            arguments.callee(from + 1 , r) ;
        }
    }(0,arr.length-1));    
    return arr;
}

//console.log(quickSort(arr));


/* 冒泡排序 */
function bubleSort(arr){

    for(var i = 0 ; i < arr.length-1 ; i ++ ) {
        for(var j = 0 ; j < arr.length - i -1 ; j++ ) {
            if( arr[j] < arr[j+1] ) {
                arr[j] = [arr[j+1],arr[j+1]=arr[j]][0];
            }
        }
    }

    return arr;
}

//console.log(bubleSort(arr));

/* 堆排序 */
function heapSort(arr){
    
    var makeMinHeap = function(a , len){

        for(var i = len -1 ; i >= 0 ; i --) {
            var parentIdx = Math.floor((i-1)/2);
            if( parentIdx >= 0 && a[i] < a[parentIdx] ){
                a[i] = [ a[parentIdx] , a[parentIdx] = a[i] ][0];
            }
        }
        return a;
    }

    for( var i = arr.length -1 ; i > 0 ; i -- ){
        arr = makeMinHeap(arr,i+1);
        arr[0] = [arr[i],arr[i] = arr[0]][0];
    }

    return arr;
}

//console.log(heapSort(arr));

</script>

</body>
</html>