归并排序是分治法的一个好例子,属于基于比较的内部/外部排序算法。普通的归并算法具有 O(n * log(n))
的时间和 O(n)
的空间复杂度。就地归并算法能帮助降低额外空间开销,使得归并排序更高效。
时间复复杂度的推导也非常的典型:
T(N)=2T(N2)+N
T(N)N=T(N/2)N/2+1
T(N)N=11+logN
T(N)=O(NlogN)
归并排序之所以可以轻松应用到外部排序上,是因为归并排序的归并过程是顺序扫描的,可以用来处理顺序存储的文件,多路归并还可以用多线程或是并行计算来加速,这样处理大文件就方便了。而想随机访问一个文件,就没那么快了。
排序数组
void merge(int a[], int temp[], int left, int right, int rightEnd) {
int leftEnd = right - 1;
int numElement = rightEnd - left + 1;
int i = left;
while (left <= leftEnd && right <= rightEnd) {
if (a[left] < a[right])
temp[i++] = a[left++];
else
temp[i++] = a[right++];
}
while (left <= leftEnd)
temp[i++] = a[left++];
while (right <= rightEnd)
temp[i++] = a[right++];
for (i = 0; i < numElement; i++, rightEnd--)
a[rightEnd] = temp[rightEnd];
}
void mergeSort(int a[], int temp[], int leftBegin, int rightEnd) {
int mid;
if (leftBegin < rightEnd) {
mid = (leftBegin + rightEnd)/2;
mergeSort(a, temp, leftBegin, mid);
mergeSort(a, temp, mid + 1, rightEnd);
merge(a, temp, leftBegin, mid + 1, rightEnd);
}
}
int main () {
int a[10] = {9, 2, 8, 3, 4, 1, 5, 18, 11, 14};
int temp[10];
mergeSort(a, temp, 0, 9);
for (int i = 0; i < 10 ; i++)
printf("%d#", a[i]);
printf("\n");
}
合并两个有序的链表
leetcode 21 题正是应用归并排序来实现两个有序链表的合并。
下面代码可以通过测试。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL)
return l2;
if (l2 == NULL)
return l1;
ListNode *head = new ListNode(0);
ListNode *pos = head;
int temp;
while(l1 && l2) {
if (l1->val < l2->val) {
temp = l1->val;
l1 = l1->next;
}
else {
temp = l2->val;
l2 = l2->next;
}
pos->next = new ListNode(temp);
pos = pos->next;
}
while(l1 != NULL) {
pos->next = new ListNode(l1->val);
pos = pos->next;
l1 = l1->next;
}
while(l2 != NULL) {
pos->next = new ListNode(l2->val);
pos = pos->next;
l2 = l2->next;
}
return head->next;
}