`
javaG
  • 浏览: 554956 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

java 快速排序demo

    博客分类:
  • java
阅读更多
快速排序算法思想如下,先选取一个元素作为基准,然后根据这个基准依次比较整个数列,最后把这个数列分为两类,例如,左边的数都不比这个基准大,右边的全比基准大,然后把这个基准放在中间,二分这两类。然后再把这个这个数列分成两块,在用这个算法。

package cn.lsd;

import java.util.Comparator;
import java.util.Random;

/**
 *
 * @date   2008-11-29 
 * @author lsd
 */
public class QuickSort {
    public static final Random RND = new Random();

    private void swap(Object[] array, int i, int j) {
        Object tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    private int partition(Object[] array, int begin, int end, Comparator cmp) {
        int index = begin + RND.nextInt(end - begin + 1);
        Object pivot = array[index];
        swap(array, index, end);	
        for (int i = index = begin; i < end; ++ i) {
            if (cmp.compare(array[i], pivot) <= 0) {
                swap(array, index++, i);//<=>swap(array,index,i);index++;
            }
        }
        swap(array, index, end);	
        return (index);
    }

    private void qsort(Object[] array, int begin, int end, Comparator cmp) {
        if (end > begin) {
            int index = partition(array, begin, end, cmp);
            qsort(array, begin, index - 1, cmp);
            qsort(array, index + 1,  end,  cmp);
        }
    }

    public void sort(Object[] array, Comparator cmp) {
        qsort(array, 0, array.length - 1, cmp);
    }

    
    public static void main(String[] args){
        Integer[] a= new Integer[10];
        for(int i=0;i<10;i++){
            a[i]=10-i;
            System.out.println("a["+i+"]="+a[i].intValue());
        }

        Comparator<Integer> cmp =   new Comparator<Integer>(){
                                      public int compare(Integer o1, Integer o2) {
                                        return (o1.intValue()<o2.intValue()?-1:1);
                                      }
                                    };
                                    
        new QuickSort().sort(a, cmp);
        
        for(int i=0;i<10;i++){
            System.out.println("a["+i+"]="+a[i].intValue());
        }
    }
}

分享到:
评论

相关推荐

    Java各种排序算法Demo

    本资料包"Java各种排序算法Demo"聚焦于通过Java代码展示不同的排序算法,旨在帮助开发者理解和应用这些算法。 首先,我们来探讨几种基础的排序算法: 1. **冒泡排序**:冒泡排序是一种简单的排序算法,通过重复...

    基于java实现的快速排序算法 Demo

    在这个Java实现的Demo中,我们将深入理解快速排序的工作原理,并通过代码示例来演示其具体实现。 1. **快速排序的基本原理** 快速排序的核心是选择一个基准值(pivot),然后将数组分为两部分:一部分的元素都小于...

    JAVA快速排序法.pdf

    2. 快速排序的Java实现:通过编写一个主类Demo2,其中包含main方法,用以启动程序和定义测试数组。然后定义一个或多个排序类(如QuickSort1和QuickSort2),在这些类中实现快速排序算法的核心逻辑。 3. 快速排序的...

    Java demo 算法笔记

    在算法方面,Java提供了丰富的数据结构和算法实现,如排序算法(冒泡排序、快速排序、归并排序)、查找算法(二分查找、哈希查找)以及图算法、树算法等。算法是解决问题的关键,理解并能熟练应用这些算法能大大提高...

    java 策略模式demo

    1. 策略接口:这个接口定义了一组相关或相互排斥的操作,比如不同的排序算法(如冒泡排序、快速排序等)。 2. 具体策略类:这些类实现了策略接口中定义的方法,每个类代表一个特定的策略。例如,可能会有...

    JAVA快速排序法[借鉴].pdf

    在主类`Demo2`中,创建了两个快速排序对象`QuickSort1`和`QuickSort2`,分别对一个无序数组进行排序。排序完成后,遍历并打印排序后的数组,展示快速排序的效果。 快速排序的平均时间复杂度为O(n log n),最坏情况...

    java版支付宝支付Demo

    Java版支付宝支付Demo是针对开发者提供的一个集成支付宝支付功能的示例项目,它包含了必要的库文件和示例代码,帮助开发者快速理解和实现支付宝接口的调用。在这个Demo中,主要涉及以下几个关键知识点: 1. **...

    Java微信支付Demo

    Java Demo中会使用MD5或HMAC-SHA256等算法进行签名,签名过程需要包括所有请求参数,并按照特定顺序排序。 4. **统一下单接口**:这是支付流程的起点,开发者需要通过此接口生成预支付交易会话标识(prepay_id),...

    微信支付 java后端demo

    微信支付Java后端Demo是一个详尽的开发示例,旨在帮助开发者快速理解和实施微信支付功能。这个Demo包含了处理微信支付过程中可能遇到的各种场景和问题,从而避免开发者在实际开发时遭遇不必要的困扰。以下是对这个...

    各种排序算法Demo

    本资源"各种排序算法Demo"提供了一系列用Java语言实现的排序算法示例,旨在帮助学习者理解和掌握这些算法的工作原理及其应用。以下是这些排序算法的详细介绍: 1. 直接插入排序(直接插入法): 直接插入排序是一...

    Java 集合类 简单Demo

    `HashMap`提供快速的查找,插入和删除操作,而`TreeMap`则根据键的自然顺序或自定义比较器保持键的排序。 在`CollectionsTest.java`文件中,可能包含了以下示例代码: 1. 创建集合:例如`ArrayList&lt;String&gt; list =...

    平时练习的Java的demo

    Java中可以实现各种算法,如排序(快速排序、归并排序、冒泡排序等)、查找(二分查找、哈希查找等)和图/树算法(深度优先搜索、广度优先搜索等)。通过这些练习,可以提高解决复杂问题的能力。 5. **JVM(Java...

    排序算法总结 实现 Demo (Java)

    快速排序是一种高效的排序算法,采用了分治的思想。它的主要步骤包括: - 选择一个基准元素。 - 重新排列数组,使得所有小于基准的元素位于基准的左边,大于基准的元素位于基准的右边,这个过程称为分区操作。 - ...

    EasyUI+java demo

    【EasyUI+Java Demo】是一个基于EasyUI框架和Java技术的实战项目,旨在提供一个直观且详尽的示例,帮助开发者快速理解并掌握EasyUI的使用方法。EasyUI是一款基于jQuery的轻量级前端组件库,它为开发人员提供了丰富的...

    交换排序Java实现

    本篇文章将深入探讨在Java中实现两种经典的排序算法:冒泡排序和快速排序。 首先,让我们从冒泡排序开始。冒泡排序是一种简单直观的排序算法,它重复地遍历待排序的数列,一次比较两个元素,如果他们的顺序错误就把...

    lucene for java 简单demo

    **Lucene for Java 简单DEMO** Lucene 是一个全文搜索引擎库,由Apache软件基金会开发并维护,它提供了一个高效、可扩展的搜索框架,使得开发者可以轻易地在自己的应用程序中集成全文检索功能。Java是Lucene的主要...

    java汉字笔画排序源码

    然后,可以使用各种排序算法(如快速排序、归并排序或冒泡排序)对汉字列表进行排序。考虑到性能,可能会选择时间复杂度较低的排序算法。 在Java中,可以使用`java.util.Comparator`接口自定义比较规则,根据笔画数...

    结合jquery官方demo自己修改的java+mysql的demo

    在这个“结合jquery官方demo自己修改的java+mysql的demo”项目中,我们看到了一个整合了前端jQuery库与后端Java以及MySQL数据库的应用示例。这个项目可能是为了展示如何使用jQuery来构建用户界面,并通过Java后端与...

    java中常见排序的所有demo,包含冒泡,选择,插入,快速,堆,希尔,二叉树等

    4. **快速排序(Quick Sort)**:快速排序是一种高效的排序算法,采用分治策略。首先选取一个基准值,将数组分为两部分,一部分的元素都比基准值小,另一部分的元素都比基准值大,然后对这两部分再分别进行快速排序...

    datatable java web运行demo 包含增删改查

    本项目是一个`Datatable`与Java后端结合的实战运行Demo,涵盖了基本的数据表操作:增、删、改、查,旨在帮助开发者快速理解和应用`Datatable`。 首先,让我们深入理解`Datatable`。`Datatable`是一个用于HTML表格的...

Global site tag (gtag.js) - Google Analytics