Timsort

Timsort 在 Python, Java 等编程语言的标准库中都有使用, 综合性能比较好.

Timsort 是对归并排序(merge sort)的优化.

Timsort 的步骤

它的优化思路是:

先将数组分成相同间隔的子数组, 常用的间隔值是 32 或者 24
然后用插入排序(或者考虑用希尔排序) 对这些子数组进行排序, 因为这些子数组比较短小, 插入排序的效率比较高
排序后, 依次将子数组合并在一起形成有序的大数组, 直到整个数组变得有序
合并子数组的方法与归并排序里一致, 不再详述
如果数组中的元素较少, 就只会使用插入排序

下图展示了 timsort 的一个示例:

timsort

Timsort 的实现

#![allow(unused)]
fn main() {
use crate::insertion_sort::insertion_sort;
use crate::shell_sort::shell_sort;

/// Timsort 是对归并排序 (merge sort) 的优化.
pub fn timsort<T>(arr: &mut [T])
where
    T: PartialOrd + Clone,
{
    const RUN: usize = 32;

    let len = arr.len();
    if len < 2 {
        return;
    }

    // 先将数组分隔成大小相同的子数组, 并利用插入排序进行排序.
    // 插入排序比较善于处理已基本有序的较小的数组.
    for i in (0..len).step_by(RUN) {
        let end = (i + RUN).min(len);
        insertion_sort(&mut arr[i..end]);
    }

    // 然后将各个子数组合并在一起
    // 数组间隔依次是 RUN, RUN * 2, RUN * 4, ...
    let mut size = RUN;
    while size < len {
        // 合并子数组
        for left in (0..len).step_by(2 * size) {
            // 两个子数组分别是 `arr[left..=middle]` 和 `arr[middle+1..=right]`.
            let middle = left + size - 1;
            let right = (left + 2 * size - 1).min(len - 1);

            if middle < right {
                merge(arr, left, middle, right);
            }
        }

        size *= 2;
    }
}

/// 合并子数组 `arr[left..=middle]` 和 `arr[middle+1..=right]`
fn merge<T>(arr: &mut [T], left: usize, middle: usize, right: usize)
where
    T: PartialOrd + Clone,
{
    // 先创建辅助数组
    let aux_left = arr[left..=middle].to_vec();
    let aux_right = arr[middle + 1..=right].to_vec();
    let left_len = middle - left + 1;
    let right_len = right - middle;

    // 合并子数组
    let mut i = 0;
    let mut j = 0;
    let mut k = left;
    while i < left_len && j < right_len {
        if aux_left[i] < aux_right[j] {
            arr[k].clone_from(&aux_left[i]);
            i += 1;
        } else {
            arr[k].clone_from(&aux_right[j]);
            j += 1;
        }
        k += 1;
    }

    // 最后复制剩下的元素
    while i < left_len {
        arr[k].clone_from(&aux_left[i]);
        i += 1;
        k += 1;
    }

    while j < right_len {
        arr[k].clone_from(&aux_right[j]);
        j += 1;
        k += 1;
    }
}

/// 其思路是, 先将前 i 个元素调整为增序的, 随着 i 从 0 增大到 n, 整个序列就变得是增序了.
pub fn insertion_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    let len = arr.len();
    for i in 1..len {
        for j in (1..=i).rev() {
            if arr[j - 1] > arr[j] {
                arr.swap(j - 1, j);
            } else {
                break;
            }
        }
    }
}
}

使用希尔排序代替插入排序

上面提到了, 可以用希尔排序来代替插入排序, 可以将子数组的间隔设置得更大些, 我们选取 RUN = 64;

#![allow(unused)]
fn main() {
/// 使用希尔排序代替插入排序
///
/// 只创建一次辅助数组
pub fn shell_timsort<T>(arr: &mut [T])
where
    T: PartialOrd + Clone,
{
    const RUN: usize = 64;

    let len = arr.len();
    if len < 2 {
        return;
    }

    // 先将数组分隔成大小相同的子数组, 并利用插入排序进行排序.
    // 插入排序比较善于处理已基本有序的较小的数组.
    for i in (0..len).step_by(RUN) {
        let end = (i + RUN).min(len);
        shell_sort(&mut arr[i..end]);
    }

    // 然后将各个子数组合并在一起
    // 数组间隔依次是 RUN, RUN * 2, RUN * 4, ...
    let mut size = RUN;
    let mut aux = arr.to_vec();

    while size < len {
        // 合并子数组
        for left in (0..len).step_by(2 * size) {
            // 两个子数组分别是 `arr[left..=middle]` 和 `arr[middle+1..=right]`.
            let middle = left + size - 1;
            let right = (left + 2 * size - 1).min(len - 1);

            if middle < right {
                merge_with_aux(arr, left, middle, right, &mut aux);
            }
        }

        size *= 2;
    }
}

/// 合并子数组 `arr[left..=middle]` 和 `arr[middle+1..=right]`
fn merge_with_aux<T>(arr: &mut [T], left: usize, middle: usize, right: usize, aux: &mut [T])
where
    T: PartialOrd + Clone,
{
    // 先初始化辅助数组
    for i in left..=right {
        aux[i].clone_from(&arr[i]);
    }

    // 合并子数组
    let mut i = left;
    let mut j = middle + 1;
    let mut k = left;
    while i <= middle && j <= right {
        if aux[i] < aux[j] {
            arr[k].clone_from(&aux[i]);
            i += 1;
        } else {
            arr[k].clone_from(&aux[j]);
            j += 1;
        }
        k += 1;
    }

    while i <= middle {
        arr[k].clone_from(&aux[i]);
        i += 1;
        k += 1;
    }
    while j <= right {
        arr[k].clone_from(&aux[j]);
        j += 1;
        k += 1;
    }
}

#[cfg(test)]
mod tests {
    use crate::timsort::{shell_timsort, timsort};

    #[test]
    fn test_timsort() {

/// Shell sort is a simple extension to insertion sort that allows exchanging
/// elements that far apart.
///
/// It produces partially sorted array (h-sorted array).
pub fn shell_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    const FACTOR: usize = 3;
    let len = arr.len();

    // 计算第一个 gap 的值, 大概是 len/3
    let mut h = 1;
    while h < len / FACTOR {
        h = FACTOR * h + 1;
    }

    while h >= 1 {
        // 使用插入排序, 将 `arr[0..h]` 排序好
        for i in h..len {
            let mut j = i;
            while j >= h && arr[j - h] > arr[j] {
                arr.swap(j - h, j);
                j -= h;
            }
        }

        h /= FACTOR;
    }
}
}

Timsort 的特点

最差情况下的时间复杂度是: O(n log(n)), 最间复杂度是 O(n)
如果数组已基本有序, 最好情况下的时间复杂度是 O(n)
是稳定排序, 不是原地排序 (in-place sort)
与归并排序不同的是, 它不需要递归调用自身将数组分成左右子数组
timsort 与插入归并排序的区别较大

数据结构与算法 - Rust 语言实现

Timsort

Timsort 的步骤

Timsort 的实现

使用希尔排序代替插入排序

Timsort 的特点

参考