在里面 快速排序 ，理想情况是始终选择中值作为轴心，因为这会导致时间最短。在本文中， 合并排序树 用于在快速排序中找到不同范围的中值，并分析比较次数。 例如：
null
Input : arr = {4, 3, 5, 1, 2}Output : 11ExplanationWe have to make 11 comparisons when we apply quick sort to the array.
如果我们仔细分析快速排序算法，那么每当数组被赋予快速排序函数时，数组总是由某个范围L到R的数字排列组成。最初，它是[1到N]，然后是[1到pivot–1]和[pivot+1到N]等等。而且，很难观察到每个可能的数组中数字的相对顺序都没有改变。现在为了得到枢轴元素，我们只需要得到中间数，即（r–l+2）/2 th 数组中的数字。 为了有效地做到这一点，我们可以使用 持久段树 A. 芬威克树 ，或 合并排序树 .本文重点介绍合并排序树的实现。 在改进的快速排序算法中，我们选择数组的枢轴元素作为数组的中位数。现在，确定中位数需要我们在对数组进行排序后找到所考虑的中间元素，该数组本身是一个O（n*log（n））操作，其中n是数组的大小。 假设我们有一个从L到R的范围，那么这个范围的中值计算如下：
Median of A[L; R] = Middle element of sorted(A[L; R]) = (R - L + 1)/2th element of sorted(A[L; R])
让我们考虑在快速排序算法中有p个分区，这意味着我们必须通过将数组范围从L到R排序来找到枢轴，其中L和R是每个分区的起始点和结束点。这很昂贵。 但是 ，在每个分区中，我们有一个从L到R的数字排列，所以我们可以找到ceil（（R–L+1）/2） th 我们知道，当我们对这个分区进行排序时，这个范围内的最小数总是这个元素，最终会成为中间元素，也就是枢轴。现在，小于pivot的元素进入左子树，大于pivot的元素进入右子树，也保持了它们的顺序。 我们对所有分区P重复这个过程，并找到每个分区中涉及的比较。因为在当前分区中，该分区从L到R的所有元素都会与枢轴进行比较，所以我们在当前分区中进行（R–L+1）比较。我们还需要通过递归计算，考虑左、右子树的总比较。因此我们得出结论，
Total Comparisons = Comparisons in Current Partition + Comparisons in Left partition + Comparisons in right partition
我们在上面讨论了有效地找到枢轴元素的方法 K th 使用合并排序树的顺序统计 可用于查找与讨论相同的内容。
CPP
// CPP program to implement number of comparisons // in modified quick sort #include <bits/stdc++.h> using namespace std; const int MAX = 1000; // Constructs a segment tree and stores tree[] void buildTree( int treeIndex, int l, int r, int arr[], vector< int > tree[]) { /* l => start of range, r => ending of a range treeIndex => index in the Segment Tree/Merge Sort Tree */ /* leaf node */ if (l == r) { tree[treeIndex].push_back(arr[l - 1]); return ; } int mid = (l + r) / 2; /* building left subtree */ buildTree(2 * treeIndex, l, mid, arr, tree); /* building left subtree */ buildTree(2 * treeIndex + 1, mid + 1, r, arr, tree); /* merging left and right child in sorted order */ merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin(), tree[2 * treeIndex + 1].end(), back_inserter(tree[treeIndex])); } // Returns the Kth smallest number in query range int queryRec( int segmentStart, int segmentEnd, int queryStart, int queryEnd, int treeIndex, int K, vector< int > tree[]) { /* segmentStart => start of a Segment, segmentEnd => ending of a Segment, queryStart => start of a query range, queryEnd => ending of a query range, treeIndex => index in the Segment Tree/Merge Sort Tree, K => kth smallest number to find */ if (segmentStart == segmentEnd) return tree[treeIndex][0]; int mid = (segmentStart + segmentEnd) / 2; // finds the last index in the segment // which is <= queryEnd int last_in_query_range = (upper_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin()); // finds the first index in the segment // which is >= queryStart int first_in_query_range = (lower_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryStart) - tree[2 * treeIndex].begin()); int M = last_in_query_range - first_in_query_range; if (M >= K) { // Kth smallest is in left subtree, // so recursively call left subtree for Kth // smallest number return queryRec(segmentStart, mid, queryStart, queryEnd, 2 * treeIndex, K, tree); } else { // Kth smallest is in right subtree, // so recursively call right subtree for the // (K-M)th smallest number return queryRec(mid + 1, segmentEnd, queryStart, queryEnd, 2 * treeIndex + 1, K - M, tree); } } // A wrapper over query() int query( int queryStart, int queryEnd, int K, int n, int arr[], vector< int > tree[]) { return queryRec(1, n, queryStart, queryEnd, 1, K, tree); } /* Calculates total Comparisons Involved in Quick Sort Has the following parameters: start => starting index of array end => ending index of array n => size of array tree => Merge Sort Tree */ int quickSortComparisons( int start, int end, int n, int arr[], vector< int > tree[]) { /* Base Case */ if (start >= end) return 0; // Compute the middle point of range and the pivot int middlePoint = (end - start + 2) / 2; int pivot = query(start, end, middlePoint, n, arr, tree); /* Total Comparisons = (Comparisons in Left part + Comparisons of right + Comparisons in parent) */ // count comparisons in parent array int comparisons_in_parent = (end - start + 1); // count comparisons involved in left partition int comparisons_in_left_part = quickSortComparisons(start, pivot - 1, n, arr, tree); // count comparisons involved in right partition int comparisons_in_right_part = quickSortComparisons(pivot + 1, end, n, arr, tree); // Return Total Comparisons return comparisons_in_left_part + comparisons_in_parent + comparisons_in_right_part; } // Driver code int main() { int arr[] = { 4, 3, 5, 1, 2 }; int n = sizeof (arr) / sizeof (arr[0]); // Construct segment tree in tree[] vector< int > tree[MAX]; buildTree(1, 1, n, arr, tree); cout << "Number of Comparisons = " << quickSortComparisons(1, n, n, arr, tree);; return 0; } |
输出：
Number of Comparisons = 11
复杂性是O（log） 2. （n） ）每查询一次
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
