直接插入排序

基本思想：在要排序的一组数，假设前面（n-1）[n>=2]个数已经是排好顺序的，先要把第n个数插入到前面的有序数，使得这n个数也是排好顺序的。如此反复循环，知道全部排好顺序。

// 直接插入排序
Array.prototype.straightInsertionSort = function() {
    for (var i = 1; i < this.length; i++) {
        if (this[i] < this[i - 1]) {
            var temp = this[i];
            for (j = i - 1; j >= 0 && this[j] > temp; j--) {
                this[j + 1] = this[j];
            }
            this[j + 1] = temp;
        }
    }
    return this;
}
// 查看输出结果
console.info("[57,68,59,52,47,38,61,53]直接插入排序结果 ：" + [57, 68, 59, 52, 47, 38, 61, 53].straightInsertionSort());

希尔排序

基本思想：算法先将要排序的一组数按某个增量d（n/2，n为要排序的个数）分成若干组，每组中记录的下标相差d。对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。

// 希尔排序
Array.prototype.shallSort = function() {
    for (var fraction = Math.floor(this.length / 2); fraction > 0; fraction = Math.floor(fraction / 2)) {
        for (var i = fraction; i < this.length; i++) {
            for (var j = i - fraction; j >= 0 && this[j] > this[fraction + j]; j -= fraction) {
                var temp = this[j];
                this[j] = this[fraction + j];
                this[fraction + j] = temp;
            }
        }
    }
    return this;
}
// 查看输出结果
console.info("[57,68,59,52,47,38,61,53]希尔排序结果 　　：" + [57, 68, 59, 52, 47, 38, 61, 53].shallSort());

简单选择排序

基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换，然后剩下的数当中找出最小的与第二个位置的数交换，如此寻哈un到倒数第二个数和最后一个数为止。

// 简单选择排序
Array.prototype.selectSort = function() {
    var min, temp;
    for (var i = 0; i < this.length; i++) {
        min = i;
        for (var j = i + 1; j < this.length; j++) {
            if (this[min] > this[j])
                min = j;
        }
        if (min != i) {
            temp = this[i];
            this[i] = this[min];
            this[min] = temp;
        }
    }
    return this;
};
// 查看输出结果
console.info("[57,68,59,52,47,38,61,53]简单选择排序结果 ：" + [57, 68, 59, 52, 47, 38, 61, 53].selectSort());

堆排序

基本思想：堆排序是一种树形选择排序，是对直接选择排序的有效改进。

具有n个元素的序列（h1,h2,…,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,…,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

// 堆排序
//以下是针对堆进行调整
Array.prototype.buildMaxHeap = function() {
    for (var i = Math.floor(this.length / 2) - 1; i >= 0; i--) {
        this.heapAdjust(i, this.length);
    }
};
Array.prototype.swap = function(i, j) {
    var tmp = this[i];
    this[i] = this[j];
    this[j] = tmp;
};
Array.prototype.heapSort = function() {
    this.buildMaxHeap();
    for (var i = this.length - 1; i > 0; i--) {
        this.swap(0, i);
        this.heapAdjust(0, i);
    }
    return this;
};
Array.prototype.heapAdjust = function(i, j) {
    var largest = i;
    var left = 2 * i + 1;
    var right = 2 * i + 2;
    if (left < j && this[largest] < this[left]) {
        largest = left;
    }
    if (right < j && this[largest] < this[right]) {
        largest = right;
    }
    if (largest != i) {
        this.swap(i, largest);
        this.heapAdjust(largest, j);
    }
};
// 查看输出结果
console.info("[57,68,59,52,47,38,61,53]堆排序结果　　　 ：" + [57, 68, 59, 52, 47, 38, 61, 53].heapSort());

冒泡排序

基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

// 冒泡排序
Array.prototype.bubbleSort = function() {
    for (var i = 0; i < this.length; i++) {
        for (var j = this.length; j > 0; j--) {
            if (this[j] < this[j - 1]) {
                var temp = this[j - 1];
                this[j - 1] = this[j];
                this[j] = temp;
            }
        }
    }
    return this;
}
// 查看输出结果
console.info("[57,68,59,52,47,38,61,53]冒泡排序结果　　 ：" + [57, 68, 59, 52, 47, 38, 61, 53].bubbleSort());

快速排序

基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

// 快速排序
function quickSort(array) {
    function sort(prev, numsize) {
        var nonius = prev;
        var j = numsize - 1;
        var flag = array[prev];
        if ((numsize - prev) > 1) {
            while (nonius < j) {
                for (; nonius < j; j--) {
                    if (array[j] < flag) {
                        array[nonius++] = array[j];　
                        break;
                    };
                }
                for (; nonius < j; nonius++) {
                    if (array[nonius] > flag) {
                        array[j--] = array[nonius];
                        break;
                    }
                }
            }
            array[nonius] = flag;
            sort(0, nonius);
            sort(nonius + 1, numsize);
        }
    }
    sort(0, array.length);
    return array;
}
// 查看输出结果
console.info("[57,68,59,52,47,38,61,53]快速排序结果　　 ：" + quickSort([57, 68, 59, 52, 47, 38, 61, 53]));

归并排序

基本排序：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

// 归并排序
function　 merge(left, right) {
    var　 result = [];
    while (left.length > 0 && right.length > 0) {
        if (left[0] < right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    return　 result.concat(left).concat(right);
}
function　 mergeSort(a) {
    if (a.length == 1) {
        return　 a;
    }
    var　 middle = Math.floor(a.length / 2),
        left = a.slice(0, middle),
        right = a.slice(middle);
    return　 merge(mergeSort(left), mergeSort(right));
}
// 查看输出结果
console.info("[57,68,59,52,47,38,61,53]归并排序结果　　 ：" + mergeSort([57, 68, 59, 52, 47, 38, 61, 53]));

基数排序

基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

现在我们分析一下8种排序算法的稳定性。

直接插入排序：一般插入排序，比较是从有序序列的最后一个元素开始，如果比它大则直接插入在其后面，否则一直往前比。如果找到一个和插入元素相等的，那么就插入到这个相等元素的后面。插入排序是稳定的。
希尔排序：希尔排序是按照不同步长对元素进行插入排序，一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，稳定性就会被破坏，所以希尔排序不稳定。
简单选择排序：在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。光说可能有点模糊，来看个小实例：858410，第一遍扫描，第1个元素8会和4交换，那么原序列中2个8的相对前后顺序和原序列不一致了，所以选择排序不稳定。
堆排序：堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, …这些父节点选择元素时，有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，所以堆排序并不稳定。
冒泡排序：由前面的内容可知，冒泡排序是相邻的两个元素比较，交换也发生在这两个元素之间，如果两个元素相等，不用交换。所以冒泡排序稳定。
快速排序：在中枢元素和序列中一个元素交换的时候，很有可能把前面的元素的稳定性打乱。还是看一个小实例：6 4 4 5 4 7 8 9，第一趟排序，中枢元素6和第三个4交换就会把元素4的原序列破坏，所以快速排序不稳定。
归并排序：在分解的子列中，有1个或2个元素时，1个元素不会交换，2个元素如果大小相等也不会交换。在序列合并的过程中，如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，所以，归并排序也是稳定的。
基数排序：是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。