我有这样的合并源代码。
void mergesort(low, high){
index mid;
if(low < high){
mid = (low+high)/2;
mergesort(low mid);
mergesort(mid+1, high);
merge(low, mid, high);
}
}
void merge(low, high, mid){
index i = low, j = mid +1, k = low;
while(i<=mid && j<=high){
if(S[i] < S[j]) {
U[k] = S[i];
i++;
}else{
U[k] = S[j];
j++;
}
k++;
}
if(i > mid){
copy S[j] through S[high] to U[k] through U[high]
}else{
copy S[i] through S[mid] to U[k] through U[high];
copy U[low] through U[high] to S[low] through S[high];
}
我想制定更有效的方法来调整“索引”。我怎样才能更有效地选择一些指标?
最佳答案
常用归并排序将数组分成相等的两半,因为在一般情况下没有更有效和更简单的策略。
但对于特定情况,可能会使用 natural merge sort - 它根据数据集自动选择拆分方案 - 对于部分排序的数据,它可能更有效 - 它选择排序的元素序列并合并它们,而无需为短片做过多工作。
也许在一般情况下,与划分为等份相比,确定此类序列的成本可能会变得相当高。
关于algorithm - 如何通过使用一些索引来制作高效的合并排序算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52960161/