在HeapSort时计算正值 [英] count positive values while HeapSort

问题描述

在进行HeapSort时如何计算正值?这是我的HeapSort，我在方法末尾将它们计数为一个循环，但需要在排序时完成.怎么样?

How to count positive values WHILE doing HeapSort? Here is my HeapSort and I count them in a loop at the end of the method, but it needs to be done while sorting. How''s that?

void Sift(int arr[], int left, int right)
{
	int i, j, x;
    
	i = left;
        j = 2 * i + 1;
	x = arr[i];
            
	while (j <= right)
	{
		if(j < right)
			if(arr[j] < arr[j + 1]) j++;
		
		if (x >= arr[j]) break;

		arr[i] = arr[j];
		i = j;
		j = 2 * i + 1;
	}
	
	arr[i] = x;
}

void HeapSort(int arr[], int n)
{
    int left, right, temp;

    left = n / 2 + 1;
    right = n - 1;

    while (0 < left)
    {
	left--;
                    
	Sift(arr, left, right);
    }

    while (0 < right)
    {
        temp = arr[left];
	arr[left] = arr[right];
	arr[right] = temp;

        right--;

	Sift(arr, left, right);
    }

    for(int i = 0; i < n; i++)
	if(0 < arr[i]) PosCount++;
}

推荐答案

为什么?

它不会更快.

排序为O(n log n).因此，您希望在排序时最快的是O(n log n)比较(而且您无法一次比较).

最后的循环是O(n).如果您想加快速度，请执行以下操作:

Why?

It''s not going to be faster.

The sort is O(n log n). So the fastest you could hope to be while doing it during the sort is O(n log n) comparsions (and you can''t do it in one comparison).

The loop at the end is O(n). And if you want to speed that up, do it as:

int i = 0;
while (0 < arr[i] && i < n)
   i++;

int PosCount = n - i;

就是O(n).

或者，如果您期望n很大，请执行二进制搜索:

Which is O(n).

Or if you expect n to be huge, do a binary search:

left = 0;
right = n - 1;
while (left > right) {
   int i = (left + right)/2;
   if (0 < arr[i]) {
       right = i;
   } else {
       left = i;
   }
}
int PosCount = n - left;

哪个是O(log n)

我看到要在排序时计算正数的唯一原因是这是一项家庭作业，或者该数组比物理内存大得多，并且您不想承担将其全部分页的开销.但是，如果是这样的话，堆排序将导致各种内存崩溃，那将是一个更糟糕的问题，那就是您进行不错的线性或二进制搜索.

Which is O(log n)

The only reason I could see for wanting to count the positive numbers while sorting is either this is a homework assignement, or the array is much larger than physical memory and you don''t want to incurr the cost of paging it all in again. But if that''s the case, the heap sort is going to cause all kinds of memory thrashing and that''ll be a worse problem then your nice linear or binary search.

那里没有理由遍历所有值，而对于O(n logn)的算法，这需要O(n)运算.
由于最后会有一个排序的数组，因此技巧"是:

在您的堆排序期间，请确定代码中第一个正整数所在的点.
然后可以通过以下方式计算正整数的数量:

大小-第一个正整数的索引

会增加算法的O(k)复杂度，这可以忽略不计.

There is no reason to loop over all of the values which requires a O(n) operation for an algorithm that is O(n logn).
Since you will have a sorted array in the end, the "trick" is:

During your heapsort identify the point in the code where the first positive integer resides.
The number of positive integers can then be calculated by:

Size - Index of first positive integer

which will add O(k) complexity to your algorithm, which will be negligible.

这篇关于在HeapSort时计算正值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！