#include <iostream>
using namespace std;//最naive的方法
void merge(int a[], int len1, int b[], int len2)
{int i = 0, j = 0, k = 0;int *tmp = new int[len1 + len2];while(i < len1 && j < len2){tmp[k++] = a[i] < b[j] ? a[i++] : b[j++]; }while(i < len1)tmp[k++] = a[i++];while(j < len2)tmp[k++] = b[j++];for(i = 0; i < k; ++i)a[i] = tmp[i];delete[] tmp;
}//better wayvoid merge_inverse(int a[], int len1, int b[], int len2)
{int i = len1 - 1, j = len2 - 1, k = len1 + len2 - 1;while(i > -1 && j > -1){a[k--] = a[i] > b[j] ? a[i--] : b[j--];}while(i > -1)a[k--] = a[i--];while(j > -1)a[k--] = b[j--];
}//in-place mergesort
void swap(int &x, int &y)
{x = x ^ y;y = x ^ y;x = x ^ y;
}
void merge_inplace(int a[], int lower, int upper)
{int mid = (lower + upper - 1) >> 1;int i = lower;while(i <= mid){if(a[mid + 1] < a[i]){swap(a[i], a[mid + 1]);for(int j = mid + 1; j < upper; ++j){if(a[j] <= a[j + 1])break;swap(a[j], a[j + 1]);}} i++;}
}int main(void)
{int a[100] = {1, 5, 8, 9, 20, 24};int len1 = 6;int b[] = {3, 6, 7, 14, 16, 18};int len2 = sizeof(b) / sizeof(int);int c[] = {1, 5, 8, 9, 20, 24, 3, 6, 7, 14, 16, 18};//merge(a, len1, b, len2);//merge_inverse(a, len1, b, len2);merge_inplace(c, 0, 12);for(int i = 0; i < 12; ++i)cout << c[i] << " ";
/*for(int i = 0; i < len1 + len2; ++i){cout << a[i] << " ";}*/cout << endl;return 0;
}
详细解决方案
Q9.1
热度:76 发布时间:2024-01-15 21:20:02.0
相关解决方案