algorithm - 识别数据 block (段)以实现集群排序

Question

我正在寻找任何语言或其伪代码的 Clump Sort 实现。原始研究论文不包含任何内容。由于我找不到任何现有的解决方案(主要是因为这项技术很新)，我决定自己实现。因此，作为第一步，我需要识别数字输入中的数据 block 。我知道这可能会走向人工智能，但我已经做好了准备，因为我了解基础知识。

那么关于如何识别数据人员中的团 block 有什么想法吗？现在我想关注上升或下降的数字 block 。

例如:
3, 7, 10, 56, 4, 1, 3, 34
按升序排列有 3 个团 block :
3, 7, 10, 56,
4,
1, 3, 34

我的问题是如何以编程方式执行此操作？

(簇排序:http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5489222)

谢谢!

---

更新:

好吧，我花了一些时间找到了解决方案，但我不知道论文作者是否也有同样的想法。如果是，那么我们可能已经增加了堆排序的复杂性而不是最小化它。

int[] input = { 30, 7, 10, 56, 4, 1, 3, 34 };
List<ClumpStartEnd> clumps = new List<ClumpStartEnd>();
public void ClumpIdentifier(int start)
{
    for (int i = start + 1; i < input.Length + 1; i++)
    {
        if (i == input.Length || input[i] < input[i - 1])
        {
            clumps.Add(new ClumpStartEnd(start, i - 1));
            ClumpIdentifier(i);
            break;
        }
    }
}

Answer 1

我同意 Timsort 会被打败，但我是在论文提交后不久才发现它的；对此感到抱歉。

OP 对该算法的评估很糟糕。每次 Clump 遇到反转时，它都会在期望的升序和降序之间交替。 3, 7, 10, 56, 4, 1, 3, 34 因此是 3, 7, 10, 56 的升序，然后反转开始 4, 1 的降序，然后该顺序的反转开始升序共 3 个，共 34 个。