首页 > 代码库 > 【排序】归并排序+逆序对应用
【排序】归并排序+逆序对应用
1 void merge_sort(int *A, int x, int y, int *T) 2 {//x为左端点,y为右端点 3 // 4 if(y-x<=1) return ; 5 int m = x + (y-x)/2;//划分 6 int p = x, q = m, i = x; 7 //递归 8 merge_sort(A, x, m, T); 9 merge_sort(A, m, y, T);10 //归并11 while(p < m || q < y)//只要有一个序列非空，就继续排序12 {13 if((q >= y) || (p < m && A[p] <= A[q]))14 {//若 第二个序列为空（第一个必非空）|| 两个均非空且A[p] <= A[q]时，将左半数组元素复制到临时空间15 T[i++] = A[p++];16 }17 else18 {//否则 第二个序列非空 && (p >= m || A[p] > A[q]时，将右半数组元素复制到临时空间19 T[i++] = A[q++];20 //cnt += m-p;21 }22 }23 for(int i = x; i < y; i++) {A[i] = T[i];}24 }
逆序对应用：
由于合并操作时从小到大进行的，当右边的A[j]复制到T中时，左边还没来得及复制到T中的数就是所有左边比A[j]大的数。此时只要在累加器中计入左边元素个数m-p即可。（左边所剩元素在[m, p)区间内）
1 void merge_sort(int *A, int x, int y, int *T) 2 {//x为左端点,y为右端点 3 // 4 if(y-x<=1) return ; 5 int m = x + (y-x)/2;//划分 6 int p = x, q = m, i = x; 7 //递归 8 merge_sort(A, x, m, T); 9 merge_sort(A, m, y, T);10 //归并11 while(p < m || q < y)//只要有一个序列非空，就继续排序12 {13 if((q >= y) || (p < m && A[p] <= A[q]))14 {//若 第二个序列为空（第一个必非空）|| 两个均非空且A[p] <= A[q]时，将左半数组元素复制到临时空间15 T[i++] = A[p++];16 }17 else18 {//否则 第二个序列非空 && (p >= m || A[p] > A[q])时，将右半数组元素复制到临时空间19 T[i++] = A[q++];20 cnt += m-p; //计数21 }22 }23 for(int i = x; i < y; i++) {A[i] = T[i];}24 }
【排序】归并排序+逆序对应用
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。