Showing Posts From

算法

用一个int表示德州扑克玩家牌力

这个方法是在python的一个德州库(PyPokerEngine)里看到的,并不是原创,但是原方法bug特别的多,直接导致牌局的胜负判断错误,所以我对原方法进行了一些改进,但是原方法的思想非常厉害,所以值得推荐一番。 原库的思想是这样的: int有32位,扑克牌最大的牌是K,值是13,需要用4位来表示,所以利用高16位表示牌型(如一对,两对,顺子等)值,用低16位表示关键牌的值(如一对中,对子的牌大小)。 [牌型大小(16bit)] [关键牌1(4bit)] [关键牌2(4bit)] [手牌1(4bit)] [手牌1(4bit)] 比如 A K Q 5 5,这副牌,可以使用二进制 0000 0000 0000 0001 0000 0101 0001 1101表示。 其中,高16位 0000 0000 0000 0001 表示一对,如果是两对则用 0000 0000 0000 0010 表示,这样的好处是,牌型大的牌无需比较牌面的大小,两对行成的int永远大于一对。其中低16位中的前8位表示的是牌中关键牌的值,这里 0000 0101 表示的是一对5中的5,低16位中的后8位表示的是手牌的大小,我这里假设A K是手牌,所以值为 0001 1101。 乍一看原库的思想的确很妙,不管是什么牌型直接用一个int数字就能表示并且轻易的比较,但是在有的牌局中,这个方法却出现了致命的bug。 在牌型关键牌平局的时候,只能比手牌,这样的比较肯定是错误的。在德州的规则中,如果两名玩家都是一对5,那么需要比较剩下的3张最大的牌,这个时候在原库思想中比的是玩家手牌,但是当桌面上5张牌就是最大的牌的时候,双方应该是平局,手牌不应该左右牌局的胜负方。比如这样一局牌: 公共牌:A K Q J J 玩家1手牌:9 8 玩家2手牌:8 7 这局牌在正确的规则中,应该是平局。但是在原库的代码中,判定玩家1获胜。所以需要修改一下原库的部分算法。 高16位的算法依然保持不变:因为德州的牌型只有10种,所以不需要使用到全部16位。在之前我认为低16位可以够用来进行牌面大小的比较,后来被朋友指出低16位比较算法有问题。所以改为只用最高10位,而多出来的6位需要留给后面牌面比较算法使用。高10位的算法为: // 修改前 // public final int HIGH_CARD = 0; // 高牌 // public final int ONE_PAIR = 1 << 8; // 一对 // public final int TWO_PAIR = 1 << 9; // 两对 // public final int THREE_CARD = 1 << 10; // 三张 // public final int STRAIGHT = 1 << 11; // 顺子 // public final int FLUSH = 1 << 12; // 同花 // public final int FULL_HOUSE = 1 << 13; // 葫芦 // public final int FOUR_CARD = 1 << 14; // 四张 // public final int STRAIGHT_FLUSH = 1 << 15; // 同花顺 // public final int ROYAL_FLUSH = 1 << 16; // 皇家同花顺// 修改后 public final int HIGH_CARD = 1 << 7; // 高牌 public final int ONE_PAIR = 1 << 8; // 一对 public final int TWO_PAIR = 1 << 9; // 两对 public final int THREE_CARD = 1 << 10; // 三张 public final int STRAIGHT = 1 << 11; // 顺子 public final int FLUSH = 1 << 12; // 同花 public final int FULL_HOUSE = 1 << 13; // 葫芦 public final int FOUR_CARD = 1 << 14; // 四张 public final int STRAIGHT_FLUSH = 1 << 15; // 同花顺 public final int ROYAL_FLUSH = 1 << 16; // 皇家同花顺重点就是接下来的每一种牌型的后16位写法,全部都不需要保存手牌了。 **同花顺:**只需要保存同花顺中最小牌在后16位就可以了,比如 10 J Q K A,那么只需要保存10,就能判断同花顺的大小。 **四张:**保存相同的4张牌的牌的大小和剩下最大的那张牌的大小,比如 A A A A K,那么只需要保存 A K 0 0。 **葫芦:**保存3张相同牌的牌大小和另外一对的牌大小,比如 Q Q Q J J,那么保存的就是Q J 0 0。 **顺子:**同同花顺存储方法。 **同花:**5张牌,最大的是A(用14表示),最多5张牌加起来最大的数字是69(并不可能在同花中出现),用8位二进制完全可以存起来,那么同花就保存最大5张牌的和。 **同花:**5张牌,按大小排序,最大的放在高位,最小的放在低位,4位一张牌,需要20位,利用上高位剩下来的6位,就可以将5张牌全部保存下来。 **三张:**依次保存的是,三张相同牌的牌大小,剩下两张最大的牌大小,如Q Q Q J 9,那么按顺序存的是Q J 9 0。 **两对:**依次保存的是,较大的一对的牌大小,较小的一对的牌大小,剩下最大的牌的大小,如 Q Q J J 10,那么按顺序保存的 Q J 10 0。 **一对:**依次保存的是,一对的牌大小,剩下3张最大的牌的大小,如 Q Q J 9 8,那么保存的是 Q J 9 8。 **高牌:**同同花存储方法。 以三张举例,对应的代码如下: // 搜索卡牌列表中是否存在三张,并返回三张的牌面大小,不存在返回-1 private static int searchThreeCard(List cards) { int bestRank = -1; Map> rankGroup = cards.stream().collect(Collectors.groupingBy(Card::getRank, Collectors.toList())); for (Integer rank : rankGroup.keySet()) { List cardList = rankGroup.get(rank); if (cardList.size() >= 3 && rank > bestRank) { bestRank = rank; } } return bestRank; }// 判断存在三张之后,返回三张所对应的牌力int值 if (GameUtil.searchThreeCard(cards) != -1) { int threeCard = GameUtil.searchThreeCard(cards) << 4; List topCardRank = getTopCardRank(2, cards, threeCard >> 4); if (topCardRank == null) { return (THREE_CARD | threeCard) << 8; } return ((THREE_CARD | threeCard) << 8) | ((topCardRank.get(0) << 4) | topCardRank.get(1)); }这样就能够在使用最小内存和最快的比较速度的情况下,判断出哪一位玩家获胜了。

游戏突发随机事件设计

最近在学游戏开发,尝试开发一个经营类游戏,其中有个点子就是:在游戏的过程中,会不时的发生一些突发事件,可能是任务,可能是天灾人祸等,当然,要有趣,那么这个事件就得是随机的,不能是一成不变的。 我的想法是设计一个表达式,使用表达式形成事件的多样化,表达式里的词缀够多,用词缀来实现随机化,这样添加足够多的词缀和表达式就能有足够多的随机事件。最后实现的效果应该是这样: `$charactor 很喜欢您的弟子 #disciple ,对他 $act ,获得奖励 #prize``王重阳很喜欢您的弟子王铁锤,对他千锤百炼,获得奖励一件衣服 乔峰很喜欢您的弟子王铁锤,对他千锤百炼,获得奖励领悟一个技能`其中$开头的词语,代表随机词缀;#开头的词语代表编程表达,也就是需要代码实现功能的词缀;获得的奖励,将与词缀进行挂钩。 为了快速实现原型,先采用python来完成demo,其他语言都能够实现相同效果。 第一步,先解析表达式。首先使用空格对整个表达式split,拆分出来所有的token: token = expression_str.split(" ") token # ['$charactor', '很喜欢您的弟子', '#disciple', ',对他', '$act', ',获得奖励', '#prize']遍历tokens,如果是$开头则代表词缀,#开头则代表编程表达,其实也可以直接用token来对比词缀表实现匹配,可是这样效率较低,所以加上了前缀来方便判断。 total_text = [] for i in token: if i.startswith("$"): pass elif i.startswith("#"): pass else: total_text.append(i)在处理词缀之前,首先要定义好词缀表: store_data = { 'charactor': { 'text': ["令狐冲", "林平之", "王重阳", "乔峰", "段誉", "段誉姑姑的弟弟的儿子的同学的妈妈"] }, 'act': { 'text': ['一番把玩', '千锤百炼', '打情骂俏', '拳打脚踢'] }, 'place': { 'text': ['泰山', '黄山', '茅厕', '草丛', '房顶'] } }定义好词缀表之后,在遇到$开头的词缀的时候,进行词缀随机匹配: total_text = [] for i in token: if i.startswith("$"): name = i[1:] # 去除前缀的$ rand_i = random.randint(0, len(store_data[name]['text']) - 1) # 随机获得词缀中的一个 total_text.append(store_data[name]['text'][rand_i]) elif i.startswith("#"): pass else: total_text.append(i)第二步,计算奖励,在这里为了简便,我直接定义为了#prize,并且一定要是表达式的最后一个词缀,至于为什么往下看就知道了。而#disciple我会获取到游戏中我所拥有的弟子中的一个,那首要一步是定义弟子数据。 disciple_data = ["王铁锤", "谢帅逼"] # 简单定义当碰到#disciple的时候,直接进行随机选取弟子: total_text = [] for i in token: if i.startswith("$"): name = i[1:] # 去除前缀的$ rand_i = random.randint(0, len(store_data[name]['text']) - 1) # 随机获得词缀中的一个 total_text.append(store_data[name]['text'][rand_i]) elif i.startswith("#"): name = i[1:] if name == "disciple": rand_i = random.randint(0, len(disciple_data) - 1) total_text.append(disciple_data[rand_i]) else: total_text.append(i)这个时候词缀的填充大致完成了,那是时候计算整个事件带来的奖励了,大致思路是每个词缀都有一个价值,当词缀完成整个句子的时候,整个句子的价值决定了获取到的奖励,这个时候就需要给词缀表增加价值字段: store_data = { 'charactor': { 'text': ["令狐冲", "林平之", "王重阳", "乔峰", "段誉", "段誉姑姑的弟弟的儿子的同学的妈妈"], 'value': [5, 3, 5, 4, 3, -1] }, 'act': { 'text': ['一番把玩', '千锤百炼', '打情骂俏', '拳打脚踢'], 'value': [1, 5, 1, -2] }, 'place': { 'text': ['泰山', '黄山', '茅厕', '草丛', '房顶'], 'value': [3, 3, -1, 0, 1]} }第三步就是把整个句子的价值算出来: total_value = 0 # 用来计算整个句子价值 total_text = [] for i in token: if i.startswith("$"): name = i[1:] # 去除前缀的$ rand_i = random.randint(0, len(store_data[name]['text']) - 1) # 随机获得词缀中的一个 total_text.append(store_data[name]['text'][rand_i]) total_value += store_data[name]['value'][rand_i] # 加上词缀对应的价值 elif i.startswith("#"): name = i[1:] if name == "disciple": rand_i = random.randint(0, len(disciple_data) - 1) total_text.append(disciple_data[rand_i]) else: total_text.append(i)这样价值就计算出来了,并且“ 令狐冲 ”、“ 王重阳 ”比“ 林平之 ”、“ 段誉 ”词缀的价值要高,“ 千锤百炼 ”比“ 一番把玩 ”价值要高,“ 拳打脚踢 ”甚至会产生负效果。 对应价值,设计一个简单的奖励表: prize_data = { -4: "失去10声望", -3: "失去2000块钱", -2: "失去1000块钱", -1: "失去100块钱", 0: "0块钱", 1: "100块钱", 2: "1000块钱", 3: "2000块钱", 4: "随机道具", 5: "10声望", 6: "20声望", 7: "50声望", 8: "一件衣服", 9: "一把武器", 10: "领悟一个技能", 11: "资质提升", 12: "领悟两个技能" }当然,如果算出来的奖励是多少,就获得对应等级的奖励,游戏也太无趣了,让获取奖励也多一些随机性,使用正态分布来处理获取奖励的概率,如果表达式的价值是8,那么应该是6、7、8的等级概率高,同时往两边扩散概率变低。 那么就进行最后一步,处理prize词缀,并且封装成方法,因为处理prize的时候直接使用了total_value的值,并没有检查之后是否还有词缀,所以为了计算奖励更加准确,需要将prize放在所有词缀的后面,以保证词缀都计算完成: def random_event(expression_str): token = expression_str.split(" ") total_value = 0 total_text = [] for i in token: if i.startswith("$"): name = i[1:] # 去除前缀的$ rand_i = random.randint(0, len(store_data[name]['text']) - 1) # 随机获得词缀中的一个 total_text.append(store_data[name]['text'][rand_i]) total_value += store_data[name]['value'][rand_i] elif i.startswith("#"): name = i[1:] if name == "disciple": rand_i = random.randint(0, len(disciple_data) - 1) total_text.append(disciple_data[rand_i]) elif name == 'prize': rand_i = round(random.gauss(total_value - 1, (total_value - 1) / 10)) total_text.append(prize_data[rand_i]) else: total_text.append(i) return "".join(total_text)`random_event("$charactor 很喜欢您的弟子 #disciple ,对他 $act ,获得奖励 #prize") # 段誉姑姑的弟弟的儿子的同学的妈妈很喜欢您的弟子谢帅逼,对他打情骂俏,获得奖励失去100块钱 random_event("$charactor 从 $place 到您的门派求学,是否接纳") # 王重阳从泰山到您的门派求学,是否接纳`这样就可以通过编写不同的表达式,添加不同的普通词缀,编写更丰富的编程表达,来丰富整个事件系统,事件系统的能力也会成倍数增长。当然,这只是个思路,要真正做出这个事件,还有很多的概率需要计算。

LeetCode 72. Edit Distance

LeetCode 72. Edit Distance题目:给定两个单词,将第一个单词转换成第二个单词,需要的最少的步数。其中:替换,删除,增加都算是一个步数。思路:不知道为啥这题标为难,其实也是超级简单的题目,唯一需要动一点脑子的,就是删除的那个操作,第二个单词的下标是不需要往前移的。比较值得注意的一点是,如果用的元组来做dict的key,效率很低,有可能会超时,改为二维数组效率就会快很多了。 `class Solution: def __init__(self): self.cache = [] def minDistance(self, word1, word2): """ :type word1: str :type word2: str :rtype: int """ self.cache = [[0] * len(word2) for i in range(len(word1))] return self.dp(word1, word2, 0, 0) def dp(self, word1, word2, i, j): if i == len(word1) or j == len(word2): return len(word1[i:]) + len(word2[j:]) elif self.cache[i][j] != 0: return self.cache[i][j] elif word1[i] == word2[j]: return self.dp(word1, word2, i + 1, j + 1) else: self.cache[i][j] = min(self.dp(word1, word2, i, j + 1) + 1, self.dp(word1, word2, i + 1, j) + 1, self.dp(word1, word2, i + 1, j + 1) + 1) return self.cache[i][j] `

LeetCode 712. Minimum ASCII Delete Sum for Two Strings

712. Minimum ASCII Delete Sum for Two Strings 又是dp题目题目:删掉两个字符串中的字符让两个字符串相同,并统计删掉的字符的ascii码总和,要求总和最低。思路:也是动态规划,和最长公共子序列很像,是个变种。 有两种思路,第一种:继续按照最长公共子序列来做,算出了最长公共子序列之后,拿两个字符串的ascii码总和减去公共子序列的ascii码值,就是去掉的字符串的ascii码的和;第二种:反向算最长公共子序列,当dp计算的时候,如果字符不相等,进行ascii码的计算,相等则继续循环。 我采用的是第二种思路,用的递归写法,个人认为递归的写法比较简单,一下就能开写,不太需要思考。 `class Solution: def __init__(self): self.cache = [] def minimumDeleteSum(self, s1, s2): """ :type s1: str :type s2: str :rtype: int """ self.cache = [[0] * (len(s2) + 1) for i in range(len(s1) + 1)] return self.dp(s1, s2, 0, 0) def dp(self, s1, s2, i, j): if i == len(s1) or j == len(s2): return self.cal(s1[i:]) + self.cal(s2[j:]) elif s1[i] == s2[j]: return self.dp(s1, s2, i + 1, j + 1) elif self.cache[i][j] != 0: return self.cache[i][j] else: self.cache[i][j] = min(self.dp(s1, s2, i, j + 1) + ord(s2[j]), self.dp(s1, s2, i + 1, j) + ord(s1[i])) return self.cache[i][j] return self.cache[(i, j)] def cal(self, string): rsum = 0 for i in string: rsum += ord(i) return rsum `

LeetCode 198&213. House Robber & House Robber II

LeetCode 198&213. House Robber & House Robber II 两题一起题目:抢劫房屋,不能抢劫相邻的房屋,否则会被抓。升级版的房屋是一个环,也就是最后和最先的房屋是相邻的。思路:基础版是最简单的动态规划,升级版就是抢最后一间和不抢最后一间的情况取最大的那个。只放基础版的代码了。 `class Solution: def rob(self, nums): """ :type nums: List[int] :rtype: int """ take = 0 not_take = 0 for i,n in enumerate(nums): index = i + 2 temp = take take = max(take, not_take + n) not_take = max(not_take, temp) return take `

LeetCode 746. Min Cost Climbing Stairs

LeetCode 746. Min Cost Climbing Stairs题目:爬楼梯,可以选择爬一级或者两级,每一级需要消耗的能量存储在cost数组中,可以选择从第一级或者第二级开始爬,求最小的能量消耗是多少。思路: 非常简单的一道动归题目,只需要用到缓存,就能直接解决了。唯一我用到的一个技巧:因为要爬到最上面,意味着要爬过最后一级台阶,那么我向数组里push一个消耗为0的台阶,作为最终目标。没有多想,直接开码: `/** * @param {number[]} cost * @return {number} */ var minCostClimbingStairs = function(cost) { cost.push(0); let target = cost.length - 1, memo = {}; if (target < 2) { return Math.min(...cost); } let r = function (i) { if (memo[i]) return memo[i]; if (i > 1) { memo[i] = Math.min(r(i - 1) + cost[i], r(i - 2) + cost[i]); } else { memo[i] = cost[i]; } return memo[i]; }; return r(target); }; `

LeetCode 10. Regular Expression Matching

题目:实现正则表达式的.和*两个符号。思路:第一时间看到正则,马上就想到了用while来不停匹配。后来遇到了a*a匹配aa,发现要处理贪心和不贪心多种情况,所以将while转为了递归。 题目考察的多是递归的设计和考虑多种情况是否周全,代码很少(JS实现): var isMatch = function(s, p) { if (!p) return !s; let match = !!s && (s[0] === p[0] || p[0] === "."); // console.log(s, p, match) if (p[1] === "*") { return isMatch(s, p.substr(2)) || (match && isMatch(s.substr(1), p)); } else { return match && isMatch(s.substr(1), p.substr(1)) } };如果觉得递归代码不好看,可以将递归改为动态规划,使用bottom-up或者简单的memo来提高程序的性能。

LeetCode 650. 2 Keys Keyboard

题目:初始化字符只有一个A,现在有两种操作:1.复制当前所有字符。2.粘贴。使用这两种操作得到n个A字符,求最少的步数。思路:我是在dp的tag下找到的这个题目,但是我发现最简单的解法应该直接使用贪心算法就可以了。 要得到n个A字符,可以认为最少的步数肯定是通过粘贴最多的字符来得到的,那么反推就能得到最少步数了。 举个例子,如果输入n=12,那么根据贪心的思想,可以认为是先得到6个A,然后进行复制粘贴两步得到,6个A又是通过3个A粘贴得到,3个A需要3步得到,那么总共需要的最少步数是:3(3A) + 2(3A -> 6A)+ 2(6A -> 12A)= 7步。 代码如下(JS实现): var minSteps = function(n) { let sum = 0; while (n >= 2) { for (let i = 2; i <= n; i++) { if (n % i === 0) { sum += i; n = n / i; break; } } } return sum; };&nbsp;

LeetCode 689. Maximum Sum of 3 Non-Overlapping Subarrays

题目:给定一个数组nums,给定一个整数k,求数组内k长度的子串和最大的3个子串位置。(位置不可重复,结果数字序要求最小) 比如: Input: [1,2,1,2,6,7,5,1], 2 Output: [0, 3, 5] 最大为 [1, 2] [2, 6] [7, 5]的和思路:看到带3的题目,首先要想到利用3。3代表着可以构成左中右结构,也就是说只要能知道当前位置符合要求的左边最大值,右边最大值就知道了答案。 那么第一步就是先求出子串和的数组(打印输出以上面例子作为输入): let sumArray = []; let sum = 0; for (let i = 0; i < nums.length; i++) { sum += nums[i]; if (i >= k) sum -= nums[i - k]; if (i >= k - 1) sumArray[i - k + 1] = sum; } console.log(sumArray); // [ 3, 3, 3, 8, 13, 12, 6 ]然后相应的求出当前i位置的左侧最大值,和右侧最大值: let left = []; left[0] = 0; for (let i = 1; i < sumArray.length; i++) { left[i] = sumArray[left[i-1]] >= sumArray[i] ? left[i-1] : i; } console.log(left); // [ 0, 0, 0, 3, 4, 4, 4 ]let right = []; right[sumArray.length - 1] = sumArray.length - 1; for (let i = sumArray.length - 2; i >= 0; i--) { right[i] = sumArray[right[i+1]] >= sumArray[i] ? right[i+1] : i; } console.log(right); // [ 4, 4, 4, 4, 4, 5, 6 ]最后,循环数组,计算出最大值和所在位置就可以了,完整代码如下: var maxSumOfThreeSubarrays = function(nums, k) { let result = []; let sumArray = []; let sum = 0; for (let i = 0; i < nums.length; i++) { sum += nums[i]; if (i >= k) sum -= nums[i - k]; if (i >= k - 1) sumArray[i - k + 1] = sum; } console.log(sumArray); let left = []; left[0] = 0; for (let i = 1; i < sumArray.length; i++) { left[i] = sumArray[left[i-1]] >= sumArray[i] ? left[i-1] : i; } console.log(left); let right = []; right[sumArray.length - 1] = sumArray.length - 1; for (let i = sumArray.length - 2; i >= 0; i--) { right[i] = sumArray[right[i+1]] >= sumArray[i] ? right[i+1] : i; } console.log(right); let ans = [0, k, 2 * k]; for (let i = k; i < sumArray.length - k; i++) { if (sumArray[i] + sumArray[left[i - k]] + sumArray[right[i + k]] > sumArray[ans[0]] + sumArray[ans[1]] + sumArray[ans[2]]) { ans = [left[i - k], i, right[i+k]] } } console.log(ans); return ans; };&nbsp;

LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee

题目:给定一个股票价格数组prices,标记了每天股票的价格,还有一个股票买卖手续费fee。求交易最大利润。 比如: Input: prices = [1, 3, 2, 8, 4, 9], fee = 2 Output: 8思路:动态规划,使用两个变量分别记录当前购买股票hold和售出股票cash获得的利润。 cash计算很简单,当前股票卖出的时候只要是赚的,就可以出售,递推式也就是: cash = Math.max(cash, hold + prices[i] - fee)hold的要求很简单,不要买亏就好了,那么递推式就是: hold = Math.max(hold, cash - prices[i])不知道这么说是否直观,可以根据例子来推算一下: 第一天的假设我们买了,cash = 0, hold = -1 第二天会发现,卖出股票减去手续费,没有赚,并且换一支持股,也更亏,那么第二天可以略过。 第三天同第二天。 第四天,很重要的一天。卖出股票减去手续费可以赚5块,那么直接卖。然后再买股票,那么持有股票的金额就为1元。 第五天,最后一天。卖出股票减去手续费可以赚7块,也卖掉。最后手中持有的钱就为8块了。 最后代码如下,JS实现: var maxProfit = function(prices, fee) { let hold = -prices[0], cash = 0; for (let i = 1; i < prices.length; i++) { cash = Math.max(cash, hold + prices[i] - fee); hold = Math.max(hold, cash - prices[i]); } return cash; };&nbsp;

Java源码解析-DualPivotQuicksort

Java源码解析-DualPivotQuicksort

前言 一直都想阅读一些比较深层次的东西,但是自己的水平还没有达到那个层次,所以从比较基础也是比较底层的Java源码下手。 排序应该是使用的比较多,性能比重比较大的算法之一,而快排更是排序中的经典。不论是C++的qsort还是Java的Arrays.sort都是快排实现,我一直很好奇这些语言设计者写出的快排是怎样的,不看不知道,一看吓一跳,果然跟我以前学的快排不一样,我们就来了解一下Java中的快排实现吧。 JAVA中不同的快排 Java在不同版本中对算法进行更改已经不是稀罕事了,对于sort方法也不例外。 Java1.7之前的快排 在Java1.7之前的快排只是普通的快排,跟我们今天要研究的快排不一样,性能也差了许多,但其中对快排所做的各种优化我们依然是可以学习的。 Java1.7的快排 Java1.7的快排是一种双轴快排,顾名思义:双轴快排是基于两个轴来进行比较,跟普通的选择一个点来作为轴点的快排是有很大的区别的。算法是由Vladimir Yaroslavskiy在2009年研究出来的,并在2011年发布在了Java1.7。由于Arrays.sort对于数组的排序做了各种各样的优化,并且大多数优化和我们今天要研究的双轴排序无关,所以我们暂且略过,以后有时间研究Arrays源码的时候我们再进行分析。 算法分析 既然这个算法比之前快排要快,那么肯定有它的巧妙之处,我们来仔细看看吧。 算法步骤 1.对于很小的数组(长度小于27),会使用插入排序。 2.选择两个点P1,P2作为轴心,比如我们可以使用第一个元素和最后一个元素。 3.P1必须比P2要小,否则将这两个元素交换,现在将整个数组分为四部分: (1)第一部分:比P1小的元素。 (2)第二部分:比P1大但是比P2小的元素。 (3)第三部分:比P2大的元素。 (4)第四部分:尚未比较的部分。 在开始比较前,除了轴点,其余元素几乎都在第四部分,直到比较完之后第四部分没有元素。 4.从第四部分选出一个元素a[K],与两个轴心比较,然后放到第一二三部分中的一个。 5.移动L,K,G指向。 6.重复 4 5 步,直到第四部分没有元素。 7.将P1与第一部分的最后一个元素交换。将P2与第三部分的第一个元素交换。 8.递归的将第一二三部分排序。 图表演示注:图片来自Vladimir Yaroslavskiy的论文。 算法源码 //对外公开的两个sort方法 public static void sort(int[] a) { sort(a, 0, a.length); } public static void sort(int[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); dualPivotQuicksort(a, fromIndex, toIndex - 1, 3); } //对数组的边界检测 private static void rangeCheck(int length, int fromIndex, int toIndex) { if (fromIndex > toIndex) { throw new IllegalArgumentException("fromIndex > toIndex"); } if (fromIndex < 0) { throw new ArrayIndexOutOfBoundsException(fromIndex); } if (toIndex > length) { throw new ArrayIndexOutOfBoundsException(toIndex); } } //交换数组中两个元素 private static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } /** * 双轴快排的具体实现 * @param a 待排序数组 * @param left 数组需排序上界 * @param right 数组需排序下界 * @param div 理解为从何位置取轴 */ private static void dualPivotQuicksort(int[] a, int left,int right, int div) { int len = right - left; //数组长度如果很小(27),则直接用插入排序对其排序 if (len < 27) { for (int i = left + 1; i <= right; i++) { for (int j = i; j > left && a[j] < a[j - 1]; j--) { swap(a, j, j - 1); } } return; } //取到位于1/div和div-1/div位置的点,并用他们来做轴 int third = len / div; int m1 = left + third; int m2 = right - third; if (m1 <= left) { m1 = left + 1; } if (m2 >= right) { m2 = right - 1; } //确保left是小的,right是大的 if (a[m1] < a[m2]) { swap(a, m1, left); swap(a, m2, right); } else { swap(a, m1, right); swap(a, m2, left); } // 两个轴 int pivot1 = a[left]; int pivot2 = a[right]; // 代表比p1小和比p2大的两个指针 int less = left + 1; int great = right - 1; // 开始取出less到great之间的未知大小数据,与两个轴比较 // 并且将数据放入正确的区域后调整各个指针 for (int k = less; k <= great; k++) { //如果取出的数比p1小,那么直接到less左侧,并且less右移 if (a[k] < pivot1) { swap(a, k, less++); } //如果取出的数比p2大,那么首先确定great左侧没有比p2大的数 //然后与great位置的数字交换,great左移 //此时,great交换的数字肯定是比p2小或者相等的(首先确定过) //那么此时再与p1相比,处理这个数的区间 else if (a[k] > pivot2) { while (k < great && a[great] > pivot2) { great--; } swap(a, k, great--); if (a[k] < pivot1) { swap(a, k, less++); } } //如果这个数比p1大但是比p2小,则不需要交换,只需将k指针右移 } //将p1与less左侧的第一个数交换 swap(a, less - 1, left); //将p2与great右侧的第一个数交换 swap(a, great + 1, right); // 计算出在两轴大小之间的个数 int dist = great - less; //如果这个数很小(13),那么取轴的点向两边偏 if (dist < 13) { div++; } // 对三个子区间分别排序,因为less-1和great+1是轴,已经排好了序 // 所以不需要比较 dualPivotQuicksort(a, left, less - 2, div); dualPivotQuicksort(a, great + 2, right, div); // 如果在中间区间的数字很多,那么排除掉一些相等的元素再进行排序 if (dist > len - 13 && pivot1 != pivot2) { for (int k = less; k <= great; k++) { if (a[k] == pivot1) { swap(a, k, less++); } else if (a[k] == pivot2) { swap(a, k, great--); if (a[k] == pivot1) { swap(a, k, less++); } } } } // 对中间的区间排序 if (pivot1 < pivot2) { dualPivotQuicksort(a, less, great, div); } }总结 双轴排序利用了区间相邻的特性,对原本的快排进行了效率上的提高,很大程度上是利用了数学的一些特性,果然,算法跟数学还是息息相关的吖。