0

我现在正在学习 TimSort，并且遇到了它在不同编程语言中的实现。但其中一些似乎被“剃光”了——缺少某些对构成 TimSort 至关重要的功能。我看过原作者 Tim Peters 的原始 C 实现，以及 Joshua Blancs 的 java 重写？但是有一些符号和方法我很难掌握（只是我，还是看起来不可读？）

无论哪种方式，这是我找到并修改的代码，但它缺少识别自然增加的运行或反转减少的运行，检查不变的 C>B+A、D>C+B 等是否几乎/完美地合并实现了相等、平衡的子阵列，以及著名的驰骋功能。我可以帮助以更易读的方式实现它们吗？考虑到它可以是 [32-65]，runSize 是 32 还是 64 更好？谢谢你。

我的代码：

public class TimSort {
private final int runSize = 64;

void timSort(int[] A, int n) {
    for (int i = 0; i < n; i += minrunSize(runSize)) {
        insertionSort(A, i, Math.min((i + runSize - 1), (n - 1)));
    }

    // Start merging from minrunSize 32, doubling each iteration
    for (int size = minrunSize(runSize); size < n; size = 2 * size) {

        // Start merging from left(A[0])
        // After every merge, we increase left by 2*size
        for (int leftEnd = 0; leftEnd < n; leftEnd += 2 * size) {
            // In 1 run(size>=64), halve it into left & right sub-arrays
            int mid = leftEnd + size - 1; //Start of right sub-array = mid+1
            int rightEnd = Math.min((leftEnd + 2 * size - 1), (n - 1));
            if (mid < rightEnd) merge(A, leftEnd, mid, rightEnd);
        }
    }
}

// Calculate minrunSize N such that  n/N <= 2^__
// if n<64, minrunSize N = n, simple Insertion Sort
int minrunSize(int z) {
    assert z >= 0 : "N cannot be negative!"; 


    int r = 0;
    while (z >= runSize) {
        r += (z % 2);
        z /= 2;
    }
    return z + r;
}

void insertionSort(int[] A, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int temp = A[i];
        int j = i - 1;
        while (j >= left && A[j] > temp) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = temp;
    }
}

void merge(int[] A, int L, int M, int R) {
    int leftPointer = M - L + 1, rightPointer = R - M;
    // Creating leftA & rightA separately, pointer gives size
    int[] leftA = new int[leftPointer];
    for (int i = 0; i < leftPointer; i++) leftA[i] = A[L + i];
    int[] rightA = new int[rightPointer];
    for (int i = 0; i < rightPointer; i++) rightA[i] = A[M + 1 + i];

    int i = 0;
    int j = 0;
    int k = L;

    // After comparing, merge into original A
    while (i < leftPointer && j < rightPointer) {
        if (leftA[i] <= rightA[j]) {
            A[k] = leftA[i];
            i++;
        } else {
            A[k] = rightA[j];
            j++;
        }
        k++;
    }
    // Copy any remaining elements in leftA
    while (i < leftPointer) {
        A[k] = leftA[i];
        k++;
        i++;
    }
    // Copy any remaining elements in rightA
    while (j < rightPointer) {
        A[k] = rightA[j];
        k++;
        j++;
      }
    }
}

Joshua Bolch 在 java 中的实现： https ://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/TimSort.java

4

0 回答 0