有重复元素的快速排序

news/2024/10/22 7:29:08/

当涉及到处理重复元素的快速排序时,可以使用荷兰国旗问题的方法,也就是三路划分。下面是使用 Java 实现的示例代码:

import java.util.Arrays;public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {int[] pivotIndices = partition(arr, low, high);quickSort(arr, low, pivotIndices[0] - 1);quickSort(arr, pivotIndices[1] + 1, high);}}public static int[] partition(int[] arr, int low, int high) {int pivot = arr[low];int smaller = low;int equal = low;int larger = high;while (equal <= larger) {if (arr[equal] < pivot) {swap(arr, smaller, equal);smaller++;equal++;} else if (arr[equal] == pivot) {equal++;} else {swap(arr, equal, larger);larger--;}}return new int[]{smaller, larger};}public static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {int[] arr = {3, 6, 8, 2, 3, 8, 4, 6, 3, 2};System.out.println("Original Array: " + Arrays.toString(arr));quickSort(arr, 0, arr.length - 1);System.out.println("Sorted Array: " + Arrays.toString(arr));}
}

这段代码实现了一个快速排序算法,其中的 quickSort 方法用于递归地进行排序,partition 方法用于进行三路划分(小于、等于和大于 pivot)。在 main 方法中,展示了如何使用这个快速排序算法对含有重复元素的数组进行排序。

运行此 Java 代码将对数组进行排序,并保持重复元素的相对顺序。


http://www.ppmy.cn/news/1217794.html

相关文章

Unity中【UniTask异步流程】如何进行【步骤分段】、【步骤撤销】、【步骤跳转】、【取消异步任务】

一、UniTask和Task UniTask是Unity中的Task实现&#xff0c;Task是C#中实现异步操作的一个模块(类)。UniTask与Task有着同样的使用思路&#xff08;使用习惯&#xff0c;常用API等&#xff09;&#xff0c;可以说UniTask是借鉴Task而开发出来的。 二、需求的来源 以前有一个…

Oracle 查询语句使用不等于(<>或者!=)会过滤空值的解决方案

在 Oracle 数据库中&#xff0c;使用不等于符号&#xff08;<> 或 !&#xff09;时&#xff0c;确实会将 NULL 值过滤掉&#xff0c;因为 NULL 代表未知值。要解决这个问题&#xff0c;可以使用 增加 OR IS NULL 或者 NVL函数来筛选出包含 NULL 的值。 例如&#xff0c;…

Spring整合redis的key时出现\xac\xed\x00\x05t\前缀问题

AutowiredRedisTemplate redisTemplate;User usernew User(5,"tomhs","tttt");ValueOperations opsForValue redisTemplate.opsForValue();//存放key,opsForValue.set("user"user.getId(),user);//读取数据;System.out.println(opsForValue.get…

一篇博客读懂栈——Stack

目录 一、栈的概念与结构 1.1栈的概念 1.2栈的结构 二、栈的实现 2.1开始前准备stack.h 2.2栈的初始化STInit 2.3栈的销毁STDestroy 2.4栈顶插入STPush 2.5栈顶删除STPop 2.6取栈顶元素STTop 2.7检查栈是否为空STEmpty 2.8栈的元素个数STSize 一、栈的概念与结…

卫星通信和800MHz双管齐下,中国电信对中国移动发起新挑战

依靠国内某科技企业的宣传&#xff0c;卫星通信大热&#xff0c;中国电信也由此成为受益者&#xff0c;日前中国电信又大举招标25万座800MHz 5G基站&#xff0c;显示出中国电信积极以技术优势挑战中国移动。 一、中国电信急起直追 自从4G时代以来&#xff0c;中国电信就在国内通…

2023 年最新企业微信官方会话机器人开发详细教程(更新中)

目标是开发一个简易机器人&#xff0c;能接收消息并作出回复。 获取企业 ID 企业信息页面链接地址&#xff1a;https://work.weixin.qq.com/wework_admin/frame#profile 自建企业微信机器人 配置机器人应用详情 功能配置 接收消息服务器配置 配置消息服务器配置 配置环境变量…

2023nacos源码解读第3集——nacos-client核心功能之微服务调用和配置管理测试

文章目录 1、测试项目2、项目注意事项3、 测试核心功能3.1 测试服务调用与负载均衡3.2 测试配置监听 4、参考文档 1、测试项目 项目地址 nacos-service-a nacos-service-b 2、项目注意事项 项目初始化可以使用aliyun spring initializer ,以更方便的使用springcloud alibaba…

vscode使用flake8设置单行最长字符限制设置失败的问题

vscode使用flake8设置单行最长字符限制设置失败的问题 问题描述解决方案 问题描述 如图所示&#xff0c;使用flake8单行字数过长&#xff0c;就会有有红色底的波浪线 一般情况下很多教程都会让你在setting.json里面设置 但是我打开我的setting.json&#xff0c;发现我已经进…