Sort Algorithm—MIT算法导论

插入排序

image.png

/**
 * Created by 编程只服JAVA on 2017.07.13.
 */
var arr = [1,43,23,56,12];

function inSertSort(Array)
{
    for(var i = 1; i < Array.length; ++i)
    {
        //插入的起手位置
        var key = arr[i];
        //已排好序的部分Array[0, j]
        var j = i - 1;

        //如果插入的起手位置 < 前面排好序的部分
        while (j > -1 && Array[j] > key)
        {
            Array[j + 1] = Array[j];
            --j;
        }

        //找到合适的插入位置，因为j已经跑到了前一个位置，因此需要j + 1
        Array[j + 1] = key;
    }
}

inSertSort(arr);
console.info(arr);

冒泡排序

image.png

/**
 * Created by 编程只服JAVA on 2017.07.13.
 */
var arr = [1,43,23,56,12,12];

function bubbleSort(Array)
{
    //for Array[0, high - 1]
    for(var i = 0; i < Array.length - 1; ++i)
    {

        //优化
        var flag = true;
        //for Array[high, i + 1] down to, 因为下面Array[j] < Array[j - 1]，所以j >= i + 1;
        //将小的元素向前冒
        for(var j = Array.length - 1; j >= i + 1; --j)
        {
            if (Array[j] < Array[j - 1])
            {
                var temp = Array[j];
                Array[j] = Array[j - 1];
                Array[j - 1] = temp;
                flag = false;
            }
        }

        if (flag) break;
    }
}

bubbleSort(arr);
console.info(arr);

选择排序

/**
 * Created by 编程只服JAVA on 2017.07.13.
 */
var arr = [1,43,23,56,12,12];

function selectSort(Array)
{
    // 临时变量，用于交换
    var temp = 0;
    var minIndex = 0;

    // 要注意一点，当要排序 N 个数，已经经过 N-1 次遍历后，已经是有序数列
    for(var i = 0; i < Array.length - 1; ++i)
    {
        // 用来保存最小值得索引
        minIndex = i;

        // 寻找第i个小的数值
        for(var j = i + 1; j < Array.length; ++j)
        {
            if (Array[j] < Array[minIndex])
            {
                minIndex = j;
            }
        }

        //可以加一个判断minIndex != i,或许可以提升一点效率，不加也可以
        // 将找到的第i个小的数值放在第i个位置上
        if (minIndex != i)
        {
            temp = Array[minIndex];
            Array[minIndex] = Array[i];
            Array[i] = temp;
        }
    }
}

selectSort(arr);
console.info(arr);