详解Java中使用泛型实现快速排序算法的方法
作者:飞翔的猫咪 时间:2022-04-28 09:47:00
快速排序算法概念
快速排序一般基于递归实现。其思路是这样的:
1.选定一个合适的值(理想情况中值最好,但实现中一般使用数组第一个值),称为“枢轴”(pivot)。
2.基于这个值,将数组分为两部分,较小的分在左边,较大的分在右边。
3.可以肯定,如此一轮下来,这个枢轴的位置一定在最终位置上。
4.对两个子数组分别重复上述过程,直到每个数组只有一个元素。
5.排序完成。
基本实现方式:
public static void quickSort(int[] arr){
qsort(arr, 0, arr.length-1);
}
private static void qsort(int[] arr, int low, int high){
if (low < high){
int pivot=partition(arr, low, high); //将数组分为两部分
qsort(arr, low, pivot-1); //递归排序左子数组
qsort(arr, pivot+1, high); //递归排序右子数组
}
}
private static int partition(int[] arr, int low, int high){
int pivot = arr[low]; //枢轴记录
while (low<high){
while (low<high && arr[high]>=pivot) --high;
arr[low]=arr[high]; //交换比枢轴小的记录到左端
while (low<high && arr[low]<=pivot) ++low;
arr[high] = arr[low]; //交换比枢轴小的记录到右端
}
//扫描完成,枢轴到位
arr[low] = pivot;
//返回的是枢轴的位置
return low;
}
使用泛型实现快排算法
下面设计一个QuickSort类,包含了静态函数sort(),可以对任意类型数组进行排序。如果为对象类型数组,则该对象类型必须实现Comparable接口,这样才能使用compareTo函数进行比较。
使用了最基本的快排算法,没有进行优化处理。
源代码如下:
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
public class QuickSort {
@SuppressWarnings("unchecked")
//对上述快排函数原型修改,使其可以对任意对象类型数组进行排序。这个函数为内部使用,外部排序函数接口为sort(),sort函数要求对象必须实现Comparable接口,可以提供编译时类型检测,见后文。
private static void quickSort(Object[] in,int begin, int end) {
if( begin == end || begin == (end-1) ) return;
Object p = in[begin];
int a = begin +1;
int b = a;
for( ; b < end; b++) {
//该对象类型数组必须实现Comparable接口,这样才能使用compareTo函数进行比较
if( ((Comparable<Object>)in[b]).compareTo(p) < 0) {
if(a == b){a++; continue;}
Object temp = in[a];
in[a] = in[b];
in[b] = temp;
a++;
}
}
in[begin] = in[a-1];
in[a-1] = p;
if( a-1 > begin){
quickSort(in,begin, a);
}
if( end-1 > a ) {
quickSort(in,a, end);
}
return;
}
//使用泛型,对任意对象数组排序,该对象类型数组必须实现Comparable接口
public static <T extends Comparable<? super T>> void sort(T[] input){
quickSort(input,0,input.length);
}
//添加对List对象进行排序的功能,参考了Java中的Java.util.Collections类的sort()函数
public static <T extends Comparable<? super T>> void sort(List<T> list){
Object[] t = list.toArray();//将列表转换为数组
quickSort(t,0,t.length); //对数组进行排序
//数组排序完成后再写回到列表中
ListIterator<T> i = list.listIterator();
for (int j=0; j<t.length; j++) {
i.next();
i.set((T)t[j]);
}
}
//由于Java中原始数据类型(int、double、byte等)无法使用泛型,所以只能使用函数重载机制实现对这些原始类型数组(int[]、double[]、byte[]等)的排序。这里为了共用同一个排序函数,利用原始类型的(AutoBoxing,UnBoxing)机制将其封装为对应对象类型,组成新的对象数组,排序后再解封装,这样的缺点是需要额外的转换步骤、额外的空间保存封装后的数组。另一种方式是将排序代码复制到各个重载函数中,官方API中的Java.util.Arrays这个类中的sort()函数就是使用这种方法,可以从Arrays类的源代码看出。
public static void sort(int[] input){
Integer[] t = new Integer[input.length];
for(int i = 0; i < input.length; i++){
t[i] = input[i];//封装
}
quickSort(t,0,t.length);//排序
for(int i = 0; i < input.length; i++){
input[i] = t[i];//解封装
}
}
//double[]数组的重载函数
public static void sort(double[] input){
Double[] t = new Double[input.length];
for(int i = 0; i < input.length; i++){
t[i] = input[i];
}
quickSort(t,0,t.length);
for(int i = 0; i < input.length; i++){
input[i] = t[i];
}
}
//byte[]数组的重载函数
public static void sort(byte[] input){
Byte[] t = new Byte[input.length];
for(int i = 0; i < input.length; i++){
t[i] = input[i];
}
quickSort(t,0,t.length);
for(int i = 0; i < input.length; i++){
input[i] = t[i];
}
}
//short[]数组的重载函数
public static void sort(short[] input){
Short[] t = new Short[input.length];
for(int i = 0; i < input.length; i++){
t[i] = input[i];
}
quickSort(t,0,t.length);
for(int i = 0; i < input.length; i++){
input[i] = t[i];
}
}
//char[]数组的重载函数
public static void sort(char[] input){
Character[] t = new Character[input.length];
for(int i = 0; i < input.length; i++){
t[i] = input[i];
}
quickSort(t,0,t.length);
for(int i = 0; i < input.length; i++){
input[i] = t[i];
}
}
//float[]数组的重载函数
public static void sort(float[] input){
Float[] t = new Float[input.length];
for(int i = 0; i < input.length; i++){
t[i] = input[i];
}
quickSort(t,0,t.length);
for(int i = 0; i < input.length; i++){
input[i] = t[i];
}
}
//测试用的main函数
public static void main(String[] args) {
//生产一个随机数组成的int[]数组,用来测试
int LEN = 10;
int[] input = new int[LEN];
Random r = new Random();
System.out.print("int[] before sorting: ");
for(int i = 0; i < input.length; i++) {
input[i] = r.nextInt(10*LEN);
System.out.print(input[i] + " ");
}
System.out.println();
System.out.print("int[] after sorting: ");
sort(input);
for(int i : input) {
System.out.print(i + " ");
}
System.out.println();
//生成一个字符串数组,用来测试
String[] s = new String[]{"b","a","e","d","f","c"};
System.out.print("String[] before sorting: ");
for(int i = 0; i < s.length; i++) {
System.out.print(s[i] + " ");
}
System.out.println();
System.out.print("String[] after sorting: ");
sort(s);
for(int i = 0; i < s.length; i++) {
System.out.print(s[i] + " ");
}
System.out.println();
//生成一个字符串列表,用来测试
List<String> l = new LinkedList<String>();
s = new String[]{"b","a","e","d","f","c"};
System.out.print("LinkedList<String> before sorting: ");
for (int j=0; j<s.length; j++) {
l.add(s[j]);
System.out.print(s[j] + " ");
}
System.out.println();
sort(l);
System.out.print("LinkedList<String> after sorting: ");
for (String ts : l) {
System.out.print(ts + " ");
}
System.out.println();
}
}
运行main函数测试,从输出可以看出QuickSort类工作正常:
int[] before sorting: 65 48 92 26 3 8 59 21 16 45
int[] after sorting: 3 8 16 21 26 45 48 59 65 92
String[] before sorting: b a e d f c
String[] after sorting: a b c d e f
LinkedList<String> before sorting: b a e d f c
LinkedList<String> after sorting: a b c d e f
标签:Java,快速排序
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
解析Android 8.1平台SystemUI 导航栏加载流程
2023-06-23 15:21:21
详解java接口基础知识附思维导图
2023-11-09 10:07:28
![](https://img.aspxhome.com/file/2023/1/58861_0s.png)
优化MyBatis配置文件中的配置详解
2023-11-10 14:03:51
![](https://img.aspxhome.com/file/2023/7/59077_0s.png)
为什么rest接口返回json建议采用下划线形式,不要用驼峰
2023-06-24 23:23:16
一文带你搞懂Java8的LocalDateTime
2023-11-10 02:02:22
![](https://img.aspxhome.com/file/2023/4/59234_0s.png)
基于ClasspathResource路径问题的解决
2022-03-29 21:23:22
![](https://img.aspxhome.com/file/2023/6/66536_0s.png)
详解Java中Period类的使用方法
2023-11-28 21:04:44
Java AQS信号量Semaphore的使用
2021-06-11 17:10:44
Springboot通过run启动web应用的方法
2021-08-30 01:57:37
![](https://img.aspxhome.com/file/2023/7/64527_0s.png)
Java面向对象实现汽车租赁系统
2023-05-20 07:03:06
![](https://img.aspxhome.com/file/2023/8/64428_0s.jpg)
Java提取2个集合中的相同和不同元素代码示例
2023-11-28 05:48:41
MyBatis-Plus实现分页的方法使用详解
2023-02-14 18:22:16
![](https://img.aspxhome.com/file/2023/6/60026_0s.png)
java实现分页显示效果
2021-12-29 20:17:43
![](https://img.aspxhome.com/file/2023/8/61378_0s.jpg)
Java算法之递归算法计算阶乘
2021-06-30 14:10:56
![](https://img.aspxhome.com/file/2023/4/63454_0s.png)
详解Spring boot使用Redis集群替换mybatis二级缓存
2023-03-09 17:17:38
MyBatis JdbcType 与Oracle、MySql数据类型对应关系说明
2023-08-23 02:23:06
![](https://img.aspxhome.com/file/2023/6/58276_0s.jpg)
springboot如何读取配置文件到静态工具类
2023-11-28 04:44:54
![](https://img.aspxhome.com/file/2023/6/60036_0s.png)
Android之复选框对话框用法实例分析
2023-10-03 05:07:03
![](https://img.aspxhome.com/file/2023/1/84751_0s.png)
SpringSecurity实现访问控制url匹配
2021-11-03 00:18:16
![](https://img.aspxhome.com/file/2023/1/63401_0s.jpg)
保证缓存和数据库的数据一致性详解
2023-11-18 08:10:44
![](https://img.aspxhome.com/file/2023/3/59573_0s.png)