MergeSort和QuickSort衍生出来的问题

本文主要是介绍MergeSort和QuickSort衍生出来的问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

归并排序和快速排序的衍生问题

MergeSort和QuickSort代表了分治算法的两类基本思想：

MergeSort: 在分的时候没有做太多的考虑，就是将数组一分为二，然后递归的进行归并排序。关键在于这样分完之后，我们怎么讲他们归并起来。

QuickSort：在如何分上面做了很多设计，采用了一个标定点，使用partition过程将其移到了合适的位置，然后将数组分割成了两部分，这样分完之后，我们在做合的过程就不用在做太多考虑了。只需要一步一步递归下去即可。

两个直接从MergeSort和QuickSort衍生出来的问题

图中2，3是顺序对， 2，1 是逆序对

一个数组中逆序对的数量是衡量一个数组的有序程度

上面一个数组，逆序对为0，下面一个数组，任何两个数都是逆序对，这个数组的逆序对数量达到了最大值

双重循环，遍历没两个元素，if x < y, 逆序对数量++

这篇关于MergeSort和QuickSort衍生出来的问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程