前言：趁着京东618，也疯狂的剁手了一回，狂买了几本编程相关的书籍。从12年开始接触编程，一直到现在，断断续续的也学习了4，5种语言，像什么C/C++/C#，Object-C, Java, PHP等。不过一直以来的目的主要都是为了工作，需要什么学习什么，没有什么具体的目标，或者说没有深入的去研究一下算法，编程思想之类的。刚好，最近的工作不是很饱和，就找一些相关的书籍充实一下自己，提高一下。目前到手的有《编程珠玑》，《代码的整洁之道》，《计算机程序设计》等，现在就讲讲读后感，或者说一些习题的代码实现等。
第一章
主要是一些基础性的介绍，其中涉及到的问题也就是一个排序，如何使用最短的时间，最小的空间，去完成一个大型的整形数组的排序。
具体问题如下
题目：一个最多包含n个正整数的文件，每个数都小于n，其中n=10^7,且所有正整数都不重复。求如何将这n个正整数升序排列。
约束：最多有1MB的内存空间可用，有充足的磁盘存储空间。
方法1（多通道法）:
第1遍遍历文件，将文件中范围在1~ 249 999的正整数读取进入1MB内存，排序（可以使用各种排序方法），将排序后的正整数存储在磁盘文件temp中
第2遍遍历文件，将文件中范围在250 000~499 999的正整数读取进入1MB内存，排序，将排序后的正整数加入存储在磁盘文件temp中
….
第40遍遍历文件，将文件中范围在10^7-250 000~10^7的正整数读取进入1MB内存，排序，将排序后的整数加入存储在磁盘文件temp中
输出temp文件
方法2（位图法）：
我们想使用hash映射，将对应的正整数映射到位图集合中。即将正整数映射到bit集合中，每一个bit代表其映射的正整数是否存在。
比如{1，2，3，5，8，13}使用下列集合表示：
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
我们可以使用具有10^7位的字符串来表示这个文件。其中，当且仅当整数i在文件中存在时候，第i位为1
接着，我们来完成具体的方法实现，首先我们约束一些基本的全局变量
// int 类型有4个字节，即32位
#define BITSPERWORD 32
// 定义右移的位数（即除以32，表示右移5位）
#define SHIFT 5
// 16进制31 二进制的话就是 0001 1111
#define MASK 0x1F
// 整数的最大值
#define N 10000000
// 最大数量
#define K 1000000
/// 大型数组必须是全局变量，或者使用static，vector修饰，否则会直接报错，栈的空间不够用
// 存放输入数据，即随机整数数组
int a[N];
// 位图排序使用的数组
int sortBit[1 + N/BITSPERWORD];
在完成具体的排序工作之前，我们还有一个准备工作需要完成，就是实现一个随机整数的数组获取。
/*
* 交换两个数组内元素位置
*/
void swap(int *a, int *b)
{
if(*a != *b){ // 异或操作 交换两个数字的位置
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
}
/******************************************************************************
*函数名称：void generateDiffRandV1(int a[], int n)
*函数功能：产生互不相同的随机数
*入口参数：
*返 回 值：无
*备 注：以空间换时间
*******************************************************************************/
void generateDiffRandV1(int a[], int n, int k)
{
int i;
time_t t;
for (i = 0; i < n; i++){
a[i] = i;
}
srand((int)time(&t));
for (i = 0; i < k; i++){
swap(&a[i], &a[i+rand()%(n-i)]);
}
}
/******************************************************************************
*函数名称：void generateDiffRandV2(int a[], int n)
*函数功能：产生互不相同的随机数(产生随机数的范围是1~n-1)
*入口参数：
*返 回 值：无
*
*思 路：先生成一个放置座号的数组，然后从中随机抽取，抽取后为防止重复，立即归零。
* ：每次生成座号，只需判断是否为0 即可，大大提高了程序执行的效率。
*******************************************************************************/
void generateDiffRandV2(int a[], int n)
{
int *flag =(int *)malloc(sizeof(int) * n);
static int flag_once = 0;
int i, index;
for(i = 0; i < n; i++)
flag[i] = i+1;
if(!flag_once){
srand((unsigned)time(0));
flag_once = 1;
}
for(i = 0; i < n;){
index = rand() % n;
if(flag[index] != 0){
a[i++] = flag[index]-1;
flag[index] = 0;
}
}
free(flag);
}
- 第一种情况：该数组中每一个数字最多出现一次
通过构建新的整形数组，来存放相关的位图信息。
整形的长度为4个字节，即32位，则数组长度为N/32 + 1。而每一个整形元素都可以表示相对应的区间内，数字是否存在。比如说待排序集合
{1,2,3,5,8,13}可以表示为：0-1-1-1 0-1-0-0 1-0-0-0 0-1-0-0，在整形数组中，则表示为8494,0-0-1-0 0-0-0-1 0-0-1-0 1-1-1-0。这个时候，我们就需要查找该位置对应的数组里面的位置。首先，i/32（从位图的方面理解就是，i>>5，向右位移5位），即表示在数组中的下标。然后i%32，对32取余（位图算法就表示i & 0x1F），获取他在整形的二进制文件中的位置，得到结果后，设为1。
比如13，二进制位0001 0101， 右移5位，结果为0，则该位图信息应该存放在sortBit[0]，同时，13对32取模，即余数为13，位图运算为0001 0101 & 1111 1111 = 0001 0101，即在13位我们需要设置为1，那么，将1左移到13位，即0000 0001 << 0001 0101 = 0010 0000 0000 0000假设之前的位图信息为0-0-0-0 0-0-0-1 0-0-1-0 1-1-1-0，即表示1，2，3，5，8存在，两者取或，0-0-1-0 0-0-0-0 0-0-0-0 0-0-0-0 | 0-1-1-1 0-1-0-0 1-0-0-0 0-0-0-0 = 0-0-1-0 0-0-0-1 0-0-1-0 1-1-1-0
具体的代码如下：
/*
* 设置对应的位置为1
*/
void set(int i) {
/// i & MASK 相当于 除以32然后取余
sortBit[i>>SHIFT] |= (1<<(i & MASK));
}
/*
* 初始化数据为0
*/
void clr(int i) {
/// i & MASK 相当于 除以32然后取余
sortBit[i>>SHIFT] &= ~(1<<(i & MASK));
}
/*
* 查找该数字是否存在
*/
int test(int i) {
/// i & MASK 相当于 除以32然后取余
return sortBit[i>>SHIFT] & (1<<(i & MASK));
}
通过C++的bitset来完成
// 导入相关类库
#include <bitset>
void sortByBitSet(int size) {
int n = 0;
// 位数可以多1位，避免数据丢失
bitset<1 + N> bit; //初始默认所有二进制位为0
while(n < size)
{
bit.set(a[n], 1); //将第n位置1
n ++;
}
for(int i = 0; i <= size + 1; i++)
{
if(bit[i] == 1)
cout << i << " ";
}
cout << endl;
}
