KJHの博客

1、标志寄存器Flag

Flag是16位的寄存器，有9个标志位，其中6个状态标志位，3个控制标志位

CPAZSO 对应为0 2 4 6 7 11

2、6个状态标志位

CF：进位或者借位 D7或者D15有进位或者借位时CF=1，并且debug显示为CY

否则CF=0，debug显示为NC

PF：奇偶标志位 运算结果低8位（AL AH等） 化为2进制 为奇数个1时PF=0 debug显示 PO

否则 偶数个1时PF=1 debug显示PE

AF:辅助进位标志 运算结果的低4位向前1位有进位或者借位时 AF=1，debug显示AC

否则无进位和借位时AF=0,debug显示NA

KMP算法是通过分析模式字符串，预先计算每个位置发生不匹配的时候，所需GOTO的下一个比较位置，整理出来一个next数组，然后在上面的算法中使用。

简单的说来，原始的字符串匹配算法是将子串中的字符一个一个的同母串进行比较，如果相同则向前推移比较下一位，如果遇到不相同的，则将字串的第一个字符同上次字串与母串比较位置的下一个位置字符进行比较。时间复杂度为O(nm)。

1
2
3
4
5
6
7
8
9
10

/*
假定字符串在数组中：char S[n]，
模式串在另一数组中：char T[m]
*/
for (int i = 0; S[i] != '\0'; ++i)
{
	for (int j = 0; S[i + j] != '\0' && T[j] != '\0' && S[i + j] == T[j]; ++j);
	if ('\0' == T[j])
		//found a match
}

即失配时，子串要回溯要起点，母串也要回溯与子串相等的长度，然后对下一个位置开始进行匹配。下面这样一种情况

针对前面讨论的八大经典排序算法：冒泡排序、插入排序、选择排序、堆排序、归并排序、快速排序、希尔排序、桶排序。

关于各种什么时间复杂度，空间复杂度的对比总结，网上一大堆，别人也总结的很好，这里就不赘述了，这里主要通过对大量数据进行排序测试，测试各排序算法的运行时间，来比较各排序之间优劣（时间上）。

先贴出测试程序：最后会给出各数据量的情况下，各算法的运行时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

typedef void(*SortFun)(int Arr[], int length);  //函数指针

double SortTest(SortFun fp)
{
	int Arr[LENGTH];
	for (int i = 0; i < LENGTH; ++i)
		Arr[i] = rand() % MAXNUM;
	clock_t beginTime = clock();
	fp(Arr, LENGTH);
	double diffTime = double(clock() - beginTime) / CLOCKS_PER_SEC;

	return diffTime;

}

上面的 LENGTH 和 MAXNUM 宏定义在另外一个头文件中（因为桶排序中需要用到 MAXNUM），LENGTH 为待排数据的量，MAXNUM 为待排数据数值的最大值。
为了方便调用函数指针，这里在原排序程序的基础上添加了一个通用的函数接口。为方便理解，这里重新贴出各排序程序

桶排序假设待排序的一组数统一的分布在一个范围中，然后设定对应数据数量的桶，待排序的一组数，分别对应算式处理归入这些子桶，并将桶中的数据进行排序，最后将各个桶中的数据有序的合并起来。

通俗的说，就是通过某个公式将待排序的一组数分为几个子范围，然后归入到对应的子桶，这样必然会有不一样的数据经过算式处理后对应同一个桶，我们可通过简单比较将对应同一个桶的不同数据排序，最后各个数据处理完后，有的桶为空，有的桶有多个数据（已排序好），这样我们就可以逐个的遍历桶，然后将数据依次放入原数组中，这样就完成了排序。

​

上面模型和哈希表的分离链接法很相似。这里不同数据对应同一个桶的插入是通过链表来存储的。

这里给出一个演示：Bucket Sort Visualization

根据上面算法模型和演示，给出代码：上面的图示模型和演示链表是带有表头的，这样是为了方便执行删除操作，但是我们这里仅作为排序，无需删除操作，所以链表是不带有表头的，这样既简化了问题又节省了空间。

快速排序也是采用分治法，将问题化整归零来处理。

步骤为：

1. 从数列中调出一个元素，称为 “基准”（pivot）；

2. 重新排序数列，排序规则就是将数列中比基准值大的放在基准的后面，将比基准值小的放在基准的前面，在这个分区退出之后，该基准就处于数列的中间位置（非绝对中间位置），这个称为分区操作；

3. 递归地把小于基准值元素的子数列和大于基准值元素的子序列排序。递归的终止条件就是数列的大小是零或一，也就是都已经被排序好了。

通俗点说就是，

1. 先从数列中取出一个数作为基准；

2. 分区过程，将比这个数大的数全部放到它的右边，小于或等于它的数全放到它的左边；

3. 对左右分区重复第 2 步，直到各分区只有一个数或没有数据。

具体流程参见下图（这里以数列的首元素作为基准）：