《算法导论》第一部分 C++综合实现

1.将第二章和第五章正文和部分习题讲到的算法用C++实现并整理到一个程序中，不同算法使用不同函数即可。
2.程序功能：输入任意个整数的序列，生成一个均匀随机排列。
2.使用vector作数据容器。
 
第二章 算法入门
2.1 插入排序 -> insertSort()
2.3 分治法 -> mergeSortByPri()
习题 2.3-2 分治法中哨兵的使用
    算法一：使用哨兵 -> mergeWithSentry()
    算法二：不使用哨兵 -> mergeNoSentry()
第五章 概率分析和随机算法
5.3 随机排列数组（详见main()）
1.) 优先级排序 PERMUTE-BY-SORTING + 习题 5.3-6 两个或更多优先级相同的情况
2.) 原地排序 RANDOMIZE-IN-PLACE
 
C++ random(a, b)的方法：（random(0, 1)简化即可）
#include <time.h>
srand((unsigned int)time(0)); // 用时间设置随机数种子
rand() % (b - a) + a; // 生成[a, b]内的随机整数
第一轮随机数由时间做种，第二轮由第一轮时间做种，以此类推
#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>
using namespace std;
int creatRandomNum(int a, int b)
{
    return rand() % (b - a) + a;
}
void swapTwoNum(vector<int> &ivec, int a, int b)
{
 int temp = ivec[a];
 ivec[a] = ivec[b];
 ivec[b] = temp;
}
// 使用哨兵
void mergeWithSentry(vector<int> &numBox, vector<int> &priBox, int begin, int middle, int end)
{
 int n1 = middle - begin + 1;
 int n2 = end - middle;
 vector<int> priL, priR, numL, numR;
 for (int i = 0; i < n1; i++) {
  priL.push_back(priBox[begin + i]);
        numL.push_back(numBox[begin + i]);
 }
 for (int j = 0; j < n2; j++) {
  priR.push_back(priBox[middle + j + 1]);
  numR.push_back(numBox[middle + j + 1]);
 }
 priL.push_back(INT_MAX);
 priR.push_back(INT_MAX);
 for (int i = 0, j = 0, k = begin; k <= end; k++) {
  if (priL[i] <= priR[j]) {
   priBox[k] = priL[i];
   numBox[k] = numL[i++];
  } else {
   priBox[k] = priR[j];
   numBox[k] = numR[j++];
  }
 }
}
// 不使用哨兵
void mergeNoSentry(vector<int> &numBox, vector<int> &priBox, int begin, int middle, int end)
{
 int n1 = middle - begin + 1;
 int n2 = end - middle;
 vector<int> priL, priR, numL, numR;
 for (int i = 0; i < n1; i++) {
  priL.push_back(priBox[begin + i]);
  numL.push_back(numBox[begin + i]);
 }
 for (int j = 0; j < n2; j++) {
  priR.push_back(priBox[middle + j + 1]);
  numR.push_back(numBox[middle + j + 1]);
 }
 for (unsigned int i = 0, j = 0, k = begin; k <= (unsigned)end; k++) {
  // 先判断是否有排完的情况，否者会造成vector的subscript越界
  if (j == priR.size() && i < priL.size()) { // 左边未完右边已完
   priBox[k] = priL[i];
   numBox[k] = numL[i++];
  } else if (i == priL.size() && j < priR.size()) { // 右边未完左边已完
   priBox[k] = priR[j];
   numBox[k] = numR[j++];
  } else if (priL[i] < priR[j]) { // 两边都未完，直接比大小
   priBox[k] = priL[i];
   numBox[k] = numL[i++];
  } else if (priR[j] < priL[i]) {
   priBox[k] = priR[j];
   numBox[k] = numR[j++];
  }
 }
}
void mergeSortByPri(vector<int> &numBox, vector<int> &priBox, int begin, int end)
{
 if (begin < end) {
  int middle = (begin + end) / 2;
  mergeSortByPri(numBox, priBox, begin, middle);
  mergeSortByPri(numBox, priBox, middle + 1, end);
  // have哨兵
  mergeWithSentry(numBox, priBox, begin, middle, end);
  // no哨兵
  // mergeNoSentry(numBox, priBox, begin, middle, end);
 }
}
void insertSort(vector<int> &numBox, vector<int> &priBox)
{
 vector<int>::size_type length = priBox.size();
 int priKey, numKey;
 for (unsigned int i, j = 1; j < length; j++) {
  priKey = priBox[j];
  numKey = numBox[j];
  // insert a[j] into the sorted sequence a[1..j-1]
  i = j - 1;
  // 线性查找
  while (i >= 0 && priBox[i] > priKey) {
   priBox[i + 1] = priBox[i];
   numBox[i + 1] = numBox[i];
   i--;
  }
  priBox[i + 1] = priKey;
  numBox[i + 1] = numKey;
 }
}
int main()
{
 srand((unsigned int)time(0));
 vector<int> numBox, priBox;
 int num;
 while (cin >> num)
  numBox.push_back(num);
 /*
     随机排列数组 算法一：优先级排序 (permute-by-sorting)
     为每个元素 numBox[i] 赋一个随机的优先级 priBox[i]，然后根据优先级对数组中的元素进行排序
 */
 vector<int>::size_type length = numBox.size();
 for (unsigned int i = 0; i < length; i++) { // 处理两个或更多优先级相同的情况
  num = creatRandomNum(1, length * length * length);
  int flag = 1;
  while (flag)
   for (vector<int>::iterator iter = numBox.begin(); iter != numBox.end();iter++)
    if (*iter == num) {
     num = creatRandomNum(1, length * length * length);
     break;
    } else if (iter + 1 == numBox.end()) {
     flag = 0;
     break;
    }
  priBox.push_back(num);
 }
 /*
     排序算法一：分治递归法 (merge-sort)
     时间复杂度：Θ(nlgn)
 */
 mergeSortByPri(numBox, priBox, 0, length - 1);
 /*
     排序算法二：线性查找插入排序 (insertion-sort)
     时间复杂度：Θ(n^2)
 */
 // insertSort(numBox, priBox);
 /*
     随机排列数组 算法二：原地排列 (randomize-in-place)
     在第i次迭代时，元素 numBox[i] 是从元素 numBox[i] 到 numBox[length - 1] 中随机选取的
     时间复杂度：O(n)
 */
 /*for (int i = 0;i < length - 1; i++)
  swapTwoNum(numBox, i, creatRandomNum(i, length - 1));*/
    for (vector<int>::iterator iter = numBox.begin(); iter != numBox.end(); ++iter)
  cout << *iter << " ";
 cout << endl;
 system("pause");
 return 0;
}
原文链接：http://www.yekezhong.com/archives/310