[アルゴリズム]並べ替え

基本的な並べ替えアルゴリズムは大きく三つの種類に分けられ、並べ替え、並べ替え、並べ替えを選択します.以下は三つの並べ替えアルゴリズムのいくつかのjavascriptが整理を実現します.
並べ替えを選択
並べ替えを簡単に選択

//     

function selection_sort(arr)

{

    var n = arr.length;

    var i, j, min, t;

    for( i =0; i < n -1; i ++)

    {

        min = i; 

        //      

        for( j = i +1; j < n; j ++)

            if( arr[min] > arr[j])min = j; 

        //   

        if( min != i)

        {

            t = arr[min];

            arr[min] = arr[i];

            arr[i] = t;

        }

    }

    return arr;

}

積み上げ順序

//    （      ）

function heap_sort(arr)

{  

    // arr        ，i            ，n      

    //      ：    arr     （              ，   ）

    function heap_adjust(arr, i, n)

    {

        var child;

        var t;

        for (t = arr[i]; 2 * i + 1 < n; i = child)

        {

            //       =2*（     ）+ 1

            child = 2 * i + 1;

            //            

            if ( child < n-1 && arr[child + 1] > arr[child])

                ++child;

            //                           ，       ，            

            if (t < arr[child])

            {

                arr[i] = arr[child];

                arr[child]= t;

            }

            else

            //       

                 break;

        }

    }

    var n = arr.length;

    var t;

    // n/2-1          

    //                             

    for (var i = n / 2 - 1; i >= 0; --i)

        heap_adjust(arr, i, n);

    //                 ，                 

    for (var i = n - 1; i > 0; --i)

    {

        //                   ，

        //                              

        t = arr[i];

        arr[i] = arr[0];

        arr[0] = t;

        

        //                    ，           ，     ，         。

        heap_adjust(arr, 0, i);

    }

    return arr;

}

並べ替えの挿入
並べ替えの直接挿入

//         

function insertion_sort(arr) 

{

    var n = arr.length;

    var t, j;

    //             ，arr[0]         

    for(var i=1;i<n;i++) 

    {

        //   arr[i] (t           )

        t=arr[i];

        j=i-1;

        //  t            ，  t      

        while (j>=0 && arr[j]>t)

        { 

            arr[j+1]=arr[j];  

            j--; 

        } 

        arr[j+1]=t; 

    } 

    return arr;

} 

ヒルの並べ替え

//     （      ）

function shell_sort(arr)

{

    var n = arr.length;

    var fraction,i,j,t;

    //    1/2      

    for(fraction=Math.floor(n/2); fraction>0; fraction=Math.floor(fraction/2)) {

        for(i = fraction; i<n; i++ ) {

            for(j = i-fraction; j>=0 && arr[j]>arr[fraction+j]; j-=fraction ) {

                t = arr[j];

                arr[j] = arr[fraction+j];

                arr[fraction+j] = t;

            }

        }

    }

    return arr;

}

並べ替えの統合

//     (            )

function merge_sort(arr, s, e, b){

    s = s || 0; 

    e = e || arr.length - 1;

    b = b || new Array(arr.length);

    if (s >= e)

        return;

    var m = (s + e) >> 1;

    merge_sort(arr, s, m, b);

    merge_sort(arr, m + 1, e, b);

    for (var i = s, j = s, k = m + 1; i <= e; ++i)

        b[i] = arr[(k > e || j <= m && arr[j] < arr[k]) ? j++ : k++];

    for (var i = s; i <= e; ++i)

        arr[i] = b[i];

}

並べ替え
泡の並べ替え

//     (      )

function bubble_sort(arr){

    var t,i,j;

    //     n-1 

    for(i=0;i<arr.length-1;i++){

        //       arr[i..n]      

        for(j=0;j<arr.length-i-1;j++){

                if(arr[j]>arr[j+1]){

                    //  

                    t=arr[j];

                    arr[j]=arr[j+1];

                    arr[j+1]=t;

                }

            }

        }

    return arr;

}

クイックソート

//         (      )

function quick_sort(arr, l, r)

{

    var i,j,x;

    l = l || 0;

    r = r || arr.length-1;

    if (l < r)

    {

        i = l, j = r, x = arr[l];

        while (i < j)

        {

            //           x  

            while(i < j && arr[j] >= x) 

                j--; 

            if(i < j)

                arr[i++] = arr[j];

            //             x  

            while(i < j && arr[i] < x) 

                i++; 

            if(i < j)

                arr[j--] = arr[i];

        }

        arr[i] = x;

        quick_sort(arr, l, i - 1); //     

        quick_sort(arr, i + 1, r);

    }

    return arr;

}

//         (      )

function stack_quick_sort(arr) {

    var stack = [0, arr.length - 1];

    var i,index,e,t;

    while (stack.length > 0){

        e = stack.pop(), s = stack.pop();  

        if (s >= e)

            continue;

        t = arr[(s + e) >> 1];

        arr[(s + e) >> 1] = arr[e];

        arr[e] = t;

        index = s - 1;

        for (i = s; i <= e; ++i){

            if (arr[i] <= arr[e]){

                ++index;

                t = arr[i];

                arr[i] = arr[index];

                arr[index] = t;

            }

        }

        stack.push(s, index - 1, index + 1, e);

    }

    return arr;

}