2021-01-14：timsort是什么，如何用代码实现？

原创

福大大架构师每日一题

修改于 2021-01-15 10:48:41

1K0

修改于 2021-01-15 10:48:41

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

福哥答案2021-01-14：

答案来自此链接：

介绍：

timsort是一种混合、稳定高效的排序算法，源自合并排序和插入排序，旨在很好地处理多种真实数据。它由Tim Peters于2002年实施使用在Python编程语言中。该算法查找已经排序的数据的子序列，并使用该知识更有效地对其余部分进行排序。这是通过将已识别的子序列（称为运行）与现有运行合并直到满足某些条件来完成的。从版本2.3开始，Timsort一直是Python的标准排序算法。如今，Timsort 已是是 Python、 Java、 Android平台和 GNU Octave 的默认排序算法。

思想：

针对现实中需要排序的数据分析看，大多数据通常是有部分已经排好序的数据块，Timsort 就利用了这一特点。Timsort 称这些已经排好序的数据块为 “run”，我们可以将其视为一个一个的“分区”。在排序时，Timsort迭代数据元素，将其放到不同的 run 里，同时针对这些 run ，按规则进行合并至只剩一个，则这个仅剩的 run 即为排好序的结果。

换句话说，就是分析待排序数据，根据其本身的特点，将排序好的（不管是顺序还是逆序）子序列的分为一个个run分区，当然，这个分区run也存在一定的约束，即根据序列会产生一个minrun，如果原始的run小于minrun的长度，用插入排序扩充run，直到达到条件，之后使用归并排序来合并多个run。

知乎：

首先，timsort是Python里默认的排序算法，直接就可以在cPython的源码里找到，我没记错的话好像是600多行。

timsort改进自归并排序，因为待排序数据中是一定存在一些连续递增和连续严格递减子序列的，那么timsort会找到这样的子序列，称其为run。之后便是把严格递减的run反向，整个序列就变成了好多好多个递增的run。

然后就是使用归并排序的方式merge相邻的run，等到数组中只剩下一个run的时候自然就排好序了。

实际实现时，扫描出一个run就要分析一下已有的runs要不要合并，主要是通过最后面的两到三个run的长度来进行判断。

如果初始run的数量恰好为2的整数次幂或者略小于2的整数次幂，可以进一步避免长度差距太大的两个run的合并。（如果一个run的长度大于另一个run的两倍，就可以认为差距过大了）

所以要对长度过短的run使用插入排序进行扩充，最终要保证初始run的长度在32和64之间（记不清边界条件了，没敢写成区间形式），这样可以保证长度过短时用插入排序提高效率，初始run的长度较为接近，数量也保证了后续不会存在过多的差距过大的run的合并。

在合并的时候也没有使用普通的归并排序的方式，但唯独这一小块我还不太了解。之前自己用C++语言写过一个不完整的timsort，自认为还算是比较了解的，当然合并不同的run我用的是普通的归并排序的方式。

时间有限，timesort只是了解了大概。代码参考了其他文献，用go语言改写。代码里是非原地排序。代码如下：

package main

import (
    "fmt"
    "math/rand"
    "time"
)

//https://blog.csdn.net/sinat_35678407/article/details/82974174
func main() {
    rand.Seed(time.Now().Unix())
    SucCount := 0
    FaiedCount := 0
    for i := 0; i < 1000; i++ {
        arr1 := NewRandArr()
        arr2 := make([]int, len(arr1))
        copy(arr2, arr1)
        fmt.Println("原数组：", arr1)
        arr1 = timsort(arr1)
        fmt.Println("timsort排序：", arr1)
        SelectionSort(arr2)
        fmt.Println("选择排序：", arr2)

        isEqual := true
        for j := 0; j < len(arr1); j++ {
            if arr1[j] != arr2[j] {
                isEqual = false
                fmt.Println("错误")
                break
            }
        }
        if isEqual {
            SucCount++
        } else {
            FaiedCount++
        }
        fmt.Println("----")
    }
    fmt.Println("成功 = ", SucCount)
    fmt.Println("失败 = ", FaiedCount)

}
func binary_search(arr []int, left int, right int, value int) int {
    if left >= right {
        if arr[left] <= value {
            return left + 1
        } else {
            return left
        }
    } else {
        mid := left + (right-left)>>1
        if arr[mid] < value {
            return binary_search(arr, mid+1, right, value)
        } else {
            return binary_search(arr, left, mid-1, value)
        }
    }
}
func insertion_sort(arr []int) []int {
    arrLen := len(arr)
    ret := make([]int, 0)
    for i := 1; i < arrLen; i++ {
        value := arr[i]
        pos := binary_search(arr, 0, i-1, value)

        ret = append(ret, arr[:pos]...)
        ret = append(ret, value)
        ret = append(ret, arr[pos:i]...)
        ret = append(ret, arr[i+1:]...)
    }
    return ret
}
func merge(l1 []int, l2 []int) []int {
    l1Len := len(l1)
    if l1Len <= 0 {
        return l2
    }
    l2Len := len(l2)
    if l2Len <= 0 {
        return l1
    }
    ret := make([]int, 0)
    if l1[0] < l2[0] {
        ret = append(ret, l1[0])
        ret = append(ret, merge(l1[1:], l2)...)
    } else {
        ret = append(ret, l2[0])
        ret = append(ret, merge(l1, l2[1:])...)
    }
    return ret
}
func timsort(arr []int) []int {
    arrLen := len(arr)
    if arrLen <= 1 {
        return arr
    }
    runs := make([][]int, 0)
    //sorted_runs := make([][]int, 0)
    new_run := []int{arr[0]}
    for i := 1; i < arrLen; i++ {
        if arr[i] < arr[i-1] {
            runs = append(runs, new_run)
            new_run = []int{arr[i]}
        } else {
            new_run = append(new_run, arr[i])
        }
        if arrLen-1 == i {
            runs = append(runs, new_run)
            break
        }
    }
    for i := 0; i < len(runs); i++ {
        insertion_sort(runs[i])
    }
    sorted_arr := make([]int, 0)
    for i := 0; i < len(runs); i++ {
        sorted_arr = merge(sorted_arr, runs[i])
    }
    //fmt.Println(sorted_arr)
    return sorted_arr

}

//选择排序
func SelectionSort(arr []int) {
    arrlen := len(arr)
    if arrlen < 2 {
        return
    }
    // 0～n-1
    // 1～n-1
    // 2～n-1
    for i := 0; i < arrlen; i++ { // i ~ N-1
        // 最小值在哪个位置上  i～n-1
        minIndex := i
        for j := i + 1; j < arrlen; j++ { // i ~ N-1 上找最小值的下标
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
}

//产生一个随机数组
func NewRandArr() []int {

    Len := rand.Intn(100) + 1
    ret := make([]int, Len)
    for i := 0; i < Len; i++ {
        ret[i] = rand.Intn(1000)
    }
    return ret
}

执行结果如下：