详解Java中使用泛型实现快速排序算法的方法_java

快速排序算法概念
快速排序一般基于递归实现。其思路是这样的：
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
， 快速排序
， 泛型
排序算法
快速排序算法详解、排序算法详解、快速排序算法、快速排序算法流程图、c语言快速排序算法，以便于您获取更多的相关知识。

时间： 2024-12-02 13:23:35

详解Java中使用泛型实现快速排序算法的方法_java的相关文章

详解Java中使用ImageIO类对图片进行压缩的方法_java

最近做项目需要图片压缩处理,网上找的方法大都使用了 com.sun.image.codec.jpeg.* 这个包中的JPEGImageEncoder类,引入这个包后一直报错,各种google百度,尝试了各种方法,包括手动引jre中的rt.jar,以及在eclipse中把受访问限制的API提示从ERROR改为WARNING,等等,然而这些都是不好使的,因为后来我发现我的java-7-openjdk-amd64中的rt.jar里边根本就没有com.sun.image.*,貌似这个类在java7中已经

详解Java中格式化日期的DateFormat与SimpleDateFormat类_java

DateFormat 1. DateFormat 介绍DateFormat 的作用是 格式化并解析"日期/时间".实际上,它是Date的格式化工具,它能帮助我们格式化Date,进而将Date转换成我们想要的String字符串供我们使用 不过DateFormat的格式化Date的功能有限,没有SimpleDateFormat强大:但DateFormat是SimpleDateFormat的父类.所以,我们先对DateFormat有个整体了解,然后再学习SimpleDateFormat. D

详解Java中使用externds关键字继承类的用法_java

理解继承是理解面向对象程序设计的关键.在Java中,通过关键字extends继承一个已有的类,被继承的类称为父类(超类,基类),新的类称为子类(派生类).在Java中不允许多继承.(1)继承 class Animal{ void eat(){ System.out.println("Animal eat"); } void sleep(){ System.out.println("Animal sleep"); } void breathe(){ System.ou

详解Java类库的概念以及import的使用方法_java

Java类库及其组织结构(Java API) Java 官方为开发者提供了很多功能强大的类,这些类被分别放在各个包中,随JDK一起发布,称为Java类库或Java API. API(Application Programming Interface, 应用程序编程接口)是一个通用概念. 例如我编写了一个类,可以获取计算机的各种硬件信息,它很强大很稳定,如果你的项目也需要这样一个功能,那么你就无需再自己编写代码,将我的类拿来直接用就可以.但是,我的类代码很复杂,让你读完这些代码不太现实,而且我也不

详解Java获取环境变量及系统属性的方法_java

环境变量这个概念不陌生, 就是操作系统的环境变量. 系统变量就是java本身维护的变量. 通过 System.getProperty 的方式获取. 对于不同的操作系统来说, 环境变量的处理可能会有一些不统一的地方, 比如说: 不区分大小写 等等. Java 获取环境变量Java 获取环境变量的方式很简单: System.getEnv()  得到所有的环境变量 System.getEnv(key) 得到某个环境变量的值   Map map = System.getenv(); Iterator i

详解Java中的正则表达式

详解Java中的正则表达式,并列出常用的正则表达式语法和一些常用的场景. 判断一个字符串是否是由数字组成: 当不使用正则表达式的时候的实现代码: public class RegexDemo01 { public static void main(String[] args) { String s = "23432324"; char c[] = s.toCharArray();//将字符串转换成字符数组 for (int i = 0; i < c.length; i++) {

详解Java中的指针、引用及对象的clone

对象|详解 Java语言的一个优点就是取消了指针的概念,但也导致了许多程序员在编程中常常忽略了对象与引用的区别,本文会试图澄清这一概念.并且由于Java不能通过简单的赋值来解决对象复制的问题,在开发过程中,也常常要要应用clone()方法来复制对象.本文会让你了解什么是影子clone与深度clone,认识它们的区别.优点及缺点.看到这个标题,是不是有点困惑:Java语言明确说明取消了指针,因为指针往往是在带来方便的同时也是导致代码不安全的根源,同时也会使程序的变得非常复杂难以理解,滥用指针写成的

详解java中finalize的实现与相应的执行过程_java

FinalReference引用 此类是一个package类型,表示它并不是公开的一部分,继承自Reference, 即表示也是一种特定的引用类型,因此每个包装在其中的对象在被回收之前,自己都会放到指定的referqyebceQueue当中. 这个引用对象专门为带finalize方法的类服务,可以理解为每一个有相应的方法的对象,其都会封装为一种finalRefernece对象. 因为finalize方法是object定义的,其默认实现为空.那么如果重写了此方法,那么方法体肯定不为空.即可以通过这

详解java中Reference的实现与相应的执行过程_java

一.Reference类型(除强引用) 可以理解为Reference的直接子类都是由jvm定制化处理的,因此在代码中直接继承于Reference类型没有任何作用.只能继承于它的子类,相应的子类类型包括以下几种.(忽略没有在java中使用的,如jnireference)      SoftReference      WeakReference      FinalReference      PhantomReference 上面的引用类型在相应的javadoc中也有提及.FinalRefere