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

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

前言

        在[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循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

mysql出现ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的解决方法

《mysql出现ERROR2003(HY000):Can‘tconnecttoMySQLserveron‘localhost‘(10061)的解决方法》本文主要介绍了mysql出现... 目录前言:第一步:第二步:第三步:总结:前言:当你想通过命令窗口想打开mysql时候发现提http://www.cpp

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

springboot报错Invalid bound statement (not found)的解决

《springboot报错Invalidboundstatement(notfound)的解决》本文主要介绍了springboot报错Invalidboundstatement(not... 目录一. 问题描述二.解决问题三. 添加配置项 四.其他的解决方案4.1 Mapper 接口与 XML 文件不匹配

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时