数据结构基础10:三路划分(解决快速排序的问题)

2023-10-15 00:52

本文主要是介绍数据结构基础10:三路划分(解决快速排序的问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

快速排序之:三路划分

  • 一.题目描述:
    • 1.方法一:三路划分:
      • >1.为什么会有三路划分?
      • >2.三路划分的主要思路:
    • 2.方法二:取值更加的随机:
      • >1.产生的问题:
      • >2.在一个方向可以去解决:

一.题目描述:

请添加图片描述
题目链接:

这个题目有一个问题在hore 挖坑 前后指针 递归或者非递归 并且加上了三数取中的自己实现的快速排序方法但是过不了上面这个oj‘题目:

1.方法一:三路划分:

>1.为什么会有三路划分?

因为在lectcoude上自己写的快速排序通过不了报超出时间限制:
针对了快速排序的明显缺陷设计了测试用例:

请添加图片描述

>2.三路划分的主要思路:

1.我们下面使用一个动图去演示代码的执行逻辑过程!
2.结束一次会发现产生了一个效果就是非常多相同的中间值到了中间并且已经排和了一个比较大的范围,之后我们递归进入左和右的区间范围再一次进入这样的操作就比较方便:

请添加图片描述

代码实现:

void partsort4(int* arr , int beging , int end)
{if (beging >= end)return;int tmp = arr[beging];int left = beging;int right = end;int cur = left + 1;while (cur <= right){//1.cur的值和tmp的相等的时候就直接cur++:if (arr[cur] == tmp){cur++;}//2.cur的值比tmp的值小的时候就进行left和cur的交换并且++两个:else if (arr[cur] < tmp){swap(&arr[cur], &arr[left]);cur++;left++;}//3.cur的值比tmp的值大的时候//就进行right和cur的交换并且--一个right//不++cur是因为我们不知道交换来的数值具体和他mp的大小关系:else if (arr[cur] > tmp){swap(&arr[cur], &arr[right]);right--;}}//结束循环之后:left到right值相等并且是一个大范围://递归进入左右:partsort4(arr, beging, left - 1);partsort4(arr, right + 1, end);
}

2.方法二:取值更加的随机:

>1.产生的问题:

我们运行代码在上面的oj里面出现了下面的问题说通过了所有的测试用例但是呢结果显示我们通过了所有的测试用例但是时间复杂度过高?

这又是怎么回事呢有没有什么办法解决呢?

在这里插入图片描述

>2.在一个方向可以去解决:

1.我们前面三数取中的那个数值就是整个数组里面值比较多并且适合中间区域的数值,但是三数取中有可能导致取到的tmp值不是这个数组范围中最适合作为tmp的数值 (tmp满足是这个数组中最多的一个数值中间数值才那最多左右范围才能越小!)
2,总结:在一个重复数据比较多的数组中三数取中和随机获取,随机获取->获取到的那个值比三数取中更加容易得到较多数值的那个值!!!

请添加图片描述

代码实现!

void swap(int* n1 , int *n2)
{int tmp = *n1;*n1 = *n2;*n2 = tmp;
}int getmin(int* arr,int left,int right)
{int min = (left + right) / 2;if (arr[left] < arr[right]){if (arr[min] < arr[left]){return left;}else if (arr[min] < arr[right]){return min;}else{return right;}}else if(arr[left]>arr[right]){if (arr[min] > arr[left]){return left;}else if (arr[min] > arr[right]){return  min;}else{return right;}}return left;
}
//2.三路划分:
void partsort4(int* arr , int beging , int end)
{if (beging >= end)return;//范围不一定从0开始int ran = beging + (rand() % (end - beging));swap(&arr[ran], &arr[beging]);int tmp = arr[beging];int left = beging;int right = end;int cur = left + 1;while (cur <= right){//1.cur的值和tmp的相等的时候就直接cur++:if (arr[cur] == tmp){cur++;}//2.cur的值比tmp的值小的时候就进行left和cur的交换并且++两个:else if (arr[cur] < tmp){swap(&arr[cur], &arr[left]);cur++;left++;}//3.cur的值比tmp的值大的时候//就进行right和cur的交换并且--一个right//不++cur是因为我们不知道交换来的数值具体和他mp的大小关系:else if (arr[cur] > tmp){swap(&arr[cur], &arr[right]);right--;}}//结束循环之后:left到right值相等并且是一个大范围://递归进入左右:partsort4(arr, beging, left - 1);partsort4(arr, right + 1, end);
}int* sortArray(int* nums, int numsSize, int* returnSize){srand((unsigned int)time(NULL));partsort4(nums,0,numsSize-1);*returnSize = numsSize;return nums;
}

这篇关于数据结构基础10:三路划分(解决快速排序的问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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.

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

springboot security快速使用示例详解

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

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

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

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

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

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. 不同操作