三路快速排序法
2022/12/19 3:23:59
本文主要是介绍三路快速排序法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
三路快速排序法
三路快速排序将数组分成了 <V, ==V, >V 三部分,这样只需递归的对<V和>V的部分进行快速排序
具体步骤演示:
处理e的各种情况
e == v, i++
e < v, e 和 arr[lt + 1] 交换, lt++, i++查看下一个元素
e > v, e 和 arr[gt - 1] 交换位置, gt--
当 i == gt : 表示对整个数组处理完毕
交换arr[l]和arr[lt], lt++
接下来只需对<v的部分和>v的部分进行递归排序就好了, ==v的部分已经放在了数组中合适的位置
这种方案的优点:不需对大量==v 的元素进行排序操作
快速排序和归并排序都是Nlog(N),但是快速排序比归并排序要快些
代码部分
public class ThreeWayQuickSort extends Sort { private Random random; public void sort(int[] arr, int n) { random = new Random(new Date().getTime()); quickSort(arr, 0, n - 1); } /** * 对arr[l..r]部分进行三路快速排序 * 将arr[l..r]分为<v, ==v, >v 三部分 * 然后递归对<v 和 >v 部分进行三路快速排序 */ private void quickSort(int[] arr, int l, int r) { if (l >= r) { return; } if ( r - l <= 15) {//优化1:子序列元素个数小于16时用插入排序 AlgorithmUtils.insertionSort(arr, l, r); return; } //由于三路快速排序的中间部分是==v的一个区间,java语言不好写出返回区间首尾的值, //所以不单独写partition方法 AlgorithmUtils.swap(arr, l, Math.abs(random.nextInt()) % (r - l + 1) + l); int v = arr[l]; int lt = l; //arr[l + 1..lt] < v //初始时 lt < l + 1, 为空区间 int i = l + 1; //arr[lt + 1..i - 1] == v int gt = r + 1; //arr[gt..r] > v //初始时 r < gt , 为空区间 while (i < gt) { if (arr[i] < v) { AlgorithmUtils.swap(arr, i, lt + 1); lt++; i++; }else if (arr[i] > v) { AlgorithmUtils.swap(arr, i, gt - 1); gt--; }else { i++; } } AlgorithmUtils.swap(arr, l, lt); quickSort(arr, l, lt - 1); quickSort(arr, gt, r); } }
这篇关于三路快速排序法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding
- 2024-04-14出海软件草根逆袭打法是什么?
- 2024-04-13鸿蒙原生应用再新丁!企查查 碧蓝航线 入局鸿蒙
- 2024-04-11RAG应用开发实战(01)-RAG应用框架和解析器
- 2024-04-10DevOps已死?2024年的DevOps将如何发展
- 2024-04-10码农必看:常见源代码混淆技术详解