19其他算法（algo）——复杂的算法

1、一些复杂的算法

例如：lower_bound、upper_bound、binary_search、next_permutation、prev_permutation、random_shuffle、partial_sort、partial_sort_copy、sort、equal_range、inplace_merge、nth_element、merge sort等。

2、lower_bound

这是二分查找的一种版本，在已排序的[first,last)中寻找大于等于value的第一个元素，返回该元素迭代器；如果没有这样的元素存在，返回last。lower_bound的含义是最后返回的迭代器i使得[first,i)区间中的每个元素都小于value。

random_access_iterator_tag简化版本：

template <class RandomAccessIterator, class T, class Distance>
RandomAccessIterator __lower_bound(RandomAccessIterator first,
                                   RandomAccessIterator last, const T& value,
                                   Distance*, random_access_iterator_tag) {
  Distance len = last - first;
  Distance half;
  RandomAccessIterator middle;
  --last;
  while (first < last) {
    half = len >> 1;
    middle = first + half;
    if (*middle < value) {
      first = middle + 1;
      len = len - half - 1;
    }
    else
      last = middle;
  }
  return first;
}

template <class ForwardIterator, class T, class Distance>
ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last,
                              const T& value, Distance*,
                              forward_iterator_tag) {
  Distance len = 0;
  distance(first, last, len);
  Distance half;
  ForwardIterator middle;

  while (len > 0) {
    half = len >> 1;
    middle = first;
    advance(middle, half);
    if (*middle < value) {
      first = middle;
      ++first;
      len = len - half - 1;
    }
    else
      len = half;
  }
  return first;
}

template <class RandomAccessIterator, class T, class Distance>
RandomAccessIterator __lower_bound(RandomAccessIterator first,
                                   RandomAccessIterator last, const T& value,
                                   Distance*, random_access_iterator_tag) {
  Distance len = last - first;
  Distance half;
  RandomAccessIterator middle;

  while (len > 0) {
    half = len >> 1;
    middle = first + half;
    if (*middle < value) {
      first = middle + 1;
      len = len - half - 1;
    }
    else
      len = half;
  }
  return first;
}

template <class ForwardIterator, class T>
inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
                                   const T& value) {
  return __lower_bound(first, last, value, distance_type(first),
                       iterator_category(first));
}

3、upper_bound

这是二分查找的一种版本，在已排序的[first,last)中寻找大于value的第一个元素，返回该元素迭代器；如果没有这样的元素存在，返回last。upper_bound的含义是最后返回的迭代器i使得[i,last)区间中的每个元素都大于value。

random_access_iterator_tag简化版本：

template <class RandomAccessIterator, class T, class Distance>
RandomAccessIterator __lower_bound(RandomAccessIterator first,
                                   RandomAccessIterator last, const T& value,
                                   Distance*, random_access_iterator_tag) {
  Distance len = last - first;
  Distance half;
  RandomAccessIterator middle;
  --last;
  while (first < last) {
    half = len >> 1;
    middle = first + half;
    if (*middle <= value) {
      first = middle + 1;
      len = len - half - 1;
    }
    else
      last = middle;
  }
  return first;
}

template <class ForwardIterator, class T, class Distance>
ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last,
                              const T& value, Distance*,
                              forward_iterator_tag) {
  Distance len = 0;
  distance(first, last, len);
  Distance half;
  ForwardIterator middle;

  while (len > 0) {
    half = len >> 1;
    middle = first;
    advance(middle, half);
    if (value < *middle)
      len = half;
    else {
      first = middle;
      ++first;
      len = len - half - 1;
    }
  }
  return first;
}

template <class RandomAccessIterator, class T, class Distance>
RandomAccessIterator __upper_bound(RandomAccessIterator first,
                                   RandomAccessIterator last, const T& value,
                                   Distance*, random_access_iterator_tag) {
  Distance len = last - first;
  Distance half;
  RandomAccessIterator middle;

  while (len > 0) {
    half = len >> 1;
    middle = first + half;
    if (value < *middle)
      len = half;
    else {
      first = middle + 1;
      len = len - half - 1;
    }
  }
  return first;
}

template <class ForwardIterator, class T>
inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
                                   const T& value) {
  return __upper_bound(first, last, value, distance_type(first),
                       iterator_category(first));
}

4、binary_search

二分查找，在已排序的[first,last)中寻找元素value，如果区间内有等同于value的元素，便返回true，否则返回false。binary_search调用lower_bound函数即可，最后的迭代器所指元素是否等于value即可。

template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
                   const T& value) {
  ForwardIterator i = lower_bound(first, last, value);
  return i != last && !(value < *i);
}

template <class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value,
                   Compare comp) {
  ForwardIterator i = lower_bound(first, last, value, comp);
  return i != last && !comp(value, *i);
}

5、next_permutation

STL提供了两个排列组合关系的算法，分别是next_permutation和prev_permutation，分别返回的是下一个排列组合和前一个排列组合。比如序列{a,b,c}按字典顺序可能的排列组合：abc,acb,bac,bca,cab,cba。

next_permutation()会取得[first,last)所标示的序列的下一个排列组合，如果没有下一个排列组合，返回false，否则返回true。

算法思想：从最尾端开始往前寻找相邻的两个元素*i和*ii满足*i<*ii，找到这样一组相邻元素后，再从尾端开始往前检验，找出第一个大于*i的元素*j，交换i和j的值，再将ii之后的所有元素颠倒排序，此时的序列就是所求的下一个排列组合。

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
                      BidirectionalIterator last) {
  if (first == last) return false;
  BidirectionalIterator i = first;
  ++i;
  if (i == last) return false;
  i = last;
  --i;

  for(;;) {
    BidirectionalIterator ii = i;
    --i;
    if (*i < *ii) {
      BidirectionalIterator j = last;
      while (!(*i < *--j));
      iter_swap(i, j);
      reverse(ii, last);
      return true;
    }
    if (i == first) {
      reverse(first, last);
      return false;
    }
  }
}

6、prev_permutation

prev_permutation()会取得[first,last)所标示的序列的前一个排列组合，如果没有前一个排列组合，返回false，否则返回true。

算法思想：从最尾端开始往前寻找相邻的两个元素*i和*ii满足*i>*ii，找到这样一组相邻元素后，再从尾端开始往前检验，找出第一个小于*i的元素*j，交换i和j的值，再将ii之后的所有元素颠倒排序，此时的序列就是所求的前一个排列组合。

template <class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first,
                      BidirectionalIterator last) {
  if (first == last) return false;
  BidirectionalIterator i = first;
  ++i;
  if (i == last) return false;
  i = last;
  --i;

  for(;;) {
    BidirectionalIterator ii = i;
    --i;
    if (*ii < *i) {
      BidirectionalIterator j = last;
      while (!(*--j < *i));
      iter_swap(i, j);
      reverse(ii, last);
      return true;
    }
    if (i == first) {
      reverse(first, last);
      return false;
    }
  }
}

7、random_shuffle

将[first,last)的元素次序随机重排，也就是说在N！种可能的元素排列顺序中随机选出一种，N=last-first。random_shuffle会产生一个均匀分布，任何一个排列被选中的几率为1/N。

template <class RandomAccessIterator, class Distance>
void __random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
                      Distance*) {
  if (first == last) return;
  for (RandomAccessIterator i = first + 1; i != last; ++i)
#ifdef __STL_NO_DRAND48
    iter_swap(i, first + Distance(rand() % ((i - first) + 1)));
#else
  iter_swap(i, first + Distance(lrand48() % ((i - first) + 1)));
#endif
}

template <class RandomAccessIterator>
inline void random_shuffle(RandomAccessIterator first,
                           RandomAccessIterator last) {
  __random_shuffle(first, last, distance_type(first));
}

template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
                    RandomNumberGenerator& rand) {
  if (first == last) return;
  for (RandomAccessIterator i = first + 1; i != last; ++i)
    iter_swap(i, first + rand((i - first) + 1));
}

8、partial_sort/partial_sort_copy

接受一个middle迭代器（位于序列[first,last)之内），然后重新排列[first,last)，使得序列中的middle-first个最小元素以递增顺序排序置于[first,middle)内，其余last-middle个元素置于[middle,last)中无任何特定顺序。如果想要使[first,last)序列中最小的N个元素以递增顺序置于[first,first+N)之内，选择partial_sort比sort效率高。

算法思想：partial_sort的任务是找出middle-first个最小元素，首先将[first,middle)序列make_heap形成大顶堆，然后循环遍历[middle,last)序列中每个元素与刚才形成的大顶堆的根节点比较，如果比根节点小，调用pop_heap函数，实际上就是交换两个元素值，并对[first,middle)序列重新调整为大顶堆，这样就保证[first,middle)序列是整个序列的最小元素，最后对[first,middle)序列调用sort_heap排序使得[first,middle)为递增序列结束。

template <class RandomAccessIterator, class T>
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
                    RandomAccessIterator last, T*) {
  make_heap(first, middle);
  for (RandomAccessIterator i = middle; i < last; ++i)
    if (*i < *first)
      __pop_heap(first, middle, i, T(*i), distance_type(first));
  sort_heap(first, middle);
}

template <class RandomAccessIterator>
inline void partial_sort(RandomAccessIterator first,
                         RandomAccessIterator middle,
                         RandomAccessIterator last) {
  __partial_sort(first, middle, last, value_type(first));
}

9、sort

STL所提供的算法中，sort()是最复杂最庞大的一个。sort算法接受两个RandomAccessIterators，然后将区间内的所有元素以递增方式由小到大重新排列。只有vector和deque容器满足是RandomAccessIterators。sort算法在数据量大时采用快速排序，分段递归排序，一旦分段的数据量小于某个门槛，为避免快速排序的递归调用带来过大的额外负担，改用Insertion Sort。

（1）Insertion Sort

Insertion Sort以双层循环形式进行，外循环遍历整个序列[first,last)，每次迭代决定出一个子区间[first,i)，内循环遍历子区间[first,i)，不断往前遍历每个元素，当遇到比*i大的元素该元素就后移，直到遇到比*i小的停止并将*i填入前一个位置。时间复杂度O(N^2)，当数据量较小时，不像快速排序的递归调用带来过大的额外负担，所以很优。

Insertion Sort算法实现优化技巧：对于内循环的时候，如果*i比第一个元素还小，直接将[first,i)区间内元素后移，*i赋值给第一个元素；否则遍历子区间[first,i)，不断往前遍历每个元素，当遇到比*i大的元素该元素就后移，直到遇到比*i小的停止并将*i填入前一个位置。这样的好处就是不用一个一个的移动，一次性移动完。

template <class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value) {
  RandomAccessIterator next = last;
  --next;
  while (value < *next) {
    *last = *next;
    last = next;
    --next;
  }
  *last = value;
}

template <class RandomAccessIterator, class T>
inline void __linear_insert(RandomAccessIterator first,
                            RandomAccessIterator last, T*) {
  T value = *last;
  if (value < *first) {
    copy_backward(first, last, last + 1);
    *first = value;
  }
  else
    __unguarded_linear_insert(last, value);
}

template <class RandomAccessIterator>
void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
  if (first == last) return;
  for (RandomAccessIterator i = first + 1; i != last; ++i)
    __linear_insert(first, i, value_type(first));
}

（2）Quick Sort

在大数据量的情况下，选择Quick Sort，Quick Sort是目前已知最快的排序法，平均时间复杂度O(nlogn)，最坏情况下达到O(n^2)，不过IntroSort可将最坏情况推进到O(nlogn)。

Quick Sort算法思想：取S中任何一个元素作为枢轴pivot，然后将S分割成L和R两段，使L内的每一个元素都小于或等于pivot，R内每一个元素都大于或等于pivot，对L和R递归执行Quick Sort，最后将每个小区间串接成大区间。

• Median-of-Three（三点中值）：任何一个元素都可以被选为作为枢轴pivot，但选的不合适会影响排序效率，最理想最稳当的方式就是取整个序列头、尾、*三个位置的元素，以其中值作为枢轴pivot。
• Partition（分割）：分割的方式很多，最简单有效的方式是将first向尾部移动，last向头部移动，当*first大于或等于pivot时就停下来，当*last小于或等于pivot也停下来，然后检验两个迭代器是否交错，如果不交错，两个元素互换，然后两个迭代器同时移动一个位置向*逼近，再继续进行相同的行为两个迭代器直至相遇。
• threshold（阈值）：当小数据量的情况下选择Insertion Sort，当大数据量的情况下选择Quick Sort，一般这个阈值在5-20左右，程序中设置__stl_threshold=16。
• introsort：Quick Sort最坏情况下达到O(n^2)，不过IntroSort可将最坏情况推进到O(nlogn)。当分割行为有恶化为二次行为的倾向时，能够自我侦测，转为Heap Sort。

template <class RandomAccessIterator, class T>
void __unguarded_insertion_sort_aux(RandomAccessIterator first,
                                    RandomAccessIterator last, T*) {
  for (RandomAccessIterator i = first; i != last; ++i)
    __unguarded_linear_insert(i, T(*i));
}

template <class RandomAccessIterator>
inline void __unguarded_insertion_sort(RandomAccessIterator first,
                                RandomAccessIterator last) {
  __unguarded_insertion_sort_aux(first, last, value_type(first));
}

template <class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first,
                            RandomAccessIterator last) {
  if (last - first > __stl_threshold) {
    __insertion_sort(first, first + __stl_threshold);
    __unguarded_insertion_sort(first + __stl_threshold, last);
  }
  else
    __insertion_sort(first, last);
}

template <class Size>
inline Size __lg(Size n) {
  Size k;
  for (k = 0; n > 1; n >>= 1) ++k;
  return k;
}

template <class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessIterator first,
                      RandomAccessIterator last, T*,
                      Size depth_limit) {
  while (last - first > __stl_threshold) {
    if (depth_limit == 0) {
      partial_sort(first, last, last);
      return;
    }
    --depth_limit;
    RandomAccessIterator cut = __unguarded_partition
      (first, last, T(__median(*first, *(first + (last - first)/2),
                               *(last - 1))));
    __introsort_loop(cut, last, value_type(first), depth_limit);
    last = cut;
  }
}

template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
  if (first != last) {
    __introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
    __final_insertion_sort(first, last);
  }
}

10、equal_range

这是二分查找的一种版本，在已排序的[first,last)中寻找等于value的区间范围，返回区间[i,j)；如果没有这样的区间存在，返回[last,last)。算法思想：只需要调用函数lower_bound找到位置i，然后调用函数upper_bound找到位置j，最后返回[i,j)。

template <class ForwardIterator, class T, class Distance>
pair<ForwardIterator, ForwardIterator>
__equal_range(ForwardIterator first, ForwardIterator last, const T& value,
              Distance*, forward_iterator_tag) {
  Distance len = 0;
  distance(first, last, len);
  Distance half;
  ForwardIterator middle, left, right;

  while (len > 0) {
    half = len >> 1;
    middle = first;
    advance(middle, half);
    if (*middle < value) {
      first = middle;
      ++first;
      len = len - half - 1;
    }
    else if (value < *middle)
      len = half;
    else {
      left = lower_bound(first, middle, value);
      advance(first, len);
      right = upper_bound(++middle, first, value);
      return pair<ForwardIterator, ForwardIterator>(left, right);
    }
  }
  return pair<ForwardIterator, ForwardIterator>(first, first);
}

template <class RandomAccessIterator, class T, class Distance>
pair<RandomAccessIterator, RandomAccessIterator>
__equal_range(RandomAccessIterator first, RandomAccessIterator last,
              const T& value, Distance*, random_access_iterator_tag) {
  Distance len = last - first;
  Distance half;
  RandomAccessIterator middle, left, right;

  while (len > 0) {
    half = len >> 1;
    middle = first + half;
    if (*middle < value) {
      first = middle + 1;
      len = len - half - 1;
    }
    else if (value < *middle)
      len = half;
    else {
      left = lower_bound(first, middle, value);
      right = upper_bound(++middle, first + len, value);
      return pair<RandomAccessIterator, RandomAccessIterator>(left,
                                                              right);
    }
  }
  return pair<RandomAccessIterator, RandomAccessIterator>(first, first);
}

template <class ForwardIterator, class T>
inline pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value) {
  return __equal_range(first, last, value, distance_type(first),
                       iterator_category(first));
}

11、inplace_merge

inplace_merge算法是将两个连接在一起的有序序列[first,middle)和[middle,last)，结合成单一一个有序序列[first,last)。

这个算法如果有额外的内存辅助，效率会好许多，但是在没有辅助的缓冲区或缓冲区不足的情况下，也可以运作。当缓冲区真的不足以容纳任何一个序列时，我们的原则是以递归分割的方式，让处理长度不断减半，看看能否容纳于缓冲区中。

原地归并排序算法递归方法（__merge_without_buffer）：对于[first,middle)和[middle,last)，长度分别是len1和len2，首先判断len1和len2哪个长，对长的那一端入手，如果len1长，找到折半点first_cut，然后在[middle,last)找到第一个大于等于*first_cut的元素为second_cut；如果len2长，找到折半点second_cut，然后在[first,middle)找到第一个大于*second_cut的元素为first_cut；然后对[first_cut,middle)和[middle,second_cut)进行rotate操作，之后分别对[first,middle)和[middle,last)调用归并函数分割点分别是first_cut和second_cut。

原地归并排序算法循环方法：对于[first,middle)和[middle,last)，首先first调用upper_bound在区间[first,middle)找到大于middle的第一个元素位置i，然后在区间[middle,last)找到大于i的第一个元素位置j，将[i,middle)和[middle,j)调用rotate旋转，++first，直到first到达last停止。其中rotate操作，只需要先将[i,middle)reverse然后将[middle,j)reverse，最后将[i,j)reverse即可。

template <class BidirectionalIterator, class Distance>
void __merge_without_buffer(BidirectionalIterator first,
                            BidirectionalIterator middle,
                            BidirectionalIterator last,
                            Distance len1, Distance len2) {
  if (len1 == 0 || len2 == 0) return;
  if (len1 + len2 == 2) {
    if (*middle < *first) iter_swap(first, middle);
    return;
  }
  BidirectionalIterator first_cut = first;
  BidirectionalIterator second_cut = middle;
  Distance len11 = 0;
  Distance len22 = 0;
  if (len1 > len2) {
    len11 = len1 / 2;
    advance(first_cut, len11);
    second_cut = lower_bound(middle, last, *first_cut);
    distance(middle, second_cut, len22);
  }
  else {
    len22 = len2 / 2;
    advance(second_cut, len22);
    first_cut = upper_bound(first, middle, *second_cut);
    distance(first, first_cut, len11);
  }
  rotate(first_cut, middle, second_cut);
  BidirectionalIterator new_middle = first_cut;
  advance(new_middle, len22);
  __merge_without_buffer(first, first_cut, new_middle, len11, len22);
  __merge_without_buffer(new_middle, second_cut, last, len1 - len11,
                         len2 - len22);
}

template <class BidirectionalIterator1, class BidirectionalIterator2,
          class Distance>
BidirectionalIterator1 __rotate_adaptive(BidirectionalIterator1 first,
                                         BidirectionalIterator1 middle,
                                         BidirectionalIterator1 last,
                                         Distance len1, Distance len2,
                                         BidirectionalIterator2 buffer,
                                         Distance buffer_size) {
  BidirectionalIterator2 buffer_end;
  if (len1 > len2 && len2 <= buffer_size) {
    buffer_end = copy(middle, last, buffer);
    copy_backward(first, middle, last);
    return copy(buffer, buffer_end, first);
  } else if (len1 <= buffer_size) {
    buffer_end = copy(first, middle, buffer);
    copy(middle, last, first);
    return copy_backward(buffer, buffer_end, last);
  } else  {
    rotate(first, middle, last);
    advance(first, len2);
    return first;
  }
}

template <class BidirectionalIterator, class Distance, class Pointer>
void __merge_adaptive(BidirectionalIterator first,
                      BidirectionalIterator middle,
                      BidirectionalIterator last, Distance len1, Distance len2,
                      Pointer buffer, Distance buffer_size) {
  if (len1 <= len2 && len1 <= buffer_size) {
    Pointer end_buffer = copy(first, middle, buffer);
    merge(buffer, end_buffer, middle, last, first);
  }
  else if (len2 <= buffer_size) {
    Pointer end_buffer = copy(middle, last, buffer);
    __merge_backward(first, middle, buffer, end_buffer, last);
  }
  else {
    BidirectionalIterator first_cut = first;
    BidirectionalIterator second_cut = middle;
    Distance len11 = 0;
    Distance len22 = 0;
    if (len1 > len2) {
      len11 = len1 / 2;
      advance(first_cut, len11);
      second_cut = lower_bound(middle, last, *first_cut);
      distance(middle, second_cut, len22);
    }
    else {
      len22 = len2 / 2;
      advance(second_cut, len22);
      first_cut = upper_bound(first, middle, *second_cut);
      distance(first, first_cut, len11);
    }
    BidirectionalIterator new_middle =
      __rotate_adaptive(first_cut, middle, second_cut, len1 - len11,
                        len22, buffer, buffer_size);
    __merge_adaptive(first, first_cut, new_middle, len11, len22, buffer,
                     buffer_size);
    __merge_adaptive(new_middle, second_cut, last, len1 - len11,
                     len2 - len22, buffer, buffer_size);
  }
}

template <class BidirectionalIterator, class T, class Distance>
inline void __inplace_merge_aux(BidirectionalIterator first,
                                BidirectionalIterator middle,
                                BidirectionalIterator last, T*, Distance*) {
  Distance len1 = 0;
  distance(first, middle, len1);
  Distance len2 = 0;
  distance(middle, last, len2);

  temporary_buffer<BidirectionalIterator, T> buf(first, last);
  if (buf.begin() == 0)
    __merge_without_buffer(first, middle, last, len1, len2);
  else
    __merge_adaptive(first, middle, last, len1, len2,
                     buf.begin(), Distance(buf.size()));
}


template <class BidirectionalIterator>
inline void inplace_merge(BidirectionalIterator first,
                          BidirectionalIterator middle,
                          BidirectionalIterator last) {
  if (first == middle || middle == last) return;
  __inplace_merge_aux(first, middle, last, value_type(first),
                      distance_type(first));
}

12、nth_element

重新排列[first,last)，使得[first,nth)区间每个元素都小于*nth，[nth,last)区间每个元素都大于等于*nth。

算法思想：不断调用快速排序里面的partition函数，使得nth左侧都小于*nth，nth右侧都大于*nth，最后调用insertion sort。

template <class RandomAccessIterator, class T>
void __nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                   RandomAccessIterator last, T*) {
  while (last - first > 3) {
    RandomAccessIterator cut = __unguarded_partition
      (first, last, T(__median(*first, *(first + (last - first)/2),
                               *(last - 1))));
    if (cut <= nth)
      first = cut;
    else
      last = cut;
  }
  __insertion_sort(first, last);
}

template <class RandomAccessIterator>
inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                        RandomAccessIterator last) {
  __nth_element(first, nth, last, value_type(first));
}

13、merge sort

调用inplace_merge函数实现归并排序。归并排序的时间复杂度是O(n*logn)，虽然时间复杂度和快速排序一样，但是归并排序需要借用额外的O(n)空间复杂度，所以归并排序效率比不上快速排序。但是实现简单、概念简单是归并排序最大的两个优点。