学习总结第三十天——归并排序与随机背包

随机背包，顾名思义，是一种随机化的背包。这个背包在与普通背包不同之处在于，每次遍历的顺序都是不一样的。在C++中我们可以通过控制begin函数来使背包进行随机化，这里同时也用到了Fisher–Yates shuffle算法，其核心思想就是从最后一项开始遍历，让每个元素和他本身或前面的一个元素随机交换位置。其代码如下

#include <iostream>
#include <cstdlib>
#include <ctime>

#ifndef INIT_SIZE
#define INIT_SIZE 10
#endif

template <typename T> inline void swap(T &a,T &b)
{
  T temp = a;
  a = b;
  b = temp;
}

template <typename T> class RandomBag
{
public:
  RandomBag();

  bool is_empty();
  int size();
  void add(T data);

  T* begin();
  T* end();

  ~RandomBag();
private:
  T *datas;
  int now_size;
  int max_size;
  void fy_sort();
  void resize(int new_size);
};

template <typename T> void RandomBag<T>::resize(int new_size)
{
  T *new_datas = new T[new_size];
  for (int i=0;i < this->now_size;i++)
  {
    new_datas[i] = this->datas[i];
  }
  delete this->datas;
  this->datas = new_datas;
}

template <typename T> RandomBag<T>::RandomBag()
{
  this->max_size = INIT_SIZE;
  this->now_size = 0;
  this->datas = new T[this->now_size];
}

template <typename T> bool RandomBag<T>::is_empty()
{
  return bool(this->now_size);
}

template <typename T> int RandomBag<T>::size()
{
  return this->now_size;
}

template <typename T> void RandomBag<T>::add(T data)
{
  if (now_size >= max_size)
  {
    this->resize(this->max_size*2);
  }
  this->datas[this->now_size++] = data;
}

template <typename T> void RandomBag<T>::fy_sort()
{
  int i = this->now_size;
  int index;
  if (this->now_size == 0)
  {
    return;
  }
  while (i--) {
    index = rand() % (i+1);
    swap (this->datas[i], this->datas[index]);
  }
}

template <typename T> T* RandomBag<T>::begin()
{
  this->fy_sort();
  return &(this->datas[0]);
}

template <typename T> T* RandomBag<T>::end()
{
  return &(this->datas[this->now_size]);
}

template <typename T> RandomBag<T>::~RandomBag()
{
  delete this->datas;
}

int main(int argc, char const *argv[]) {
  srand (time(NULL));
  RandomBag<int> bag;
  bag.add(3);
  bag.add(7);
  bag.add(2);
  bag.add(1);
  for (auto a : bag)
  {
    std::cout << a << std::endl;
  }
  return 0;
}

归并排序，是一种在元素较少时效率很高的排序算法，其核心思想为将大数组的排序转换为将两个已排序的数组合并问题，如下图所示

由Swfung8 - 自己的作品，CC BY-SA 3.0

该算法的实现示例如下：

#include <iostream>

template <typename T>void merge_sort(T *arr,int len)
{
if (len < 2)
{
  return;
}
T *left_arr = arr;
int left_len = len/2;
T *right_arr = arr+left_len;
int right_len = len-left_len;
merge_sort(left_arr, left_len);
merge_sort(right_arr, right_len);
int left_index = 0, right_index = 0, temp_index = 0;
T temp[len];
while (left_index < left_len && right_index < right_len)
{
  if (left_arr[left_index] > right_arr[right_index])
  {
    temp[temp_index++] = left_arr[left_index++];
  }
  else
  {
    temp[temp_index++] = right_arr[right_index++];
  }
}
while (left_index < left_len)
{
  temp[temp_index++] = left_arr[left_index++];
}
while (right_index < right_len)
{
  temp[temp_index++] = right_arr[right_index++];
}
for (int i = 0;i < len;i++)
{
  arr[i] = temp[i];
}
}

int main(int argc, char const *argv[]) {
int arr[10]={2,4,6,3,1,3,76,12,634,21};
merge_sort(arr,10);
for (auto i : arr)
{
  std::cout << i <<std::endl;
}
return 0;
}