文档章节

使用Java泛型实现快速排序(快排,Quicksort)算法

NealFeng
 NealFeng
发布于 2013/10/18 10:30
字数 1995
阅读 6880
收藏 3

快排算法的特点

  • 实用性强。
很多实际的项目中使用了快排算法。但通常对算法都进行了调整(tuning),比如Java.util.Arrays类中的sort函数就使用了快排算法,但使用了双参考值(Dual-Pivot Quicksort)等一些改进措施。由于快排算法为递归算法,可以用循环代替递归函数调用,改进性能。
  • 不需要额外的空间。
可以将数组中的数据直接交换位置实现排序,所以理论上不需要额外的空间。

时间复杂度

  • 平均情况:O(nlgn)
  • 最坏情况:O(n*n),发生在当数据已经是排序状态时

快排算法的基本原理

1、从数据中选取一个值a[i]作为参考
2、以a[i] 为参考,将数据分成2部分:P1、P2,P1中的数据全部≤a[i],P2中的数据全部>a[i],数据变为{{P1}{a[i]}{P2}}
3、将P1、P2重复上述步骤,直到各部分中只剩1个数据
4、数据完成升序排列 

示例:

原始数据:
    {3,9,8,5,2,1,6}
第1步:选取第1个数据:3
第2步:将数据分成2部分,左边≤3,右边大于>3:
    {2,1} {3} {9,8,5,6}
第3步:将各部分重复以上步骤,直到每部分只剩1个数据:
    {2,1} => {1} {2}
    {9,8,5,6} => {8,5,6} {9}=> {5,6} {8} {9}=> {5} {6} {8} {9}
第4步:数据完成升序排列:
    {1} {2} {3} {5} {6} {8} {9}

程序中数据通常保存在数组中,以int类型的数组为例,可以将上面的步骤写成一个quickSort函数原型:

quickSort(int begin, int end) { 
//begin为数组的第一个数据的索引值,end为数组的最后一个数据的索引值+1
    //如果只有1个数据或0个数据,则程序返回
    if( begin == end || begin == (end-1) ) return; 
    int p = in[begin];//p为选择的参考数据,选择第一个数据
    int a = begin +1; //a作为2部分数据分界线的索引值
    int b = a;//b为待比较的数据的索引值
    for( ; b < end; b++) {//将数组中的各个数据依次与参考数据进行比较
        if( in[b] < p) { //如果该数据<参考数据则将其移动到左边
            if(a == b){a++; continue;} //如果该数据已经在左边则不动
            int temp = in[a];//将数据移动到左边
            in[a] = in[b];
            in[b] = temp;
            a++;//将分界线右移
        }
    }
    in[begin] = in[a-1];//讲参考值移动到2组数据中间
    in[a-1] = p;
    if( a-1 > begin){ // 如果左边有数据则将其重复上述步骤
        quickSort(begin, a);
    } 
    if( end-1 > a ) {// 如果右边有数据则将其重复上述步骤
        quickSort(a, end);
    } 
    return; // 如果无数据返回
}


使用泛型实现快排算法

下面设计一个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


参考资料:

[1] 麻省理工学院公开课:算法导论> 快排及随机化算法
http://v.163.com/movie/2010/12/S/4/M6UTT5U0I_M6V2T7IS4.html

[2] Java官方API(Oracle Java SE7)源代码,下载安装JDK后,源代码位于安装根目录的src.zip文件中
http://www.oracle.com/technetwork/java/javase/downloads/jdk7-downloads-1880260.html

[3] OpenJDK源代码下载(包括了HotSpot虚拟机、各个系统下API的源代码,其中API源代码位于openjdk\jdk\src\share\classes文件夹下):
https://jdk7.java.net/source.html


© 著作权归作者所有

共有 人打赏支持
NealFeng
粉丝 25
博文 55
码字总数 36482
作品 0
朝阳
程序员
私信 提问
O(n*logn)级别的算法之二(快速排序)的三种实现方法详解及其与归并排序的对比

一,单路快排 1.测试用例: 1 #ifndef INC06QUICKSORTDEALWITHNEARLYORDEREDARRAYSORTTESTHELPERH 2 #define INC06QUICKSORTDEALWITHNEARLYORDEREDARRAYSORTTESTHELPERH 3 #include 4 #incl......

Tom-shushu
11/19
0
0
算法设计:两种快速排序代码实现

快速排序是一种高效且使用广泛的排序算法,在很多语言的标准库中自带的排序都是快速排序,所以我们也有必要了解快排的原理以及其实现方法。 快排的大致思想 快速排序实现的重点在于数组的拆分...

Sunrise_1018
11/23
0
0
JDK提供的排序算法是怎么实现的?

前几天整理的一套面试题,其中有一个问题就是Java的JDK中我们见到的Collections.sort()和Arrays.sort()这两个排序算法的实现方式是什么,很多小伙伴心里边默认的应该是快排,但是不全对或者理...

HOT_POT
07/29
0
0
函数式思维和函数式编程

作为一个对Hashell语言[1]彻头彻尾的新手,当第一次看到一个用这种语言编写的快速排序算法的优雅例子时,我立即对这种语言发生了浓厚的兴趣。下面就是这个例子: 我很困惑。如此的简单和漂亮...

oschina
2014/09/05
11.1K
24
08《Java核心技术》之Vector、ArrayList、LinkedList有何区别?

一、提出问题 我们在日常的工作中,能够高效地管理和操作数据是非常重要的。由于每个编程语言支持的数据结构不尽相同,比如我们最早接触到的 C 语言,需要自己实现很多基础数据结构,管理和操...

飞鱼说编程
10/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

特斯拉车主成功破解了自己Model 3汽车

据汽车博客Electrek消息,一位特斯拉车主成功破解了自己Model 3汽车,还在此基础上运行了Ubuntu。 这位叫trsohmers的网友表示,“功劳大多要归到Ingineerix的头上,他花了数月才找到初始的那...

linuxCool
15分钟前
0
0
Gitbook : random errors when using gitbook plugin on running "gitbook serve"

在执行gitbook serve时,会有不定的失败错误 参考问题 :#1309 解决方案: 更新gitbook版本,这个问题似乎是3版本的问题 , 官方也不打算在这个版本解决了。 更新 到最新版本后, 不再出现问...

ol_O_O_lo
30分钟前
1
0
提灯照暗,向内自省——《中国文化的深层结构》读书笔记3800字

提灯照暗,向内自省——《中国文化的深层结构》读书笔记3800字: 作者:王健茜;断断续续一个多月才读完了《中国文化的深层结构》,这并不是一本难懂的书,之所以读得慢,源于对书中观点的思...

原创小博客
32分钟前
1
0
高德地图-行政区域接口

1、获取全国各省信息 https://restapi.amap.com/v3/config/district?extensions=all&key=应用Key&s=rsv3&output=json 2、获取下级行政区域信息 https://restapi.amap.com/v3/config/distric......

voole
44分钟前
4
0
集群介绍 ..

12月19日任务 18.1 集群介绍 18.2 keepalived介绍 18.3/18.4/18.5 用keepalived配置高可用集群 一.集群介绍 根据功能划分为两大类:高可用和负载均衡 高可用集群通常为两台服务器,一台工作,...

hhpuppy
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部