(C/C++)k個有序陣列進行復雜度O(nlogk)的k-路歸併

摘要： 假定有k個有序陣列，每個陣列中含有n個元素，您的任務是將它們合併為單獨的一個有序陣列，該陣列共有kn個元素。 設計和實現 一個有效的分治演算法解決k-路合併操作問題，並分析時間複雜度。 思路 分治演算法即將有序陣列兩兩歸併 相關歸...

假定有k個有序陣列，每個陣列中含有n個元素，您的任務是將它們合併為單獨的一個有序陣列，該陣列共有kn個元素。

設計和實現 一個有效的分治演算法解決k-路合併操作問題，並分析時間複雜度。

思路

分治演算法即將有序陣列兩兩歸併

相關歸併程式碼源自網上博主寫的java程式碼，java的陣列可以直接求length，但C++的陣列要手動傳入length很麻煩……故改寫成C++費了一些時間

#include <iostream>
#define N 5
#define INDEX_COUNT 5
using namespace std;
int INDEX[INDEX_COUNT][N] =
{ 1,4,5,8,9,
2,6,8,9,10,
3,5,5,7,8,
4,5,6,7,12,
1,5,8,9,10 };

int MERGED_INDEXS[N*INDEX_COUNT];

void showArray(int a[], int length)
{
for (int i = 0; i < length; i++)
{
cout << a[i] << " ";
}
cout << "\n";
}


int* mergeTwoArrays(int* A, int* B,int lengthA,int lengthB) {
int* temp = new int[lengthA + lengthB];
int index = 0, i = 0, j = 0;
while (i < lengthA && j < lengthB) {
if (A[i] < B[j]) {
temp[index++] = A[i++];
}
else {
temp[index++] = B[j++];
}
}
while (i < lengthA) {
temp[index++] = A[i++];
}
while (j < lengthB) {
temp[index++] = B[j++];
}
return temp;
}

// 分治遞迴深度為O(log k), 每層合併時間複雜度O(n)
int* kMergeSort(int arrays[INDEX_COUNT][N], int start, int end) {
if (start >= end) {
return arrays[start];
}
int mid = start + (end - start) / 2;
int* left = kMergeSort(arrays, start, mid);
int* right = kMergeSort(arrays, mid + 1, end);
cout << "歸併INDEX" << start << "和INDEX" << end<<endl;
return mergeTwoArrays(left, right, N*(mid - start + 1), N*(end - mid));
}

int* mergekSortedArrays(int arrays[INDEX_COUNT][N],int length) {
int* list = new int[N*INDEX_COUNT];
if (arrays == NULL) {
return list;
}
int* ans = kMergeSort(arrays, 0, length - 1);
showArray(ans, N*INDEX_COUNT);
return list;
}




int main(void) {
for (int i = 0; i < INDEX_COUNT; i++) {
cout << "陣列" << i << ":";
showArray(INDEX[i], N);
}
mergekSortedArrays(INDEX, INDEX_COUNT);
//showArray(mergeTwoArrays(INDEX[0], INDEX[1], N, N), N + N);
system("pause");
return 0;
}