一、归并排序
归并排序的思路
归并排序是典型的分治算法,把一个数组的排序,分为两个子序列的排序,然后将两个有序序列合并。以上就是整个算法的核心。整个过程如下图所示(图侵删):
?...范围的内容被复制回原数组)
for(i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
}
二、归并排序的延伸算法...for(i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
return res;
}
可以发现,相比归并排序算法...例如:1, 5, 6, 3, 2的逆序对为(3,2), (5,2), (6,2), (5,3), (6,3)
算法思路
跟上一道题一样,在merge的基础上进行拓展。...arr[p1] <= arr[p2]) {
help[i++] = arr[p1++];
}else {
// 左 > 右,说明以p1为界限,p1~m之间的数据都大于右