引言在日常研发的过程中,我们无时无刻都在考虑自己开发的程序是否高效,一段好的程序执行离不开对算法的深刻认识和熟练掌握。接下来的日子,我将带着大家一起重温一下常见
引言
在日常研发的过程中,我们无时无刻都在考虑自己开发的程序是否高效,一段好的程序执行离不开对算法的深刻认识和熟练掌握。接下来的日子,我将带着大家一起重温一下常见的几种算法。
先上大图:
下面我们一起来学习一下 快速排序算法 吧!
快速排序算法
维基百科介绍: 快速排序使用分治法(Divide and conquer)策略來把一个序列(list)分为较小和较大的2个子序列,然后递归地排序两个子序列,最终合并得到一个从小到大的序列。
有聪明的小伙伴就会问了:什么是分治法策略呢?
分治法(Divide and conquer)
字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
由此就可以引出我们今天讲的快速排序算法的实现步骤了:
- 从数据中随机获取一个值,按这个值的大小对比分成左右两个数据集合,左边数据集合的值小于此值,右边反之
- 将两边数据进行递归调用步骤1
- 将所有数据合并
快速排序算法实现
void main() { List<int> quickSort(List<int> arr) { // 处理边界问题 if (arr.length <= 1) { return arr; } // 取出第一个值作为参考 int splitData = arr[0]; // 小于参考值的集合 List<int> low = []; // 大于参考值的集合 List<int> hight = []; // 与参考相等的集合 List<int> mid = []; // 初次把参考值添加到mid中 mid.add(splitData); for (int i = 1; i < arr.length; i++) { if (arr[i] < splitData) { // 小于 low.add(arr[i]); } else if (arr[i] > splitData) { // 大于 hight.add(arr[i]); } else { // 等于 mid.add(arr[i]); } } // 二分数据后,再继续递归整理 low = quickSort(low); hight = quickSort(hight); // 最后合并 return [...low, ...mid, ...hight]; } const List<int> ary = [4, 5, 1, 3, 6, 2, 5, 6, 7, 2, 4]; print(quickSort(ary)); }
至此,我们就重新温习了一下 快排算法 !
更多关于Flutter Dart快速排序算法的资料请关注好代码网其它相关文章!