[排序算法] 如何解决快速排序特殊情况效率低的问题------三路划分

本文主要是介绍[排序算法] 如何解决快速排序特殊情况效率低的问题------三路划分,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

        在[C/C++]排序算法 快速排序 (递归与非递归)一文中,对于快速排序的单趟排序一共讲了三种方法: hoare挖坑法双指针法 ,这三种方法实现的快速排序虽然在一般情况下效率很高,但是如果待排序数据存在大量重复数据,那这几种方法的效率就很低,而为了解决快速排序在这样特殊情况下效率低下的问题, 三路划分就可以完美解决

三路划分

思想:

        对于上述三种方法,其本质都是选定数组开头元素作特定值,让小的数据放左边,大的数据放右边。而三路划分顾名思义就是通过处理将数据分为三个部分 [小于特定值的部分   等于特定值的部分  大于特定值的部分] ,这样划分好后,只需要对小于特定值的部分和大于特定值的部分进行递归排序即可,中间的数据就不需要处理了,相比于上述三种方法效率提升很大,并且重复数据越多排序效率越快,当带排序数据全为重复数据时,时间复杂度甚至可以达到O(N)。

算法实现

首先我们定义一个cur指针指向begin的下一个元素,将begin开始所指元素定为关键值key

比较a[cur]与key的值,会出现三种情况

  1. 若a[cur]<key,交换a[begin]和a[cur], cur++, begin++
  2. 若a[cur]>key,交换a[end]和a[cur],end--
  3. 若a[cur]==key,cur++

重复比较操作,直到cur>end

[解释]:

为什么a[begin]和a[cur]交换后, cur要++, 而a[end]和a[cur]交换后,cur不和情况1一样++呢?

        因为a[end]和a[end]交换,目的是让大于key的值放到后面,而end所指元素我们不知道其与key的大小关系,所以下一次循环,还得判断其与key的关系才行,cur++会跳过这个元素。而begin初始所指元素就是关键值key, 当第一次找到比key小的数让两者交换,此时cur所指元素就是关键值,再仔细揣摩一下,只有小的数往左放的时候begin才会++,碰到大的数会把他往后放,放完还得比较当前cur所指的元素,碰到与key相同的元素不交换,cur往后走,这样我们会发现begin只会指向和key一样大的元素,所以交换完后,cur可以++。


单趟排序图解如下:

a[cur]<key,交换,cur++,begin++

a[cur]<key,交换,cur++,begin++

a[cur]==key, cur++

a[cur]==key, cur++

a[cur]>key,交换a[end]和a[cur],end--

a[cur]==key, cur++

a[cur]==key, cur++,此时cur>end,排序完成,将数据分为了三个部分

因为单趟排序排好后划分了三个部分,我们处理两边的部分需要返回两个值,所以就不单独封装三路划分的单趟排序了

代码如下:

void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}int GetMid(int* a, int begin, int end)
{int mid = (begin + end) / 2;if (a[begin] > a[mid]){if (a[mid] > a[end])return mid;else if (a[begin] > a[end])return end;elsereturn begin;}else{if (a[begin] > a[end])return begin;else if (a[mid] > a[end])return end;elsereturn mid;}
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int mid = GetMid(a, begin, end);swap(&a[begin], &a[mid]);//由于begin和end要改变,提前保存,便于递归使用int left = begin;int right = end;int cur = begin + 1;int key = a[begin];while (cur <= end){if (a[cur] < key){swap(&a[cur], &a[begin]);begin++;cur++;}else if (a[cur] > key){swap(&a[cur], &a[end]);end--;}else{cur++;}}QuickSort(a, left, begin - 1);QuickSort(a, end + 1, right);
}

这篇关于[排序算法] 如何解决快速排序特殊情况效率低的问题------三路划分的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/572098

相关文章

Springboot项目启动失败提示找不到dao类的解决

《Springboot项目启动失败提示找不到dao类的解决》SpringBoot启动失败,因ProductServiceImpl未正确注入ProductDao,原因:Dao未注册为Bean,解决:在启... 目录错误描述原因解决方法总结***************************APPLICA编

解决pandas无法读取csv文件数据的问题

《解决pandas无法读取csv文件数据的问题》本文讲述作者用Pandas读取CSV文件时因参数设置不当导致数据错位,通过调整delimiter和on_bad_lines参数最终解决问题,并强调正确参... 目录一、前言二、问题复现1. 问题2. 通过 on_bad_lines=‘warn’ 跳过异常数据3

解决RocketMQ的幂等性问题

《解决RocketMQ的幂等性问题》重复消费因调用链路长、消息发送超时或消费者故障导致,通过生产者消息查询、Redis缓存及消费者唯一主键可以确保幂等性,避免重复处理,本文主要介绍了解决RocketM... 目录造成重复消费的原因解决方法生产者端消费者端代码实现造成重复消费的原因当系统的调用链路比较长的时

深度解析Nginx日志分析与499状态码问题解决

《深度解析Nginx日志分析与499状态码问题解决》在Web服务器运维和性能优化过程中,Nginx日志是排查问题的重要依据,本文将围绕Nginx日志分析、499状态码的成因、排查方法及解决方案展开讨论... 目录前言1. Nginx日志基础1.1 Nginx日志存放位置1.2 Nginx日志格式2. 499

SpringBoot监控API请求耗时的6中解决解决方案

《SpringBoot监控API请求耗时的6中解决解决方案》本文介绍SpringBoot中记录API请求耗时的6种方案,包括手动埋点、AOP切面、拦截器、Filter、事件监听、Micrometer+... 目录1. 简介2.实战案例2.1 手动记录2.2 自定义AOP记录2.3 拦截器技术2.4 使用Fi

kkFileView启动报错:报错2003端口占用的问题及解决

《kkFileView启动报错:报错2003端口占用的问题及解决》kkFileView启动报错因office组件2003端口未关闭,解决:查杀占用端口的进程,终止Java进程,使用shutdown.s... 目录原因解决总结kkFileViewjavascript启动报错启动office组件失败,请检查of

SQL Server安装时候没有中文选项的解决方法

《SQLServer安装时候没有中文选项的解决方法》用户安装SQLServer时界面全英文,无中文选项,通过修改安装设置中的国家或地区为中文中国,重启安装程序后界面恢复中文,解决了问题,对SQLSe... 你是不是在安装SQL Server时候发现安装界面和别人不同,并且无论如何都没有中文选项?这个问题也

SpringBoot 异常处理/自定义格式校验的问题实例详解

《SpringBoot异常处理/自定义格式校验的问题实例详解》文章探讨SpringBoot中自定义注解校验问题,区分参数级与类级约束触发的异常类型,建议通过@RestControllerAdvice... 目录1. 问题简要描述2. 异常触发1) 参数级别约束2) 类级别约束3. 异常处理1) 字段级别约束

java内存泄漏排查过程及解决

《java内存泄漏排查过程及解决》公司某服务内存持续增长,疑似内存泄漏,未触发OOM,排查方法包括检查JVM配置、分析GC执行状态、导出堆内存快照并用IDEAProfiler工具定位大对象及代码... 目录内存泄漏内存问题排查1.查看JVM内存配置2.分析gc是否正常执行3.导出 dump 各种工具分析4.

Python错误AttributeError: 'NoneType' object has no attribute问题的彻底解决方法

《Python错误AttributeError:NoneTypeobjecthasnoattribute问题的彻底解决方法》在Python项目开发和调试过程中,经常会碰到这样一个异常信息... 目录问题背景与概述错误解读:AttributeError: 'NoneType' object has no at