几种常见的排序算法

整理复习了一下几种常见的排序算法，参考资料为维基百科。简单分析了它们的基本原理，没有涉及到复杂度的计算，仅仅以结果的形式记录，在每种排序算法的最后都提供了 JavaScript 的实现代码。

1. 冒泡排序（Bubble Sort）

重复地走访要排序的序列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访序列的工作是重复地进行直到不再需要交换，序列排序完成。

时间复杂度为O(n^2)。

Array.prototype.bubbleSort = function() {
    var i, j, temp;
    for (i = 0; i < this.length - 1; i++) {
        for (j = 0; j < this.length - i - 1; j++) {
            if (this[j] > this[j + 1]) {
                temp = this[j + 1];
                this[j + 1] = this[j];
                this[j] = temp;
            }
        }
    }
};

2. 插入排序 (Insertion Sort)

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置插入。

具体细节如图：

时间复杂度为O(n^2)。

Array.prototype.insertionSort = function() {
    var i, j, temp;
    for (i = 0; i < this.length - 1; i++) {
        for (j = i + 1; j > 0; j--) {
            if (this[j] > this[j - 1]) break;

            temp = this[j - 1];
            this[j - 1] = this[j];
            this[j] = temp;
        }
    }
};

3. 选择排序 (Selection Sort)

首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小(大)元素，放到已排序序列的末尾，循环此过程，直到所有元素排列完毕。

具体细节如图：

时间复杂度为O(n^2)。

交换次数比冒泡排序较少，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

Array.prototype.selectionSort = function() {
    var i, j, min;
    for (i = 0; i < this.length - 1; i++) {
        min = this[i];
        for (j = i + 1; j < this.length; j++) {
            if (this[j] < min) {
                min = this[j];
                this[j] = this[i];
                this[i] = min;
            }
        }
    }
};

4. 快速排序(Quick Sort)

快速排序使用分治法，把一个序列分为两个子序列来排序。

步骤可分为：

1. 从序列中挑出一个元素作为基准(pivot)
2. 重新排序序列，所有比基准值小的元素摆放在基准前面，比基准大的元素摆在基准后面
3. 递归地把小于基准值元素的子序列和大于基准值元素的子数列排序

最优时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)

基础版本：

Array.prototype.quickSort = function() {
    var len = this.length;
    if (len <= 1) return this.slice(0);

    var left = [];
    var right = [];
    var mid = [this[0]];
    for (var i = 1; i < len; i++) {
        if (this[i] < mid[0]) {
        	left.push(this[i]);
        } else {
        	right.push(this[i]);
        }
    }

    return left.quickSort().concat(mid.concat(right.quickSort()));
};

上面简单版本的缺点是，它需要Ω(n)的额外存储空间，也就跟归并排序一样不好。额外需要的内存空间配置，在实际上的实现，也会极度影响速度和缓存的性能。有一个比较复杂使用原地（in-place）分区算法的版本，且在好的基准选择上，平均可以达到O(log n)空间的使用复杂度。(维基百科)

原地 (In-place) 版本：

Array.prototype.quickSortIP = function() {
    function swap(array, i, k) {
        var temp = array[i];
        array[i] = array[k];
        array[k] = temp;
    }

    function partition(array, left, right) {
        var storeIndex = left;
        var pivot = array[right]; // 选择最右边的元素作为基准元素

        for (var i = left; i < right; i++) {
            if (array[i] < pivot) {
                swap(array, i, storeIndex);
                storeIndex++;
            }
        }

        swap(array, right, storeIndex); // 将基准还原到正确位置
        return storeIndex;
    }

    function sort(array, left, right) {
        if (left > right) return;

        var storeIndex = partition(array, left, right);
        sort(array, left, storeIndex - 1);
        sort(array, storeIndex + 1, right);
    }

    sort(this, 0, this.length - 1);
};

5. 希尔排序 (Shell Sort)

希尔排序是插入排序一种更高效的改进版本，基于以下插入排序的两种特点进行改进：

• 插入排序在对几乎已经排好序的数据操作时，效率高，可以达到线性排序的效率
• 插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

算法思路：

1. 先取一个正整数 d1 (d1 < n)，把全部记录分成 d1 个组，所有距离为 d1 倍数的记录看成一组，然后在各组内进行插入排序
2. 取正整数 d2 (d2 < d1)
3. 重复上述操作，直到 di = 1 (i >= 1)，即所有记录成为一个组，最后对这个组进行插入排序即可

最优时间复杂度为O(n log2 n)，最坏时间复杂度为O(n^2)。

// 此处 d1 选取了 n/2
Array.prototype.shellSort = function() {
    function swap(array, i, k) {
        var temp = array[i];
        array[i] = array[k];
        array[k] = temp;
    }

    var len = this.length,
        gap = Math.floor(len / 2);

    while (gap > 0) {
        for (var i = gap; i < len; i++) {
            for (var j = i; j > 0; j -= gap) {
                if (this[j - gap] > this[j]) {
                    swap(this, j - gap, j);
                } else {
                    break;
                }
            }
        }

        gap = Math.floor(gap / 2);
    }
};