算法珠玑

文章目录
  1. 排序
    1. 稳定性
    2. 位排序
  2. 随机数

查了相关资料说这是一本非常好的算法入门书, 于是买来学习一下, 记录学习过程中的一些扩展知识点以及关于课后习题的思考

参考书 : 编程珠玑(第2版•修订版)

算法可视化工具VisuAlgo

每一种算法都有自己的使用条件, 根据不同的问题具体分析, 比如对于输入比较小的问题, 是否可以将文件加载进内存排序而不是在磁盘上排序, 任何算法都是对于某一类问题的权衡, 必定要牺牲某种优势换取另一种优势, 同时应用背景还要了解应用背景, 因为不同的应用背景提出的性能需求不一样, 比如运行时间等指标; 同时, 提到算法就不能离开数据结构, 程序 = 算法+数据结构, 良好的数据结构节省时间和空间, 提高程序的可移植性和可维护性

排序

稳定性

  • 通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同

(1)冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

(2)选择排序

选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n - 1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

(3)插入排序
插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

(4)快速排序
快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j,交换a[i]和a[j],重复上面的过程,直到i > j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为5 3 3 4 3 8 9 10 11,现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j] 交换的时刻。

(5)归并排序
归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。

(6)基数排序
基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。

(7)希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小, 插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。

(8)堆排序
我们知道堆的结构是节点i的孩子为2 i和2 i + 1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列,堆排序的过程是从第n / 2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1, n / 2 - 2, … 1这些个父节点选择元素时,就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了,而第n / 2 - 1个父节点把后面一个相同的元素没 有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。

综上,得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法

位排序

问题描述 : 空间<1MB, 时间<10s

  • 输入 : 在输入的$n=10^7$个正整数中, 每个数都小于$n$是并且只出现一次,
  • 输出 : 升序排列的列表

问题分析 :

  • 在空间的限制下, 我们一次最多可以排序多少数据呢? 我们知道在基本数据类型的条件下表示数字n, 最好选择4个Byte的int类型(32bit), 因为我们希望用最少的字节数表示n($2^{32}>10^7$), 这样我们一次最多可排序$1MB/4Byte=250000$个数, 这样我们就需要$10^7/250000=40$次的IO操作, 对于加载到内存中的数据可以使用快速排序等排序方式进行排序, 这种方式的缺点很明显, 那么有没有更好的方法呢?

1MB=10^6Byte=8*10^6bit<10^7, 那么问题就是用大约800万个bit来标识1000万个数据(需要空间1.25MB)呢? 我们可以通过寻找稀疏位来实现, 但是假设现在有1.25MB空间了, 我们来看一下位排序算法

  1. 用位向量表示数据集合, 假如有正整数数据集$\{2,4,5,7,8\}$, 用位向量表示该数据集为:

    $$(01011011)_{bit}$$

    • 我们用1Byte的空间表示了上面的数据集, 也就是说在数据集中出现的数字在相应的位上标记为1, 否则标记为零, 这样我们用程序处理的时候自然也就排序了, 最后按顺序输出就可以了, 很精妙的算法!
  2. 注意:减少程序的空间需求也会减少其运行时间, 因为减少空间需求意味着需要处理的数据量变小了, 那么处理时间也会相应的减少, 还有一个原因是我们可以将数据加载进内存而不是在磁盘上操作

代码实现见Github的Programming Pearls中的bitsort.c, 代码分析见注释
测试结果:

  1. 位排序(bitsort.c):2260000ms
  2. C++的Set集合实现(sortints.cpp) : 31030000ms

位排序关键代码解析:

1
2
3
4
5
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
  • 数组a所占的空间为1250004Byte, 也就是限制在1MB左右的内存, 共包含312501个元素
1
2
3
void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); } //置1操作
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); } //置0操作
int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); } //判断是否为1
  • 1<<(i & MASK) : 将1左移(i & MASK)位, 将二进制后面添加(i & MASK)个0实现左移操作

(i & MASK)表示多少呢? : Stackoverflow的相关问题

  • i是int类型占用4Byte共32位, MASK=0x1F是两个十六进制共8位, 转化为2进制为$(00011111)_{2}$, 那么这个操作就是取i的低五位, 也就是说i的取值在[0,32]之间, 也就是说i最多左移32位, 这和int类型的大小是一致的, 即对于一个位操作是在一个整型元素内操作的, 这和我们定义的数组类型是相关的, 因为对于每一个元素来说实际操作的是32位, 其实这个操作本质上就是i % 32, 但是有一个条件i & MASK and i % 32 are the same thing as long as you're sure i is not negative, 因为我们最终想知道第i个数在a[]中某个元素的32位中的哪一位上, 所以要对32取余确定是32位的哪一位, 1<<(i & MASK)便实现了在32位的二进制中置1的操作

a[i>>SHIFT]确定了i在a[]中的哪个元素上

  • 我们知道对于二进制左移就是乘法运算, 右移就是除法运算, 那么i>>SHIFT表示将i右移5位, 也就是i/32便确定了i在a[]中的哪个元素上

a[i>>SHIFT] |= (1<<(i & MASK)); : 数组元素置1操作(set)

a[i>>SHIFT] = a[i>>SHIFT] | (1<<(i & MASK));

  • 我们知道了i在a[]中的具体元素(a[i>>SHIFT]), 也知道在该元素中的置1位置(1<<(i & MASK)), 通过或运算就将i的位置设置为1
  • 清零判定功能同理

随机数

问题描述 :

生成$[0,n-1]$之间的$k$个不同的乱序的随机整数? 假如生成一个1-10000000的随机数组,数组中的数字不能重复,但是位置是随机的

  • 输入 : 两个整数$k$和$n$, 其中$k<n$
  • 输出 : $k$个随机数

问题分析 :

为了保证不重复, 最常见的思路是生成的随机数去数组里面判断一下存在与否, 但是这样效率太低了, 对于不能重复这一点, 我们知道数组的索引肯定是不重复的, 那么我们能否利用数组的索引来生成呢, 答案是肯定的

代码实现见 gendata.cpp

关键代码分析

1
2
3
4
5
6
7
8
int randint(int l, int r){
return rand() % (r - l) + l;
}
for (int i = 0; i < N; i++)
a[i] = i;
for (int i = 0; i < K; i++)
swap(a[i], a[randint(i, N)]);
printf("%d\n", a[i]);
  • randint() : 生成了$[l,r]$之间的随机数

  • 第一个for循环生成了一个下标序列, 保证不重复

  • 第二个for循环交换了第i个元素和[i,N]之间的某一个元素, 也就是说第i个元素和该元素前面的某个元素进行随机交换, 因为都在同一个数组a[]内进行操作, 所以元素不会重复, 这样输出生成的k个不重复的值且在[0,n-1]之间