排序

发表于: 2017-01-05分类于:算法

选择排序

找到最小的元素和第一位交换,从第二位开始在最小的元素和第二位交换,如此往复。

特点:

  • 运行时间和输入无关
  • 数据移动最少

插入排序

不断和前一个元素比较,如果前一个元素大于当前元素,则交换。就像整理扑克牌一样,第一张牌不动,第二张则插在第一张的左或右边,而第三张则插入在前两张的合适位置。

特点:

  • 插入排序对下列数组排序效果很好 :
    • 数组中只有几个元素的位置不正确
    • 每个元素都离自己正确的位置不远
  • 当倒置数很少的时候,性能很好

希尔排序

对于大数组,插入排序工作的并不好,因为它只会交换相邻元素,元素只能一点一点地搬动到另一端。而希尔排序,通过调整跨度,可以将大数组快速地调整为局部有序的数组,而后再采用插入排序完成最终排序。

shell

function shell_sort(a){
    let h = 1;
    let length = a.length;
    while(h < length / 3){
        h = h * 3 + 1;
    }

    while(h >= 1){
        for(let i=h;i<length;i++){
            // 将 a[i] 插入到 a[i-h],  a[i-2*h],  a[i-3*h] ... 的合适位置 
            for(let j=i;j>=h && a[j] < a[j-h];j -= h){
                let num = a[j];
                a[j] = a[j-h];
                a[j-h] = num;
            }
        }
        h = Math.floor(h/3)
    }
}

归并排序

归并排序的思路是将问题两个有序数组的合并,合并两个有序数组是线性复杂度的。

自顶向下的归并排序

自顶向下的归并排序采用递归的写法,可以想象不断将数组划分为原来的一半,递归到最深层有两个元素进行比较,这时候就相当于是两个有序数组了,可将他们归并为一个有序数组。而后递归退回一层将两个有序数组在归并。这样整个数组就进行排序。

function merge_sort(a, lo, hi) {
    if (hi <= lo) {
        return;
    }
    let mid = Math.floor(lo + (hi - lo) / 2);
    merge_sort(a, lo, mid);
    merge_sort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
}

merge 算法,需要一个额外的空间来保存两个 a 数组中的内容。

function merge( a,  lo,  mid,  hi) {
    let i = lo, j = mid + 1;

    for (let k = lo; k <= hi; k++) {
        aux[k] = a[k];
    }

    for (let k = lo; k <= hi; k++) {
        if (i > mid) {
            a[k] = aux[j++];
        }
        else if (j > hi) {
            a[k] = aux[i++];
        }
        else if (aux[i] > aux[j]) {
            a[k] = aux[j++];
        }
        else {
            a[k] = aux[i++];
        }
    }
}

自顶向下的归并排序需要递归,其本质是将两个有序子数组合并为一个有序数组。为了得到有序子数组,纯粹的递归归并,是通过递归深入到最底层,进行两个元素的比较。这才得到了一个有两个元素的有序子数组,而后有四个元素的有序子数组……。

这样递归深度是 log2(N) 层,为了减少递归深度,可以在子数组长度较少时可以使用插入排序得到有序的子数组。这样可以减少递归的深度。

自底向上的归并排序

模仿递归的归并排序的效果,可采用迭代完成相同的效果。第一次迭代以 2 为跨度,将两个元素调整为有序,而后以 4 为跨度,将其中的两个有 2 个元素的有序数组合并,而后以 8 为跨度……

function merge_sort(a) {
    let N = a.length;
    for (let sz = 1; sz < N; sz += sz) {
        for (let lo = 0; lo < N - sz; lo += sz + sz) {
            merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
        }
    }
}

快速排序

数组中一个元素左边元素均小于它,右边元素均大于它,那么将该元素两边的子数组分别排序,整个数组也就有序了。快速排序的思路是在数组中取第一个数 a[lo],假如值是 v ,将它放到合适的位置,以满足上面描述的那种场景。

为了满足这个场景,需要调整数组中元素的位置。用 i、j 两个指针从数组的左右两端,找到比 v 大的数,和比 v 小的数,然后交换两者,而后 i 继续往后走,j 往前走,继续搜寻,最终 i 和 j 会碰面,或者 j 走前 i 前面。此时 j 所指的要么是等于 v 的,要么是小于 v 的,于是交换 j 和 lo。 j 则将整个数组分为了两部分,j 左边全小于等于 v ,j 右边则全 大于等于 v。而后对这两部分继续进行快速排序。

function quick_sort(a){
    function _quick_sort(a, lo, hi){
        // 可以在这里改进,对小数组使用插入排序
        // M 可取 5~15 之间,因系统而异
        // if(hi <= lo + M){
        //     insert_sort(a, lo, hi);
        //     return;
        // }

        if(hi <= lo) return;

        let j = partition(a, lo, hi);
        _quick_sort(a, lo, j - 1);
        _quick_sort(a, j+1,hi);
    }

    function exch(a, i ,j){
        let t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    function partition(a, lo, hi){
        let i = lo, j = hi + 1;

        let v = a[lo];        

        while(true){
            // 防止 i 越界
            while(v > a[++i] && i < hi);
            while(v < a[--j]);
            if(i>=j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }

    // 将数组打乱,避免出现最坏的情况
    // 第一次用最小的元素切,第二次用次最下的元素切……
    shuffle(a);
    _quick_sort(a, 0, a.length - 1);
}

改进方法:

对于小数组切换到插入排序,因为对于小数组快速排序比插入排序慢。

如果数组中有大量重复元素,可以将数组分为三部分,小于 v 、等于 v、 大于 v。

堆排序

堆排序是利用二叉堆的特性,首先用待排序数组构成二叉堆,而后不断将堆中最大元素放到数组的后面,同时减小堆得大小,当堆为空时,排序完成。

function heap_sort(a){

    // 完成堆的下沉
    function sink(a, parent_index, N){
        // N 为堆的最大索引
        // parent_index 为父节点索引,即要下沉的元素的索引

        while(parent_index * 2 <= N){
            // 左孩子的索引
            let child_index = 2 * parent_index;
        
            // 如果右孩子大于左孩子,就和右孩子交换
            if(child_index < N && a[child_index] < a[child_index + 1]){
                // 改为右孩子的索引
                child_index += 1;
            }
            // 如果父比子大,就不用下沉了
            if(a[parent_index] > a[child_index]){
                break;
            }
            // 否则,下沉
            exch(a, parent_index, child_index);
            parent_index = child_index;
        }
    }
    // 交换元素
    function exch(a, i ,j){
        let t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    // 以下是堆排序算法部分

    // 因为用数组构成二叉堆是索引是从 1 开始的,即 a[0] 不参与排序
    // 所以第一步先把数组中最下的元素挑出来放到第 0 位
    let min_index = 0;
    let min = a[0];
    for(let i=1;i<a.length;i++){
        if(a[i] < min){
            min = a[i];
            min_index = i;
        }
    }
    exch(a, 0, min_index);

    let N = a.length - 1;
    // 构建堆
    // 在构建堆的时候,先构造只有一层的堆,也就是两个孩子都是叶子节点
    // 而后,两个孩子都是二叉堆了,这个时候就能构建更大的二叉堆
    // 所以这里是从后往前迭代的
    for(let parent_index = Math.floor(N/2); parent_index >= 1; parent_index--){
        sink(a, parent_index, N);
    }


    // 上面的 for 循环构建了二叉堆
    // 也就是 a[1] 是最大元素,将最大元素和末尾交换
    // 交换后,a[1] 这样 a[1] 又是余下的最大的元素,
    // 而后将 a[1] 和倒数第二个元素交换,重复以上过程
    while(N > 1){
        exch(a, 1, N--);
        sink(a, 1, N);
    }
}