zhengrenzhe's blog   About

选择与插入排序

选择与插入排序是排序算法中最简单,最易理解的两个,可以作为学习一系列排序算法的开端。

选择排序

选择排序的概念极易理解:从序列初始位置遍历至序列尾,每次遍历过程中在当前索引与最后一位元素之间寻找最小(大)的元素,并与当前索引元素交换。

选择排序的缺点是无论当前序列的排序情况怎样,都需要在每次遍历过程中扫描当前索引后的所有元素,这造成了对一个完全随机的序列和已经几乎排好序的序列排序,所花费的时间是一样的,所以选择排序无法应用于大型数据的排序。

import { swap } from "./tools";

export default function sort<T>(items: T[], cmp = (a: T, b: T) => a > b) {
    let index = 0;
    const length = items.length;

    // 遍历每个元素
    while (index < length) {

        // 找到当前索引后最大(小)的元素
        const targetIndex = find(items, index, cmp);

        // 交换
        swap(items, index, targetIndex);
        index++;
    }
    return items;
}

function find<T>(
    items: T[],
    startPos: number,
    cmp: (a: T, b: T) => boolean,
): number {
    const endPos = items.length;
    let targetIndex = startPos;
    while (startPos !== endPos) {
        if (cmp(items[startPos], items[targetIndex])) targetIndex = startPos;
        startPos++;
    }
    return targetIndex;
}
// tools.ts
export function swap<T>(items: T[], pIndex: number, qIndex: number) {
    const tmp = items[pIndex];
    items[pIndex] = items[qIndex];
    items[qIndex] = tmp;
}

插入排序

插入排序也很容易理解,他的过程类似于排序扑克牌:对当前序列进行遍历,在遍历过程中,将当前元素 i 与其左边的元素进行比较,如果大(小)于左边的元素,则交换两者位置。交换后的(原 i)元素继续与左边的元素比较,不断重复这个过程,直到不再满足当前元素大(小)于左边的元素,则当前这次遍历结束。每次遍历过程中不断交换两个元素的过程,从整体来看就是将元素插入到一个位置,并将这个位置后的元素进行整体后移的过程。

对于遍历过程中的每一个元素,其左边都是经过之前步骤所排序好的,所以插入排序对于几乎排好序的序列很高效,因为只需要将当前元素与左边的几个进行对比,不像选择排序还需要扫描剩余的内容。

总的来说,插入排序对部分排好序或小型数组比较高效。

import { swap } from "./tools";

export default function sort<T>(items: T[], cmp = (a: T, b: T) => a > b) {
    let index = 1;
    const length = items.length;

    // 遍历每个元素
    while (index < length) {

        // 从当前元素开始不断与左边的元素对比,满足条件则交换,继续与左边的对比
        // 直到序列顶端或不满足条件为止
        let leftIndex = index;
        while (leftIndex > 0 && cmp(items[leftIndex], items[leftIndex - 1])) {
            swap(items, leftIndex, leftIndex - 1);
            leftIndex--;
        }
        index++;
    }

    return items;
}

← Microsoft Chakra 嵌入使用指南  希尔排序 →