redis 中sort实现原理

redis客户端发送sort 操作时调用函数为sortCommand,sortCommand函数对参数进行解析,之后调用pqsort函数,pqsort函数在pqsort.c文件中,此文件提供给外部只有一个函数qsort(),内部调用_pqsort()实现的,文件中一些其他的静态函数和宏也是辅助作用的。

void pqsort(void *a, size_t n, size_t es,    int (*cmp) (const void *, const void *), size_t lrange, size_t rrange)

参数a:待排序数组的首地址。n:待排序元素的个数 。es:element size 每个元素的字节大小 。cmp:回调函数,定义了比较的规则 。lrange:待排序的左边界。rrange:待排序的右边界。


排序函数

内部调用 _pqsort,二者差别是psort()的参数中左右边界值含义是下标;_pqsort()参数中的左右边界值,其含义是指针。

辅助函数:


SWAPINIT

    该宏的目的在于给swaptype赋值,swaptype = 2,数组a中元素的大小不是sizeof(long)的倍数;swaptype = 0 ,每个元素大小是sizeof(long);swaptype=1,是sizeof(long)的倍数但是不等于sizeof(long)。


med3

    根据回调函数cmp指定的比较规则,求出变量a,b,c中处于中间大小的变量,也就是求出中位数。

_pqsort流程:


元素个数小于7

排序的元素个数小于7的时候,采用了冒泡排序。


元素个数大于7

pm指向数组中间位置索引,pl指向数组首位置索引,pn执向数组末位置索引,然后求出三个数中的中位数。

元素个数大于40的时候,将元素分为8个子区间,pl左边三个区间首部中的中位数索引,pm中间三个区间首部中的中位数索引。pr右边三个区间首部中的中位数索引。

pm理解为快排中所选择的基准(key),每次排序后保证基准左边小于它,基准右边大于它,并且左右区间长度大致相同,接下来排序效率就会更高。


快排操作

把基准(key)放在第一元素中,从前面位置(pa,pb)开始向后遍历,找到比基准的的数字,从后向前找到比基准小的数字,然后交换。


基准交换到中间


开始下一轮排序

新排序开始使用循环(goto loop),而不是使用递归,文中给出的注释是节省栈空间。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,717评论 6 496
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,501评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,311评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,417评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,500评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,538评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,557评论 3 414
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,310评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,759评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,065评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,233评论 1 343
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,909评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,548评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,172评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,420评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,103评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,098评论 2 352

推荐阅读更多精彩内容