您现在的位置是：首页 >其他 >轻量级C通用库Klib解读 —— ksort网站首页其他

前言

Klib是一个独立的轻量级c通用库，里面大多数组件除了C标准库外不包含外部库，想用对应组件直接拷贝对应文件即可使用。
该库致力于高效和较小的内存占用，其中部分组件（如khash、kbtree、ksort、kvec），无论是内存还是速度方面，都是所有编程语言中相似算法或数据结构最高效的实现之一。

ksort

各种排序集合啦，源代码在这里
因为每个算法的原理其他地方都讲的比较清楚了，如果实现流程跟其他地方一致的话我这里就不再赘述了，可能只会提一下一些实现上的小细节
定义宏KSORT_INIT

#define KSORT_INIT(name, type_t, __sort_lt)	...

• type_t：元素类型
• __sort_lt：元素比较函数bool (*)(type_t a, type_t b)

定义内置类型比较方便的宏

• KSORT_INIT_GENERIC：name跟值类型一致（比如都设置为int）
• KSORT_INIT_STR：name为str，值类型为const char *

#define KSORT_INIT_GENERIC(type_t) KSORT_INIT(type_t, type_t, ks_lt_generic)
#define KSORT_INIT_STR KSORT_INIT(str, ksstr_t, ks_lt_str)

#define ks_lt_generic(a, b) ((a) < (b))
#define ks_lt_str(a, b) (strcmp((a), (b)) < 0)

注：以下所有排序API的n、a含义都一样

• n：数组长度
• a：待排序数组

归并排序：ks_mergesort

复杂度：时间O(nlogn)，空间O(n)，稳定排序
菜鸟上的原理、动图讲解、源代码实现，更加清晰易懂，不清楚原理的可先看这里

#define ks_mergesort(name, n, a, t) ks_mergesort_##name(n, a, t)

• t：临时数组，长度需至少为n，可传入0

本代码的小细节：

1. 用指针操作*p++ = *j++替换索引操作b[k++] = a[start1++]：可能小距离的++相比从数组头的偏移更快捷？
2. 用二维数组type_t *a2[2]的索引交换curr = 1 - curr; a = a2[curr]; b = a2[1 - curr]替换指针交换

梳排序：ks_combsort

复杂度：冒泡排序的优化版本，但最差时间仍是O(n²)，空间O(1)，不稳定排序
某度上的原理讲解得挺清楚的了，可看这里

#define ks_combsort(name, n, a) ks_combsort_##name(n, a)

算法基本就是原理的直接实现

• 当间隔为9或10时直接设置为11
• 最后如果gap不为1则用插入排序做验证

堆排序：ks_heapmake、ks_heapsort

复杂度：时间O(nlogn)，空间O(1)，不稳定排序
菜鸟上的动图讲解、源代码实现，更加清晰易懂，不清楚原理的可先看这里

#define ks_heapsort(name, n, a) ks_heapsort_##name(n, a)
#define ks_heapmake(name, n, a) ks_heapmake_##name(n, a)

算法细节：

• 用输入的数组构建堆（完全二叉树）的过程，实际并不是去创建一个新的二叉树结构，而是利用下面的原理去读取与遍历数组，保证每对父节点与子节点之间都满足相同的关系，这样每次取堆顶元素都是最大/最小元素
  • 以广度优先的方式遍历一棵完全二叉树把节点按顺序排入数组，假设父节点的索引为i，则它的两个子节点索引分别为2 * i + 1和2 * i + 2
• 调整父节点的过程（ks_heapadjust），每次调用其实只是为了找到一个节点的放置位置，但最多可能会调整logn个节点

  #define ks_heapadjust(name, i, n, a) ks_heapadjust_##name(i, n, a)
  

本代码的小细节：

1. 代码实现与菜鸟上的基本一致，ks_heapadjust对应C实现的max_heapify
2. 唯一一个不同的小地方就是在父节点与子节点之间需要交换的地方，原实现里确实是交换了元素，本代码里是把目标节点提取出来放到tmp，要调整时直接挪到对应位置，感觉能稍微节省点时间

内省排序：ks_introsort

复杂度：时间O(nlogn)，空间O(logn)，不稳定排序
这是结合了快速排序、梳排序、插入排序等多个排序算法的算法，与c++的STL里的sort类似，c++的sort具体流程可看这里

#define ks_introsort(name, n, a) ks_introsort_##name(n, a)

本代码的小细节：

• 其他基本是递归实现，本代码实现方式为迭代
• 其他地方递归深度过高时使用堆排序，本代码使用梳排序（这样最差的情况为O(n²)，没有堆排序的O(nlogn)兜底了）

内部数据结构

typedef struct {
	void *left, *right;
	int depth;
} ks_isort_stack_t;

用于迭代的栈，存储待处理的大范围区间

• left：区间起点
• right：区间终点
• depth：迭代深度

算法流程

1. 计算迭代深度d，初始化处理范围起点s终点t
2. 开始循环处理区间[s, t]
   • 如果s == t，说明上一轮区间处理完毕，则尝试从迭代栈中取一个区间出来继续处理
     • 如果没有区间了，说明大区间已全部处理完毕，最终调用插入排序并返回
   • 判断当前迭代深度d，如果过高则调用梳排序处理当前区间，然后设置t = s
   • 迭代深度不足时，使用快速排序
     • 选择基准点rp
     • 排序
     • 判断划分出来的两个区间，把较大且够大的区间（>16）放入迭代栈中以便后续处理，先处理较小的区间。如果区间长度不够大，则设置s = t

#define KSORT_INIT(name, type_t, __sort_lt)								
	...																	
	void ks_introsort_##name(size_t n, type_t a[])						
	{																	
		int d;															
		ks_isort_stack_t *top, *stack;									
		type_t rp, swap_tmp;											
		type_t *s, *t, *i, *j, *k;										
																		
		... /* n == 1 || n == 2, return directly */						
		for (d = 2; 1ul<<d < n; ++d);									
		stack = (ks_isort_stack_t*)malloc(sizeof(ks_isort_stack_t) * ((sizeof(size_t)*d)+2)); 
		top = stack; s = a; t = a + (n-1); d <<= 1;						
		while (1) {														
			if (s < t) {												
				if (--d == 0) {											
					ks_combsort_##name(t - s + 1, s);					
					t = s;												
					continue;											
				}														
				... /* choose pivot */									
				rp = *k;												
				... /* sorting */										
				if (i-s > t-i) {										
					if (i-s > 16) { top->left = s; top->right = i-1; top->depth = d; ++top; } 
					s = t-i > 16? i+1 : t;								
				} else {												
					if (t-i > 16) { top->left = i+1; top->right = t; top->depth = d; ++top; } 
					t = i-s > 16? i-1 : s;								
				}														
			} else {													
				if (top == stack) {										
					free(stack);										
					__ks_insertsort_##name(a, a+n);						
					return;												
				} else { --top; s = (type_t*)top->left; t = (type_t*)top->right; d = top->depth; } 
			}															
		}																
	} ...

注：快速排序中的选择基准点pivot这里感觉有点问题，比较i、j、k的大小然后选择一个作为基准赋值给rp，这里选出来的k不一定是中值（比如i < k < j，选出来的rp = *k = *j）

void ks_introsort_##name(size_t n, type_t a[])				
{	...														
	i = s; j = t; k = i + ((j-i)>>1) + 1;					
	if (__sort_lt(*k, *i)) {								
		if (__sort_lt(*k, *j)) k = j;						
	} else k = __sort_lt(*j, *i)? i : j;					
	rp = *k;												
	...

找第k小排序：ks_ksmall

算法原理：利用快速排序的机制，把数组进行划分，只处理k对应的区间
算法步骤：

1. 初始化，处理区间[low, high]，k固定指向数组第k个元素
2. 开始循环
   • 取起点、中点、终点三个元素进行排序，取中间值作为基准值pivot放在low
   • 依次与基准值比较进行排序
   • 根据k的位置选取对应区间

#define ks_ksmall(name, n, a, k) ks_ksmall_##name(n, a, k)

#define KSORT_INIT(name, type_t, __sort_lt)								
	...																	
	type_t ks_ksmall_##name(size_t n, type_t arr[], size_t kk)			
	{																	
		type_t *low, *high, *k, *ll, *hh, *mid;							
		low = arr; high = arr + n - 1; k = arr + kk;					
		for (;;) {														
			if (high <= low) return *k;									
			if (high == low + 1) {										
				if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); 
				return *k;												
			}															
			mid = low + (high - low) / 2;								
			... /* sort *low,*mid,*high, put middle value in *low */	
			ll = low + 1; hh = high;									
			for (;;) {													
				do ++ll; while (__sort_lt(*ll, *low));					
				do --hh; while (__sort_lt(*low, *hh));					
				if (hh < ll) break;										
				KSORT_SWAP(type_t, *ll, *hh);							
			}															
			KSORT_SWAP(type_t, *low, *hh);								
			if (hh <= k) low = ll;										
			if (hh >= k) high = hh - 1;									
		}																
	} ...

不算排序

打乱算法：====

利用取随机数函数drand48将数组打乱

#define ks_shuffle(name, n, a) ks_shuffle_##name(n, a)