java 将 MergeSort 与插入排序相结合，使其更高效
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15057287/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Combining MergeSort with Insertion sort to make it more efficient
提问by Rubee
So I have a MergeSort algorithm and I want to combine MergeSort with Insertion sort to reduce the overhead of merging, the question is how? I want to sort the segments using insertion sort and then merge.
所以我有一个 MergeSort 算法，我想结合 MergeSort 和插入排序来减少合并的开销，问题是如何？我想使用插入排序对段进行排序，然后合并。
public class mergesorttest{
public static void main(String[]args){
int d[]= {10,2,3,4,5,6,5,4,3,5,6,7,1};
mergeSort(d,0,d.length);
for(int x:d) System.out.print(x+" ");
System.out.println();
}
static void mergeSort(int f[],int lb, int ub){
//termination reached when a segment of size 1 reached -lb+1=ub
if(lb+1<ub){
int mid = (lb+ub)/2;
mergeSort(f,lb,mid);
mergeSort(f,mid,ub);
merge(f,lb,mid,ub);
}
}
static void merge (int f[],int p, int q, int r){
//p<=q<=r
int i =p; int j = q;
//use temp array to store merged sub-sequence
int temp[] = new int[r-p]; int t = 0;
while(i<q && j<r){
if(f[i]<=f[j]){
temp[t] =f[i];
i++;t++;
}
else{
temp[t] = f[j];
j++;
t++;
}
//tag on remaining sequence
while(i<q){
temp[t] = f[i];
i++;
t++;
}
while(j<r){
temp[t]=f[j];
j++;
t++;
}
//copy temp back to f
i=p;t=0;
while(t<temp.length){
f[i]=temp[t];
i++;
t++;
}
}
}
}
public static void insertion_srt(int array[], int n, int b){
for (int i = 1; i < n; i++){
int j = i;
int B = array[i];
while ((j > 0) && (array[j-1] > B)){
array[j] = array[j-1];
j--;
}
array[j] = B;
}
}
回答by Bernhard Barker
The merging automatically takes care of sorting the elements. However, one can sort using insertion sort when the list gets below some threshold:
合并会自动处理元素的排序。但是，当列表低于某个阈值时，可以使用插入排序进行排序：
static final int THRESHOLD = 10;
static void mergeSort(int f[],int lb, int ub){
if (ub - lb <= THRESHOLD)
insertionSort(f, lb, ub);
else
{
int mid = (lb+ub)/2;
mergeSort(f,lb,mid);
mergeSort(f,mid,ub);
merge(f,lb,mid,ub);
}
}
Doing anything other than this (except playing around with the threshold a little) will increasethe time taken by merge sort.
做除此之外的任何事情（除了稍微玩弄阈值）都会增加归并排序所花费的时间。
Although merge sort is O(n log n) and insertion sort is O(n2), insertion sort has better constants and is thus faster on very small arrays. This, this, thisand thisare a few related questions I found.
尽管归并排序是 O(n log n) 并且插入排序是 O(n 2)，但插入排序具有更好的常数，因此在非常小的数组上速度更快。This, this, this和this是我发现的一些相关问题。
回答by Ankit Anand
public static final int K = 5;
public static void insertionSort(int A[], int p, int q) {
for (int i = p; i < q; i++) {
int tempVal = A[i + 1];
int j = i + 1;
while (j > p && A[j - 1] > tempVal) {
A[j] = A[j - 1];
j--;
}
A[j] = tempVal;
}
int[] temp = Arrays.copyOfRange(A, p, q +1);
Arrays.stream(temp).forEach(i -> System.out.print(i + " "));
System.out.println();
}
public static void merge(int A[], int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int[] LA = Arrays.copyOfRange(A, p, q +1);
int[] RA = Arrays.copyOfRange(A, q+1, r +1);
int RIDX = 0;
int LIDX = 0;
for (int i = p; i < r - p + 1; i++) {
if (RIDX == n2) {
A[i] = LA[LIDX];
LIDX++;
} else if (LIDX == n1) {
A[i] = RA[RIDX];
RIDX++;
} else if (RA[RIDX] > LA[LIDX]) {
A[i] = LA[LIDX];
LIDX++;
} else {
A[i] = RA[RIDX];
RIDX++;
}
}
}
public static void sort(int A[], int p, int r) {
if (r - p > K) {
int q = (p + r) / 2;
sort(A, p, q);
sort(A, q + 1, r);
merge(A, p, q, r);
} else {
insertionSort(A, p, r);
}
}
public static void main(String string[]) {
int[] A = { 2, 5, 1, 6, 7, 3, 8, 4, 9 };
sort(A, 0, A.length - 1);
Arrays.stream(A).forEach(i -> System.out.print(i + " "));
}
