0

我正在尝试用 C++ 编写排序算法，然后用伪代码编写它，然后用伪代码编写它并不算太糟糕，但是把它记在我的脑海里却变成了一场斗争，所以我向你们提出的问题：

我正在寻找一种算法，该算法采用一个未排序的数组，以及两个整数（比方说 B 和 C）并输出 TRUE，如果 A 包含一个既大于 B 又小于 C 的元素，否则它返回 FALSE。

For J <-- 1 to Length[A]
       Count <-- j+1
              while Count =< Length[A]

这是我的伪代码开始，因为这似乎是合乎逻辑的事情，然后在 c++ 中实现它，但是我发现自己在循环创建循环，并没有取得太大进展。希望我所说的一切都有意义，并且有人可以将它们放在一起以创建某种形式的解决方案。谢谢。

4

4 回答 4

1

我从 Steve McConnell 的Code Complete中回忆起，你的伪代码在理想情况下应该看起来更像英语而不是它。在我的拙见中，你跳得太快了。

那这个呢：

for each element in array
    check to see if element is between B and C
    if element is between B and C
        return TRUE
    else
        continue loop
next

return FALSE

这就是我从你的陈述中收集到的：

我正在寻找一种算法，该算法采用一个未排序的数组，以及两个整数（比方说 B 和 C）并输出 TRUE，如果 A 包含一个既大于 B 又小于 C 的元素，否则它返回 FALSE。

于 2012-10-31T18:09:25.133 回答
1

我将从一个检查您关心的条件的函数开始：给定一个数字，它是否在指定范围内：

boolean function in_range(A, B, C) {
    return (A > B) and (A < C);
}

从那里开始，扫描数组并调用函数，将数组的每个元素作为A（以及作为BandC提供的Band C）传递，就变成了一件简单的事情。如果函数true在任何时候返回，您可以停止扫描并且外部函数也返回 true（对于它的价值，C++11 提供std::any_of了这种情况）。

于 2012-10-31T18:11:02.447 回答
0

您只是在数组中搜索与条件 x > B && x < C 匹配的 x。线性搜索可以 - 如果您只进行一次搜索。如果必须多次进行搜索（除了 log（数组大小）之外的任何内容），那么首先排序然后进行二进制搜索是有意义的。

bool InRangeSearch(low, high)
{
  index = upper_bound(array, low);
  if(index==-1)
    return false;

  index2 = lower_bound(array, high);
  if(index2==-1)
    return true;

  return ((index2-1)>index);
}
于 2012-10-31T18:33:15.747 回答
0

伪代码：

Quicksort(A as array, low as int, high as int)
    if (low < high)
        pivot_location = Partition(A,low,high)
    Quicksort(A,low, pivot_location - 1)
    Quicksort(A, pivot_location + 1, high)

Partition(A as array, low as int, high as int)
     pivot = A[low]
     leftwall = low

     for i = low + 1 to high
         if (A[i] < pivot) then
             leftwall = leftwall + 1
             swap(A[i], A[leftwall])

     swap(A[low],A[leftwall])

    return (leftwall)

程序代码：

#include <stdio.h>

void quickSort( int[], int, int);
int partition( int[], int, int);


int  main() 
{
    int a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9};

    int i;
    printf("\n\nUnsorted array is:  ");
    for(i = 0; i < 9; ++i)      printf(" %d ", a[i]);

    quickSort( a, 0, 8);

    printf("\n\nSorted array is:  ");
    for(i = 0; i < 9; ++i)      printf(" %d ", a[i]);

    printf("\n\n " );
    return 0;

}



void quickSort( int a[], int l, int r)
{
   int j;

   if( l < r ) 
   {

        j = partition( a, l, r);
       quickSort( a, l, j-1);
       quickSort( a, j+1, r);
   }

}



int partition( int a[], int l, int r) {
   int pivot, i, j, t;
   pivot = a[l];
   i = l; j = r+1;

   while( 1)
   {
    do ++i; while( a[i] <= pivot && i <= r );
    do --j; while( a[j] > pivot );
    if( i >= j ) break;
    t = a[i]; a[i] = a[j]; a[j] = t;
   }
   t = a[l]; a[l] = a[j]; a[j] = t;
   return j;
}
于 2012-10-31T19:18:25.560 回答