[date: 2019-03-09 21:16] [visits: 5]

排序算法

直接插入排序

直接插入排序的思路是遍历过程中保持被遍历过的元素有序,每遍历到一个新元素时如不能保持已遍历元素有序,则为该新元素寻找合适的插入位置插入以保持遍历元素的有序性,当完成遍历时所有元素均有序。

假设初始列表items = [4, 2, 3, 1, 5],非降序的直接插入排序过程如下:

  1. 初始已遍历内容为[4],从i = 1开始,items[i = 1] = 2,[4] => 插入2 => [2, 4]
  2. items[i = 2] = 3,[2, 4] => 插入3 => [2, 3, 4]
  3. items[i = 3] = 1,[2, 3, 4] => 插入1 => [1, 2, 3, 4]
  4. items[i = 4] = 5,[1, 2, 3, 4] => 插入5 => [1, 2, 3, 4, 5]

代码实现:

function insertSort(items) {
    let i, j, tmp;

    for (i = 1; i < items.length; i++) {
        if (items[i] < items[i - 1]) {
            tmp = items[i];
            items[i] = items[i - 1];

            for (j = i - 1; j >= 0 && items[j] > tmp; j--) {
                items[j + 1] = items[j];
            }

            items[j + 1] = tmp;
        }
    }

    return items;
}

冒泡排序

经典排序算法,可总结成:“两两比较,两两交换”,每一轮比较和交换可以将一个最大或最小元素移动到对应的位置。

假设初始列表items = [4, 2, 3, 1, 5],非降序的冒泡排序过程如下:

  1. [(2, 4), 3, 1, 5] => [2, (3, 4), 1, 5] => [2, 3, (1, 4), 5] => [2, 3, 1, (4, 5)]
  2. [(2, 3), 1, 4, 5] => [2, (1, 3), 4, 5] => [2, 1, (3, 4), 5]
  3. [(1, 2), 3, 4, 5] => [1, (2, 3), 4, 5]
  4. [(1, 2), 3, 4, 5] => [1, 2, 3, 4, 5]

流程里中括号内的小括号是进行比较和交换的元素,整个排序看起来像是目标元素从列表中向上“冒出”的过程,所以被称为冒泡排序。

代码实现:

function bubbleSort(items) {
    let i, j, tmp;

    for (i = 0; i < items.length - 1; i++) {
        for (j = 1; j < items.length - i; j++) {
            if (items[j] < items[j - 1]) {
                tmp = items[j];
                items[j] = items[j - 1];
                items[j - 1] = tmp;
            }
        }
    }

    return items;
}

选择排序

选择排序的思路是在遍历过程中依次挑选出最大、次大、第三大...元素,并将其移动到对应的位置上,当然也可以反过来用挑选最小、次小、第三小...的方式。

假设初始列表items = [4, 2, 3, 1, 5],非降序的选择排序过程如下:

  1. i = 0,找到最小元素的下标为3,交换后:[1, 2, 3, 4, 5]
  2. i = 1,...,[1, 2, 3, 4, 5]
  3. i = 2,...,[1, 2, 3, 4, 5]
  4. i = 3,...,[1, 2, 3, 4, 5]

代码实现:

function selectSort(items) {
    let i, j, tmp;

    for (i = 0; i < items.length - 1; i++) {
        let k = i;
        for (j = i + 1; j < items.length; j++) {
            if (items[k] > items[j]) {
                k = j;
            }
        }

        tmp = items[k];
        items[k] = items[i];
        items[i] = tmp;
    }

    return items;
}

希尔排序

希尔排序是对直接插入排序的一种优化改进,做法是先挑选一个递减的delta序列,随后遍历delta序列时从待排序序列中按步长为delta的方式挑选子序列(共delta个)进行直接插入排序,直到delta = 1进行最后一次排序后,整个序列有序。

假设初始列表items = [4, 2, 6, 3, 1, 5, 8, 7],非降序的希尔排序排序过程如下:

  1. 选择delta序列[3, 2, 1]
  2. delta = 3,对子序列[4, 3, 8]、[2, 1, 7]、[6, 5]分别排序得到[3, 4, 8]、[1, 2, 7]、[5, 6],此时items = [3, 1, 5, 4, 2, 6, 8, 7]
  3. delta = 2,对子序列[3, 5, 2, 8]、[1, 4, 6, 7]分别排序得到[2, 3, 5, 8]、[1, 4, 6, 7],此时items = [2, 1, 3, 4, 5, 6, 8, 7]
  4. delta = 1,对序列[2, 1, 3, 4, 5, 6, 8, 7]排序得到[1, 2, 3, 4, 5, 6, 7, 8]

代码实现:

function shellSort(items) {
    let delta = [];
    let n = items.length;
    do {
        delta.push(n = Math.floor(n / 2));
    } while (n > 1);

    let i, j, k, l, tmp;

    for (i = 0; i < delta.length; i++) {
        j = delta[i];

        for (k = j; k < items.length; k++) {
            if (items[k] < items[k - j]) {
                tmp = items[k];
                for (l = k - j; l >= 0 && tmp < items[l]; l -= j) {
                    items[l + j] = items[l];
                }
                items[l + j] = tmp;
            }
        }
    }

    return items;
}

快速排序

快速排序的思路是先从序列中选择一个元素作为“轴中数”,然后分别将大于轴中数的元素放到右侧,小于的元素放在左侧,接着对左侧和右侧的数再次采用快速排序,快速排序的终止条件是待排序序列长度不大于1。

假设初始列表items = [4, 2, 3, 1, 5],非降序的快速排序过程如下:

  1. [4, 2, 3, 1, 5]:4 => [(1, 2, 3), 4, (5)]
  2. [1, 2, 3]:1、[5]:5 => [1, (2, 3), 4, 5]
  3. [2, 3]:2 => [1, 2, (3), 4, 5]
  4. [3]:3 => [1, 2, 3, 4, 5]

上述过程,中括号接冒号后面的值表示所选的轴中数(序列第一个元素),代码如下:

function quickSort(items) {
    return _sort(items, 0, items.length - 1);

    function _sort(items, low, high) {
        if (low >= high) {
            return items;
        }

        let i = low;
        let j = high;
        let pivot = items[low];

        while (i < j) {
            while (i < j && items[j] >= pivot) j--;
            items[i] = items[j];
            while (i < j && items[i] <= pivot) i++;
            items[j] = items[i];
        }
        items[i] = pivot;

        _sort(items, low, i - 1);
        _sort(items, i + 1, high);

        return items;
    }
}

堆排序

对于长度为n的序列,大根堆的元素满足:Ai >= A2i, 2i+1(2i + 1 \< n),小根堆的元素满足:Ai \<= A2i, 2i+1(2i + 1 \< n)。可将序列转换为一颗完全二叉树,大根堆的约束是所有非叶子结点不小于其左右孩子结点,小根堆则是不大于。

堆排序过程是先将序列调整成大根堆或小根堆,然后取走堆的根元素并用最后面的元素填充到根元素位置,随后反复调整堆符合大(小)根堆的定义以及取走根元素与填充最后元素到根元素位置,直到堆为空。

假设初始列表items = [4, 2, 6, 3, 7, 1, 5],他对应的完全二叉树如下:

        |------4------|
        |             |
    |---2---|     |---6---|
    |       |     |       |
    3       7     1       5

非降序的堆排序过程如下:

  1. 从items[floor(items.length / 2) - 1] = items[2] = 6开始向前调整,使其逐渐成为最大堆
  2. [4, 2, 6, 3, 7, 1, 5] => 6与1、5比较,不需要交换 => [4, 2, 6, 3, 7, 1, 5]
  3. [4, 2, 6, 3, 7, 1, 5] => 2与3、7比较,2与7交换 => [4, 7, 6, 3, 2, 1, 5]
  4. [4, 7, 6, 3, 2, 1, 5] => 4与7、6比较,4与7交换 => [7, 4, 6, 3, 2, 1, 5],每一次交换需要考虑交换后的元素作为根的堆是否满足大根堆定义,不满足则需要继续交换,这里4与7交换后,4作为根的堆左右孩子分别为3、2,故无需调整

经过上面4步后,整个序列已经符合大根堆的定义,其对应的完全二叉树如下:

        |------7------|
        |             |
    |---4---|     |---6---|
    |       |     |       |
    3       2     1       5

接着进行后续步骤:

  1. 取走7,将5放在7的位置,并调整5作为根的堆成为大根堆,[7, 4, 6, 3, 2, 1, 5] => [5, 4, 6, 3, 2, 1]、[7] => [6, 4, 5, 3, 2, 1]、[7]
  2. [6, 4, 5, 3, 2, 1]、[7] => 取走6用1替代 => [1, 4, 5, 3, 2]、[6, 7] => 调整1作为根的堆成为大根堆 => [5, 4, 1, 3, 2]、[6, 7]
  3. [5, 4, 1, 3, 2]、[6, 7] => 取走5用2替代 => [2, 4, 1, 3]、[5, 6, 7] => 调整2作为根的堆成为大根堆 => [4, 3, 1, 2]、[5, 6, 7]
  4. ...与上类似
  5. 最终得到[]、[1, 2, 3, 4, 5, 6, 7]

代码如下:

function heapSort(items) {
    let len = items.length;

    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        _fixHeap(items, i, len - 1);
    }

    for (let i = len - 1; i > 0; i--) {
        let tmp = items[0];
        items[0] = items[i];
        items[i] = tmp;

        _fixHeap(items, 0, i - 1);
    }

    return items;

    function _fixHeap(items, s, m) {
        let tmp = items[s];

        for (let i = 2 * s + 1; i <= m; i = i * 2 + 1) {
            if (i < m && items[i] < items[i + 1]) {
                i++;
            }

            if (tmp >= items[i]) {
                break;
            }

            items[s] = items[i];
            s = i;
        }

        items[s] = tmp;
    }
}

归并排序

归并排序的过程是多次将两个有序序列合并为一个有序序列,直到最后只剩下一个序列。

假设初始列表items = [4, 2, 6, 3, 1, 5, 8, 7],非降序的归并排序排序过程如下(正向描述):

  1. [4, 2, 6, 3, 1, 5, 8, 7] => 8个有序序列两两合并 => [(2, 4), (3, 6), (1, 5), (7, 8)]
  2. [(2, 4), (3, 6), (1, 5), (7, 8)] => 4个有序序列两两合并 => [(2, 3, 4, 6), (1, 5, 7, 8)]
  3. [(2, 3, 4, 6), (1, 5, 7, 8)] => 2个有序序列合并 => [(1, 2, 3, 4, 5, 6, 7, 8)]

代码采用的是递归方式,如下:

function mergeSort(items) {
    if (items.length <= 1) {
        return items;
    }

    let mid = Math.floor(items.length / 2);
    let left = mergeSort(items.slice(0, mid));
    let right = mergeSort(items.slice(mid));

    let result = [];
    let i = 0;
    let j = 0;
    while (i < left.length || j < right.length) {
        if (i === left.length) {
            result.push(right[j++]);
            continue;
        }
        if (j === right.length) {
            result.push(left[i++]);
            continue;
        }

        if (left[i] < right[j]) {
            result.push(left[i++]);
        }
        else {
            result.push(right[j++]);
        }
    }

    return result;
}