算法第四版- 2.3
2021/10/27 12:39:40
本文主要是介绍算法第四版- 2.3,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
算法第四版- 2.3
文章目录
- **算法第四版- 2.3**
- 基础知识
- 三项切分
- 杂记
基础知识
其实就两个函数,一个quickSort,一个partition。当然基础的函数应该是partition()
快速排序-小灰漫画
三项切分
或者说,“荷兰国旗问题”
课本上说,在有大量重复元素的情况下,用三部分的话,性能会比较好,是熵最优的排序。
private static void sort(Comparable[] a, int lo, int hi) { if (hi <= lo) return; int lt = lo, gt = hi; Comparable v = a[lo]; int i = lo + 1; while (i <= gt) { int cmp = a[i].compareTo(v); if (cmp < 0) exch(a, lt++, i++); else if (cmp > 0) exch(a, i, gt--); else i++; } // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. sort(a, lo, lt-1); sort(a, gt+1, hi); assert isSorted(a, lo, hi); }
课本上的java代码,直接从网站抓的。
补充一下,exch就是交换,和swap一样
assert,断言。当assert后面的bool为真时,继续正常运行;否则报错
配图如下:
杂记
还有一个优化的点是,当N比较小的时候,可以切换到插入排序
当 N再大一点,好像还用到了median3来进行优化,没有很看懂。
反正可以直接调API,没有动力写了,落泪。
这篇关于算法第四版- 2.3的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-20测试人员都是画画大神,让我看看谁还不会用代码图?
- 2024-05-20年薪百万的程序员都在用的摸鱼方式……
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了