知识卡片
排序接口分清元素宽度与区间
issort(void data,int size,int esize,compare)按size个、每个esize字节处理连续数组,compare为int ()(const void,const void)。成功0、临时分配失败-1,结果覆盖原数组,比较方向决定升/降序。
qksort在相同参数外还接收闭区间i/k,完整数组初始为0与size−1;它们是当前排序边界,不是两个独立数组。实际算法仅在i时分区。调用方须保证范围、元素宽度和字节索引运算合法,不能把void*当自动安全的任意对象序列。
compare的正/零/负表示大小顺序,不是相等谓词。数组元素若本身是指针,比较器接到的是指针元素所在位置的地址,需按元素表示正确解读,不能混同其所指应用对象。
209及02952实际qksort(void*,int size,int esize,int i,int k,compare)以0/-1报告执行。表中O(n log n)应限定平均/期望,正文210仍承认最坏平方;失败可能发生于较晚分区,数组可能已部分交换,没有事务回滚。
213⁄02960 mgsort(void* data,int size,int esize,int i,int k,int (compare)(const void,const void*))成功0、失败-1,完整区间0到size−1。i/k是当前边界,不是两个数组;分配失败前可能已有子区间完成,失败不回滚先前排序。
219/02972实际int rxsort(int* data,int size,int p,int k),成功0、分配失败-1;内部对每digit使用计数步骤,表描述“利用计数排序”指这一机制,不是把整个键直接交ctsort一次即可。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 排序接口分清元素宽度与区间
- · 快速排序的接口定义
- · 归并排序的接口定义
- · 基数排序的接口定义
原书出处 · 4 处
- · 查看原书依据
issort 返回值 如果排序成功,返回0;否则,返回-1。 描述 利用插入排序将数组data中的元素进行排序。data中元素的个数由size决定。而每个元素的大小由esize决定。函数指针compare会指向一个用户定义的函数来比较元素大小。在递增排序中,如果key1>key2,函数返回1;如果k
- · 查看原书依据
i和k定义当前进行排序的两个部分,其值分别初始化为0和size-1。函数指针compare会指向一个用户定义的函数来比较元素大小。其函数功能与issort中描述的一样。当qksort返回时,data包含已排序的元素。 复杂度 O(nlg n),n为要被排序的元素的个数。
- · 查看原书依据
mgsort 返回值 如果排序成功,返回0;否则,返回-1。 描述 利用归并排序将数组data中的元素进行排序。数组中的元素个数由size决定。而每个元素的大小由esize决定。参数i和k定义当前进行排序的两个部分,其值分别初始化为0和size-1。函数指针compare会指向一个用户定义的函数来比
- · 查看原书依据
rxsort 返回值 如果排序成功,返回0;否则,返回-1。 描述 利用计数排序将数组data中的整数进行排序。数组data中整数的个数由size决定。参数p指定每个整数包含的位数,k指定基数。当rxsort返回时,data包含已排序的整数。 复杂度 O(pn+pk),n为要排序的元素的个数,k为基