图解Java排序算法之快速排序的三数取中法
作者:dreamcatcher-cx 发布时间:2022-02-26 17:58:23
标签:Java,排序算法,快速排序,三数取中法
基本步骤
三数取中
在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。
根据枢纽值进行分割
代码实现
package sortdemo;
import java.util.Arrays;
/**
* Created by chengxiao on 2016/12/14.
* 快速排序
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序结果:" + Arrays.toString(arr));
}
/**
* @param arr
* @param left 左指针
* @param right 右指针
*/
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
//获取枢纽值,并将其放在当前待处理序列末尾
dealPivot(arr, left, right);
//枢纽值被放在序列末尾
int pivot = right - 1;
//左指针
int i = left;
//右指针
int j = right - 1;
while (true) {
while (arr[++i] < arr[pivot]) {
}
while (j > left && arr[--j] > arr[pivot]) {
}
if (i < j) {
swap(arr, i, j);
} else {
break;
}
}
if (i < right) {
swap(arr, i, right - 1);
}
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
}
/**
* 处理枢纽值
*
* @param arr
* @param left
* @param right
*/
public static void dealPivot(int[] arr, int left, int right) {
int mid = (left + right) / 2;
if (arr[left] > arr[mid]) {
swap(arr, left, mid);
}
if (arr[left] > arr[right]) {
swap(arr, left, right);
}
if (arr[right] < arr[mid]) {
swap(arr, right, mid);
}
swap(arr, right - 1, mid);
}
/**
* 交换元素通用处理
*
* @param arr
* @param a
* @param b
*/
private static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
排序结果
[1, 2, 3, 4, 5, 6, 7, 8]
来源:https://www.cnblogs.com/chengxiao/p/6262208.html
0
投稿
猜你喜欢
- 1)首先启动hadoop2个进程,进入hadoop/sbin目录下,依次启动如下命令[root@node02 sbin]# pwd/usr/
- 前言在web开发过程中涉及到表格时,例如dataTable,就会产生分页的需求,通常我们将分页方式分为两种:前端分页和后端分页。前端分页一次
- 为什么需要网关呢?我们知道我们要进入一个服务本身,很明显我们没有特别好的办法,直接输入IP地址+端口号,我们知道这样的做法很糟糕的,这样的做
- CSRF介绍CSRF(Cross-site request forgery),中文名称:跨站请求伪造,也被称为:one click atta
- 在线用户使用HttpSessionListener * 统计 每当一个session会话建立 在线用户人数+1每当一
- 下面是一个AOP实现的简单例子:首先定义一些业务方法:/** * Created with IntelliJ IDEA. 
- 单线程实现文件分割在老的FAT32文件系统中,最大的单个文件大小必须保存在4G内,对于经常看电影的我这个是不能允许的。不过现在Windows
- @Autowired加到接口上但获取的是实现类问题Spring的@Autowired加到接口上但获取的是实现类? &
- 前言先简单介绍下我们的使用场景,线上5台Broker节点的kafka承接了所有binlog订阅的数据,用于Flink组件接收数据做数据中台的
- java模拟TCP通信实现客户端上传文件到服务器端,供大家参考,具体内容如下客户端package com.zr;import java.io
- 项目结构项目路径可以自己定义,只要路径映射正确就可以pom.xml <properties> <spring.versio
- 线程池示例在分析线程池之前,先看一个简单的线程池示例。import java.util.concurrent.Executors;impor
- 这篇文章主要介绍了JAVA如何按字节截取字符串,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参
- 背景传说里玉皇大帝派龙王马上降雨到共光一带,龙王接到玉皇大帝命令,立马从海上调水,跑去共光施云布雨,但粗心又着急的龙王不小心把海里的鲸鱼随着
- 笔者计划为大家介绍分布式文件系统,用于存储应用的图片、word、excel、pdf等文件。在开始介绍分布式文件系统之前,为大家介绍一下使用本
- 一、几句话使用Gradle及其推荐的项目框架把密码等敏感数据放入gradle.properties不要自己写Http客户端,使用Volley
- 修改FeginCilent定义的服务名到指定服务通过覆盖类来修改对应的服务名,这里将所有的FeginClient对应的服务名都修改好。pac
- 质数又称素数。一个大于1的自然数,如果除了1和它自身外,不能被其他自然数整除的数;否则称为合数。根据算术基本定理,每一个比1大的整数,要么本
- java文件打包jar运行有效步骤:1.cmd 到当前目录(默认包主类所在目录为例) set classpath = 默认包主类所在目录2.
- dom4j是一个非常优秀的Java XML API,具有性能优异、功能强大和极端易用使用的特点,同时它也是一个开放源工具。可以在这个地址ht