转自：http://www.jb51.cc/article/p-vqxjuxmc-bag.html

问题：寻找数组中的最小值和最大值。

一道很简单的题目，一般有下面4种解法：

1遍历两次，每次分别找出最小值和最大值。

2只遍历一次，每次取出的元素先与已找到的最小值比较，再与已找到的最大值比较。

3每次取两个元素，将较小者与已找到的最小值比较，将较大者与已找到的最大值比较。

4分治：将数组划分成两半，分别找出两边的最小值、最大值，则最小值、最大值分别是两边最小值的较小者、两边最大值的较大者。

这4种算法，哪种效率最高，哪种最低？

后两种算法只要进行1.5*N次比较，因而网上有不少解答都将它们列为最佳答案。但是，算法4用到了递归，而递归法函数调用的开销是很大的，这就注定了该算法的效率肯定不高。那么，算法3就是最高效的吗？还是用代码来验证吧。

后面的代码，对每种算法都实现了两个函数（假设数组长度为N）：

算法1：solve_1a与solve_1b，后者加入两个临时变量，编译器可以将变量储存在寄存器中，不用每次循环都要写内存。比较次数为2*N次。

算法2：solve_2a与solve_2b，前者每次循环必比较2次，后者最好情况下(递减数组)只要比较1次，但最差情况下（递增数组）则要比较2次，比较次数为：N到2 * N次。

算法3：solve_3a与solve_3b，前者每次循环取头尾两元素（从两头往中间取），后者取相邻两元素。比较次数为1.5 * N次。

算法4：solve_4a与solve_4b，后者返回一个结构（只有两个元素），编译器优化可以通过两个寄存器返回该结构，减少写内存次数。（检查gcc产生的汇编，确认有进行该优化）。比较次数为1.5 * N次。

下面是测试结果：（数组长度为6e7，每种算法测4次取平均值）

编译参数：tdm-gcc 4.5.2-dw2:g++ -O3 -s -Wextra –WallVC 2010:cl /Ox /EHsc /nologo /W3

很明显，“分治”法的效率远低于其它3种算法。对前3种算法，将数组长度增加到1e8，并对十组随机数组进行测试，得到结果：

从上面的表和图可以看出，算法3在数组有序时，运行效率很高（但与算法2相差不大），而在乱序时，甚至比两次遍历都慢。乱序时：算法2效率最高，算法1次之，算法3效率最低。

算法2a和算法2b的效率差不多，有时算法2a的效率还略高。算法2a，每次循环都要比较2次，算法2b每次循环要比较1到2次，但由于前者的两次比较是无关的，后者的比较是相关的（第一次比较的结果决定是否进行第二次比较），在现代cpu“指令预测”等技术前，算法2a在某些情况下能比较算法2b更高效。

算法3的效率也不是绝对最差的，上面的随机数组是通过随机产生一些数得到，如果把它改为对数组的元素进行“随机洗牌”，就得到下面的结果（所得的新数据与上面的数据和并，下图中第一、三列是上面的数据，第二、四列是改用“随机洗牌”后得到的新数据）：

从图可以看出，改用“随机洗牌”法得到乱序数组后，VC的结果没发生改变，GCC除了函数3a，结果也没改变，但是“3a一次取头尾两元素”却成为最高效的算法，但其效率和“一次遍历取一个元素”法，相差并不是太大。因而可以说，在单线程环境下，“一次遍历取一个元素”这个最容易想到的方法，反而是本题的最佳解法。

算法上的最优，并不一定是实际上的最优，快排和堆排序就是一个典型的例子，虽然快排最坏情况下的复杂度是O(N^2)，而堆排序始终是O(N lgN)，但实际运用中，一个好的快排实现一般都比堆排序快很多。何况这4种算法的复杂度还都是O(N)。为了在最坏情况下节省0.5 * N次比较，进行的所谓优化，得到的结果很可能与所期望的恰恰相反。

测试代码：

// by flyinghearts # qq.com

#include <algorithm>
#include <limits>
#include <vector>
#include <cstdio>

#define NOMINMAX 1
#include <windows.h>

#define TEST_CASE 1                  // 第0组还是第1组测试
#define RANDOM_SHUFFLE 0             // 乱序是否通过随机洗牌获得


#define TEST_RAND_POS 0              
const unsigned Pack = 4;     // 对某组数据连续测试Pack次，取平均值
const unsigned Rand_M = 5;   // 测试某个乱序数组的 Rand_M个子数组
#if ! TEST_CASE                      
 const unsigned Fix_M = 3;      // 固定数组长度时，测试Fix_M个乱序数组
 const unsigned Length = 6e7;   // 固定数组长度
#else
 const unsigned Fix_M = 10;  
 const unsigned Length = 1e8;  
#endif

#if _MSC_VER
  #pragma comment(lib,"winmm.lib")
#endif

inline unsigned mclock() { return timeGetTime(); }

void solve_1a(const int arr[],const size_t len,int& min_value,int& max_value)
{
  min_value = max_value = arr[0];
  for (const int *p = arr + 1; p < arr + len; ++p) 
    if (*p < min_value) min_value = *p;
  for (const int *p = arr + 1; p < arr + len; ++p) 
    if (*p > max_value) max_value = *p;
}


void solve_1b(const int arr[],int& max_value)
{
  int max_v = arr[0],min_v = arr[0];
  for (const int *p = arr + 1; p < arr + len; ++p) 
    if (*p < min_v) min_v = *p;
  for (const int *p = arr + 1; p < arr + len; ++p) 
    if (*p > max_v) max_v = *p;
  max_value = max_v;
  min_value = min_v;
}


void solve_2a(const int arr[],min_v = arr[0];
  for (const int *p = arr + 1; p < arr + len; ++p) {
    if (*p < min_v) min_v = *p;
    if (*p > max_v) max_v = *p;
  }
  max_value = max_v;
  min_value = min_v;
}

void solve_2b(const int arr[],min_v = arr[0];
  for (const int *p = arr + 1; p < arr + len; ++p) {
    if (*p < min_v) min_v = *p;
    else if (*p > max_v) max_v = *p;
  }
  max_value = max_v;
  min_value = min_v;
}

void solve_3a(const int arr[],int& max_value)
{
  // int min_v = std::numeric_limits<int>::max();
  // int max_v = std::numeric_limits<int>::min();
  // const int *low = arr - 1;
  // const int *high = arr + len;
  
  const int *low = arr;
  const int *high = arr + len - 1;
  int min_v,max_v;
  if (*low < *high) { min_v = *low; max_v = *high; }
  else { min_v = *high; max_v = *low; }

  while (++low <= --high) {
    if (*low <= *high) {
      if (*low < min_v) min_v = *low;
      if (*high > max_v) max_v = *high;
    } else {
      if (*high < min_v) min_v = *high;      
      if (*low > max_v) max_v = *low;
    }
  }
  max_value = max_v;
  min_value = min_v;
}


void solve_3b(const int arr[],int& max_value)
{
  // 长度为奇、偶数时，分别先取出1、2个元素。剩下的元素个数一定是偶数
  int min_v,max_v;
  size_t t = (len - 1u) % 2u;
  if (arr[0] <= arr[t]) { min_v = arr[0];  max_v = arr[t]; }
  else { min_v = arr[t];  max_v = arr[0]; }
  
  const int *p = arr + t + 1;
  while (p < arr + len) {      // p 和 arr + len 奇偶性始终相同
    int va = *p++;
    int vb = *p++;
    if (va <= vb) {
      if (va < min_v) min_v = va; 
      if (vb > max_v) max_v = vb;
    } else {
      if (vb < min_v) min_v = vb;
      if (va > max_v) max_v = va;
    }
  }
  
  max_value = max_v;
  min_value = min_v;
}

void solve_3c(const int arr[],max_v;
  size_t t = (len - 1u) % 2u;
  if (arr[0] <= arr[t]) { min_v = arr[0];  max_v = arr[t]; }
  else { min_v = arr[t];  max_v = arr[0]; }
  
  
  for (const int *p = arr + t + 1; p < arr + len; p += 2) { // p 和 arr + len 奇偶性始终相同
    int va = *p;
    int vb = *(p + 1);
    if (va <= vb) {
      if (va < min_v) min_v = va; 
      if (vb > max_v) max_v = vb;
    } else {
      if (vb < min_v) min_v = vb;
      if (va > max_v) max_v = va;
    }
  }
  
  max_value = max_v;
  min_value = min_v;
}


static void solve_4a_(const int arr[],size_t low,size_t high,int& max_value)
{
  if (high - low <= 1u) {
    if (arr[low] <= arr[high]) { min_value = arr[low];  max_value = arr[high]; }
    else { min_value = arr[high];  max_value = arr[low]; }
    return;
  }
  
  size_t mid = low + (high - low) / 2u;
  int min_left,max_left;
  solve_4a_(arr,low,mid,min_left,max_left);
  
  int min_right,max_right;
  solve_4a_(arr,mid + 1,high,min_right,max_right);

  min_value = std::min(min_left,min_right);
  max_value = std::max(max_left,max_right);
}


void solve_4a(const int arr[],int& max_value)
{
  return solve_4a_(arr,len - 1u,min_value,max_value);
}


struct Range{
  int min_v,max_v;
  Range(int x,int y):min_v(x),max_v(y) {}
};


static Range solve_4b_(const int arr[],size_t high)
{
  if (high - low <= 1) {
    if (arr[low] <= arr[high]) return Range(arr[low],arr[high]);
    return Range(arr[high],arr[low]);
  }
  size_t mid = low + (high - low) / 2u;
  Range left = solve_4b_(arr,mid);
  Range right = solve_4b_(arr,high);
  return Range(std::min(left.min_v,right.min_v),std::max(left.max_v,right.max_v));
}

void solve_4b(const int arr[],int& max_value)
{
  Range value =  solve_4b_(arr,len - 1);
  min_value = value.min_v;
  max_value = value.max_v;
}

static void solve_4c_(const int *low,const int *high,int& max_value)
{
  if (high - low <= 1) {
    if (*low <= *high)  { min_value = *low; max_value = *high; }
    else { min_value = *high; max_value = *low; }
return;
  }
  const int *mid = low + (high - low) / 2u;
  int min_left,max_left;
  solve_4c_(low,max_right;
  solve_4c_(mid + 1,max_right);
  
  min_value = std::min(min_left,max_right);
}


void solve_4c(const int arr[],int& max_value)
{
  return solve_4c_(arr,arr + len - 1,max_value);
}


static Range solve_4d_(const int *low,const int *high)
{
  if (high - low <= 1) {
    if (*low <= *high) return Range(*low,*high);
    return Range(*high,*low);
  }
  const int* mid = low + (high - low) / 2u;
  Range left = solve_4d_(low,mid);
  Range right = solve_4d_(mid + 1,right.max_v));
}

void solve_4d(const int arr[],int& max_value)
{
  Range value =  solve_4d_(arr,arr + len - 1);
  min_value = value.min_v;
  max_value = value.max_v;
}




template<typename T>
void run_test(T arr[],size_t len,int input[],size_t input_len)
{
  int min_value,max_value;
  for (size_t i = 0; i < len; ++i) {
    printf("%d %-20s  ",i,arr[i].str);
    unsigned ta = mclock();
    for (size_t j = Pack; j != 0; --j)
      arr[i].func(input,input_len,max_value);
    ta = mclock() - ta;
    printf("min/max: %d/%d   elapsed: %u ms/n",max_value,ta / Pack);
  }
  printf("/n");
}

struct Func {
  void (*func)(const int arr[],int& max_value);
  const char *str; 
}; 
  
struct Generator {
  int operator()() const { return (rand() << 15) + rand(); }
};
  
void test()
{
  const size_t N = Length;
  if (Fix_M == 0 || N < 100) return;
  const Func func[] = {
    { solve_1a," 1a 两次遍历" },{ solve_1b," 1b 两次遍历（优化）" },{ solve_2a," 2a 一次遍历" },{ solve_2b," 2b 一次遍历（优化）" },{ solve_3a," 3a 取头尾两元素" },{ solve_3b," 3b 取相邻两元素" },// { solve_3c," 3c 取相邻两元素2" },#if ! TEST_CASE
    { solve_4a," 4a 分治法" },{ solve_4b," 4b 分治法（优化）" },// { solve_4c," 4c 分治法2" },//
    // { solve_4d," 4d 分治法（优化2）" },// 用指针，速度会稍快点
#endif

  };
  
  const size_t func_len = sizeof(func) / sizeof(func[0]);
  std::vector<int> src(N);
  for (size_t i = 0; i < N; ++i) src[i] = i; 
  
#if ! TEST_CASE  
  printf(" 递增  pos: 0  len:%u/n",N);
  run_test(func,func_len,&src[0],N);
  for (size_t i = 0; i < N; ++i) src[i] = N - i; 
  printf(" 递减  pos: 0  len:%u/n",N);
#endif  
  
  // srand(time(NULL));
  
  for (unsigned i = 0; i < Fix_M; ++i) {
  #if RANDOM_SHUFFLE
    std::random_shuffle(src.begin(),src.end());
  #else
    std::generate(src.begin(),src.end(),Generator());
  #endif
    printf (" 乱序%d pos: 0  len %u/n",i + 1,N);
    run_test(func,N);
  }
 
#if TEST_RAND_POS 
  const unsigned sub_len = N / 4u;
  const unsigned max_pos = N  - sub_len;
  for (unsigned i = 0; i < Rand_M; ++i) {
    size_t pos = rand() % max_pos;
    printf (" 乱序 pos: %u   len %u/n",pos,sub_len);
    run_test(func,&src[pos],sub_len);  
  }
#endif  

}


int main()
{
  const HANDLE handle = GetCurrentProcess();
  SetPriorityClass(handle,REALTIME_PRIORITY_CLASS);
  SYSTEM_INFO info;
  GetSystemInfo(&info);
  const int num = info.dwNumberOfProcessors;
  if (num > 1) SetProcessAffinityMask(handle,num); 
  test();
}