首页 > 代码库 > 归并排序的应用
归并排序的应用
一、归并排序
算法思路就是把数组分成左右两个部分,然后再进行归并两个有序表
void merge(int* num,int start,int mid,int end,int* copy) { int i = start,m = mid,j = mid+1,n = end,k=start; while(i <= m && j <= n) { if(num[i] < num[j])copy[k++] = num[i++]; else copy[k++] = num[j++]; } while(i <= m)copy[k++] = num[i++]; while(j <= n)copy[k++] = num[j++]; while(--k >= start) { num[k] = copy[k]; } } int mergeSort(int* num,int start,int end,int* copy) { if(start < end) { int mid = start + ((end - start)>>1); mergeSort(num,start,mid,copy);//分成两个有序数组 mergeSort(num,mid+1,end,copy); merge(num,start,mid,end,copy);//归并两个有序数组 } } void mergeSort(int* num,int length) { int* copy = new int[length]; mergeSort(num,0,length-1,copy); }变形一:leetcode之
Sort List
Sort a linked list in O(n log n) time using constant space complexity.
方法一;归并
struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: ListNode *sortList(ListNode *head) { if(!head || !head->next)return head; ListNode* fast = head -> next -> next;//至少有两个节点 ListNode* slow = head; while(fast) { fast = fast->next; slow = slow->next; if(!fast)break; fast = fast->next; } ListNode* p = slow -> next; slow -> next = NULL; ListNode* q = sortList(head); p = sortList(p); head = NULL; ListNode* tail = NULL; while(q && p) { if(q->val > p->val) { if(!head)head = tail = p; else { tail->next = p; tail = tail->next; } p = p->next; } else { if(!head)head = tail = q; else { tail->next = q; tail = tail->next; } q = q->next; } } if(p) { if(!head)head = tail = p; tail->next = p; } if(q) { if(!head)head = tail = q; else tail->next = q; } return head; } };方法二:快排,具体参考这里
剑指offer之数组中的逆序对
在数组中的两个数如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对,输入一个数组,求出这个数组中逆序对的总数
方法:边归并,边计数
void merge(int* data,int start,int mid,int end,int* tmp,int& count) { int i = mid,m = start,j = end,n = mid+1,k = end; while(i >= m && j >= n) { if(data[i] > data[j]) { count += j - n + 1; tmp[k--] = data[i--]; } else { tmp[k--] = data[j--]; } } while(i >= m)tmp[k--] = data[i--]; while(j >= n)tmp[k--] = data[j--]; while(++k <= end)data[k] = tmp[k]; } void InversePairs(int* data,int start,int end,int* tmp,int& count) { if(start < end) { int mid = start + ((end - start)>>1); InversePairs(data,start,mid,tmp,count); InversePairs(data,mid+1,end,tmp,count); merge(data,start,mid,end,tmp,count); } } int InversePairs(int* data,int length) { int* tmp = new int[length]; int count = 0; InversePairs(data,0,length-1,tmp,count); delete[] tmp; return count; }
归并排序的应用
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。