`
jiayj198609
  • 浏览: 149848 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

各种排序算法java实现

    博客分类:
  • Java
阅读更多
package org.rut.util.algorithm.support;
 
import org.rut.util.algorithm.SortUtil;
/**
 * @author treeroot
 * @since 2010-11-22
 * @version 1.0
 */
public class InsertSort implements SortUtil.Sort{
 
    /* (non-Javadoc)
     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
     */
    public void sort(int[] data) {
        int temp;
        for(int i=1;i<data.length;i++){
            for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
                SortUtil.swap(data,j,j-1);
            }
        }        
    }
 
}


冒泡排序:
 
package org.rut.util.algorithm.support;
 
import org.rut.util.algorithm.SortUtil;
 
/**
 * @author treeroot
 * @since 2010-11-22
 * @version 1.0
 */
public class BubbleSort implements SortUtil.Sort{
 
    /* (non-Javadoc)
     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
     */
    public void sort(int[] data) {
        int temp;
        for(int i=0;i<data.length;i++){
            for(int j=data.length-1;j>i;j--){
                if(data[j]<data[j-1]){
                    SortUtil.swap(data,j,j-1);
                }
            }
        }
    }
 
}
 

选择排序:
 
package org.rut.util.algorithm.support;
 
import org.rut.util.algorithm.SortUtil;
 
/**
 * @author treeroot
 * @since 2010-11-22
 * @version 1.0
 */
public class SelectionSort implements SortUtil.Sort {
 
    /*
     * (non-Javadoc)
     * 
     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
     */
    public void sort(int[] data) {
        int temp;
        for (int i = 0; i >< data.length; i++) {
            int lowIndex = i;
            for (int j = data.length - 1; j > i; j--) {
                if (data[j] < data[lowIndex]) {
                    lowIndex = j;
                }
            }
            SortUtil.swap(data,i,lowIndex);
        }
    }
 
}
 

Shell排序:
 
package org.rut.util.algorithm.support;
 
import org.rut.util.algorithm.SortUtil;
 
/**
 * @author treeroot
 * @since 2010-11-22
 * @version 1.0
 */
public class ShellSort implements SortUtil.Sort{
 
    /* (non-Javadoc)
     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
     */
    public void sort(int[] data) {
        for(int i=data.length/2;i>2;i/=2){
            for(int j=0;j<i;j++){
                insertSort(data,j,i);
            }
        }
        insertSort(data,0,1);
    }
 
    /**
     * @param data
     * @param j
     * @param i
     */
    private void insertSort(int[] data, int start, int inc) {
        int temp;
        for(int i=start+inc;i<data.length;i+=inc){
            for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
                SortUtil.swap(data,j,j-inc);
            }
        }
    }
 
}
 

快速排序:
 
package org.rut.util.algorithm.support;
 
import org.rut.util.algorithm.SortUtil;
 
/**
 * @author treeroot
 * @since 2010-11-22
 * @version 1.0
 */
public class QuickSort implements SortUtil.Sort{
 
    /* (non-Javadoc)
     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
     */
    public void sort(int[] data) {
        quickSort(data,0,data.length-1);        
    }
    private void quickSort(int[] data,int i,int j){
        int pivotIndex=(i+j)/2;
        //swap
        SortUtil.swap(data,pivotIndex,j);
        
        int k=partition(data,i-1,j,data[j]);
        SortUtil.swap(data,k,j);
        if((k-i)>1) quickSort(data,i,k-1);
        if((j-k)>1) quickSort(data,k+1,j);
        
    }
    /**
     * @param data
     * @param i
     * @param j
     * @return
     */
    private int partition(int[] data, int l, int r,int pivot) {
        do{
           while(data[++l]<pivot);
           while((r!=0)&&data[--r]>pivot);
           SortUtil.swap(data,l,r);
        }
        while(l<r);
        SortUtil.swap(data,l,r);        
        return l;
    }
 
}


改进后的快速排序:
 
package org.rut.util.algorithm.support;
 
import org.rut.util.algorithm.SortUtil;
 
/**
 * @author treeroot
 * @since 2010-11-22
 * @version 1.0
 */
public class ImprovedQuickSort implements SortUtil.Sort {
 
    private static int MAX_STACK_SIZE=4096;
    private static int THRESHOLD=10;
    /* (non-Javadoc)
     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
     */
    public void sort(int[] data) {
        int[] stack=new int[MAX_STACK_SIZE];
        
        int top=-1;
        int pivot;
        int pivotIndex,l,r;
        
        stack[++top]=0;
        stack[++top]=data.length-1;
        
        while(top>0){
            int j=stack[top--];
            int i=stack[top--];
            
            pivotIndex=(i+j)/2;
            pivot=data[pivotIndex];
            
            SortUtil.swap(data,pivotIndex,j);
            
            //partition
            l=i-1;
            r=j;
            do{
                while(data[++l]<pivot);
                while((r!=0)&&(data[--r]>pivot));
                SortUtil.swap(data,l,r);
            }
            while(l<r);
            SortUtil.swap(data,l,r);
            SortUtil.swap(data,l,j);
            
            if((l-i)>THRESHOLD){
                stack[++top]=i;
                stack[++top]=l-1;
            }
            if((j-l)>THRESHOLD){
                stack[++top]=l+1;
                stack[++top]=j;
            }
            
        }
        //new InsertSort().sort(data);
        insertSort(data);
    }
    /**
     * @param data
     */
    private void insertSort(int[] data) {
        int temp;
        for(int i=1;i<data.length;i++){
            for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
                SortUtil.swap(data,j,j-1);
            }
        }       
    }
 
}
 

归并排序:
 
package org.rut.util.algorithm.support;
 
import org.rut.util.algorithm.SortUtil;
 
/**
 * @author treeroot
 * @since 2010-11-22
 * @version 1.0
 */
public class MergeSort implements SortUtil.Sort{
 
    /* (non-Javadoc)
     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
     */
    public void sort(int[] data) {
        int[] temp=new int[data.length];
        mergeSort(data,temp,0,data.length-1);
    }
    
    private void mergeSort(int[] data,int[] temp,int l,int r){
        int mid=(l+r)/2;
        if(l==r) return ;
        mergeSort(data,temp,l,mid);
        mergeSort(data,temp,mid+1,r);
        for(int i=l;i<=r;i++){
            temp[i]=data[i];
        }
        int i1=l;
        int i2=mid+1;
        for(int cur=l;cur<=r;cur++){
            if(i1==mid+1)
                data[cur]=temp[i2++];
            else if(i2>r)
                data[cur]=temp[i1++];
            else if(temp[i1]<temp[i2])
                data[cur]=temp[i1++];
            else
                data[cur]=temp[i2++];            
        }
    }
 
}
 

改进后的归并排序:
 
package org.rut.util.algorithm.support;
 
import org.rut.util.algorithm.SortUtil;
 
/**
 * @author treeroot
 * @since 2010-11-22
 * @version 1.0
 */
public class ImprovedMergeSort implements SortUtil.Sort {
 
    private static final int THRESHOLD = 10;
 
    /*
     * (non-Javadoc)
     * 
     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
     */
    public void sort(int[] data) {
        int[] temp=new int[data.length];
        mergeSort(data,temp,0,data.length-1);
    }
 
    private void mergeSort(int[] data, int[] temp, int l, int r) {
        int i, j, k;
        int mid = (l + r) / 2;
        if (l == r)
            return;
        if ((mid - l) >= THRESHOLD)
            mergeSort(data, temp, l, mid);
        else
            insertSort(data, l, mid - l + 1);
        if ((r - mid) > THRESHOLD)
            mergeSort(data, temp, mid + 1, r);
        else
            insertSort(data, mid + 1, r - mid);
 
        for (i = l; i <= mid; i++) {
            temp[i] = data[i];
        }
        for (j = 1; j <= r - mid; j++) {
            temp[r - j + 1] = data[j + mid];
        }
        int a = temp[l];
        int b = temp[r];
        for (i = l, j = r, k = l; k <= r; k++) {
            if (a < b) {
                data[k] = temp[i++];
                a = temp[i];
            } else {
                data[k] = temp[j--];
                b = temp[j];
            }
        }
    }
 
    /**
     * @param data
     * @param l
     * @param i
     */
    private void insertSort(int[] data, int start, int len) {
        for(int i=start+1;i<start+len;i++){
            for(int j=i;(j>start) && data[j]<data[j-1];j--){
                SortUtil.swap(data,j,j-1);
            }
        }
    }
 
}


堆排序:
 
package org.rut.util.algorithm.support;
 
import org.rut.util.algorithm.SortUtil;
 
/**
 * @author treeroot
 * @since 2010-11-22
 * @version 1.0
 */
public class HeapSort implements SortUtil.Sort{
 
    /* (non-Javadoc)
     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
     */
    public void sort(int[] data) {
        MaxHeap h=new MaxHeap();
        h.init(data);
        for(int i=0;i<data.length;i++)
            h.remove();
        System.arraycopy(h.queue,1,data,0,data.length);
    }
 
 
     private static class MaxHeap{
         
        
        void init(int[] data){
            this.queue=new int[data.length+1];
            for(int i=0;i<data.length;i++){
                queue[++size]=data[i];
                fixUp(size);
            }
        }
         
        private int size=0;
 
        private int[] queue;
                
        public int get() {
            return queue[1];
        }
 
        public void remove() {
            SortUtil.swap(queue,1,size--);
            fixDown(1);
        }
        //fixdown
        private void fixDown(int k) {
            int j;
            while ((j = k ><< 1) <= size) {
                if (j < size && queue[j]<queue[j+1])
                    j++; 
                if (queue[k]>queue[j]) //不用交换
                    break;
                SortUtil.swap(queue,j,k);
                k = j;
            }
        }
        private void fixUp(int k) {
            while (k > 1) {
                int j = k >> 1;
                if (queue[j]>queue[k])
                    break;
                SortUtil.swap(queue,j,k);
                k = j;
            }
        }
 
    }
 
}
 
 
SortUtil:
 
package org.rut.util.algorithm;
 
import org.rut.util.algorithm.support.BubbleSort;
import org.rut.util.algorithm.support.HeapSort;
import org.rut.util.algorithm.support.ImprovedMergeSort;
import org.rut.util.algorithm.support.ImprovedQuickSort;
import org.rut.util.algorithm.support.InsertSort;
import org.rut.util.algorithm.support.MergeSort;
import org.rut.util.algorithm.support.QuickSort;
import org.rut.util.algorithm.support.SelectionSort;
import org.rut.util.algorithm.support.ShellSort;
 
/**
 * @author treeroot
 * @since 2010-11-22
 * @version 1.0
 */
public class SortUtil {
    public final static int INSERT = 1;
 
    public final static int BUBBLE = 2;
 
    public final static int SELECTION = 3;
 
    public final static int SHELL = 4;
 
    public final static int QUICK = 5;
 
    public final static int IMPROVED_QUICK = 6;
 
    public final static int MERGE = 7;
 
    public final static int IMPROVED_MERGE = 8;
 
    public final static int HEAP = 9;
 
    public static void sort(int[] data) {
        sort(data, IMPROVED_QUICK);
    }
    private static String[] name={
            "insert","bubble","selection","shell","quick","improved_quick","merge","improved_merge","heap"
    };
    
    private static Sort[] impl=new Sort[]{
            new InsertSort(),
            new BubbleSort(),
            new SelectionSort(),
            new ShellSort(),
            new QuickSort(),
            new ImprovedQuickSort(),
            new MergeSort(),
            new ImprovedMergeSort(),
            new HeapSort()
    };
 
    public static String toString(int algorithm){
        return name[algorithm-1];
    }
    
    public static void sort(int[] data, int algorithm) {
        impl[algorithm-1].sort(data);
    }
 
    public static interface Sort {
        public void sort(int[] data);
    }
 
    public static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}
分享到:
评论
6 楼 sam_kee 2010-11-29  
算法,算法,最头疼算法,但是也很有用
5 楼 netbo 2010-11-26  
为什么我这么笨???
4 楼 zhaspe 2010-11-25  
今天我也在用java写排序算法。最想看quick sort的实现,发现没有。不过还是赞楼主
3 楼 davepkxxx 2010-11-25  
整理的不错,现在用的少了
2 楼 bitray 2010-11-25  
还是有些意义的
1 楼 killpoer3 2010-11-25  
好久没看算法了。。。

相关推荐

    数据库基础测验20241113.doc

    数据库基础测验20241113.doc

    微信小程序下拉选择组件

    微信小程序下拉选择组件

    DICOM文件+DX放射平片-数字X射线图像DICOM测试文件

    DICOM文件+DX放射平片—数字X射线图像DICOM测试文件,文件为.dcm类型DICOM图像文件文件,仅供需要了解DICOM或相关DICOM开发的技术人员当作测试数据或研究使用,请勿用于非法用途。

    Jupyter Notebook《基于双流 Faster R-CNN 网络的 图像篡改检测》+项目源码+文档说明+代码注释

    <项目介绍> - 基于双流 Faster R-CNN 网络的 图像篡改检测 - 不懂运行,下载完可以私聊问,可远程教学 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.md文件(如有),仅供学习参考, 切勿用于商业用途。 --------

    使用epf捕获没有CA证书的SSLTLS明文(LinuxAndroid内核支持amd64arm64).zip

    c语言

    (源码)基于Arduino的天文数据库管理系统.zip

    # 基于Arduino的天文数据库管理系统 ## 项目简介 本项目是一个基于Arduino的天文数据库管理系统,旨在为Arduino设备提供一个完整的天文数据库,包括星星、星系、星团等天体数据。项目支持多种语言的星座名称,并提供了详细的天体信息,如赤道坐标、视星等。 ## 项目的主要特性和功能 星座目录包含88个星座,提供拉丁语、英语和法语的缩写和全名。 恒星目录包含494颗亮度达到4等的恒星。 梅西耶目录包含110个梅西耶天体。 NGC目录包含3993个NGC天体,亮度达到14等。 IC目录包含401个IC天体,亮度达到14等。 天体信息每个天体(不包括星座)提供名称、命名、相关星座、赤道坐标(J2000)和视星等信息。 恒星额外信息对于恒星,还提供每年在赤经和赤纬上的漂移以及视差。 ## 安装使用步骤 1. 安装库使用Arduino IDE的库管理器安装本项目的库。 2. 解压数据库将db.zip解压到SD卡中。

    (源码)基于JSP和SQL Server的维修管理系统.zip

    # 基于JSP和SQL Server的维修管理系统 ## 项目简介 本项目是一个基于JSP和SQL Server的维修管理系统,旨在提供一个高效、便捷的维修管理解决方案。系统涵盖了从维修订单的创建、管理到配件的录入、更新等多个功能模块,适用于各类维修服务行业。 ## 项目的主要特性和功能 1. 用户管理 管理员和客户的注册与登录。 管理员信息的管理与更新。 客户信息的创建、查询与更新。 2. 维修订单管理 维修订单的创建、查询与更新。 维修回执单的创建与管理。 3. 配件管理 配件信息的录入与更新。 配件库存的管理与查询。 4. 评价与反馈 客户对维修服务的评价记录。 系统反馈信息的收集与管理。 5. 数据加密与安全 使用MD5加密算法对用户密码进行加密存储。 通过过滤器实现登录验证,确保系统安全。 ## 安装使用步骤

    devecostudio-windows-3.1.0.501.zip

    HUAWEI DevEco Studio,以下简称DevEco Studio)是基于IntelliJ IDEA Community开源版本打造,为运行在HarmonyOS和OpenHarmony系统上的应用和服务(以下简称应用/服务)提供一站式的开发平台。 作为一款开发工具,除了具有基本的代码开发、编译构建及调测等功能外,DevEco Studio还具有如下特点: - 高效智能代码编辑:支持ArkTS、JS、C/C++等语言的代码高亮、代码智能补齐、代码错误检查、代码自动跳转、代码格式化、代码查找等功能,提升代码编写效率。更多详细信息,请参考[编辑器使用技巧] - 低代码可视化开发:丰富的UI界面编辑能力,支持自由拖拽组件和可视化数据绑定,可快速预览效果

    《计算机视觉技术》实验报告-8.1提取车辆轮廓

    《计算机视觉技术》实验报告-8.1提取车辆轮廓

    springboot小徐影城管理系统(代码+数据库+LW)

    随着现在网络的快速发展,网上管理系统也逐渐快速发展起来,网上管理模式很快融入到了许多生活之中,随之就产生了“小徐影城管理系统”,这样就让小徐影城管理系统更加方便简单。 对于本小徐影城管理系统的设计来说,系统开发主要是采用java语言技术,在整个系统的设计中应用MySQL数据库来完成数据存储,具体根据小徐影城管理系统的现状来进行开发的,具体根据现实的需求来实现小徐影城管理系统网络化的管理,各类信息有序地进行存储,进入小徐影城管理系统页面之后,方可开始操作主控界面,主要功能包括管理员:首页、个人中心、用户管理、电影类型管理、放映厅管理、电影信息管理、购票统计管理、系统管理、订单管理,用户前台;首页、电影信息、电影资讯、个人中心、后台管理、在线客服等功能。 本论文主要讲述了小徐影城管理系统开发背景,该系统它主要是对需求分析和功能需求做了介绍,并且对系统做了详细的测试和总结。具体从业务流程、数据库设计和系统结构等多方面的问题。望能利用先进的计算机技术和网络技术来改变目前的小徐影城管理系统状况,提高管理效率。

    C++与Matlab实现SIFT特征提取算法+项目源码+文档说明+代码注释

    <项目介绍> - SIFT特征提取算法C++与Matlab实现 - 不懂运行,下载完可以私聊问,可远程教学 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.md文件(如有),仅供学习参考, 切勿用于商业用途。 --------

    (1991-2024年)国家自然、社科基金部分名单(含部分标书)(最新!!!)

    数据介绍 数据名称:国家自然、社科基金部分名单 数据年份:1991-2024年 样本数量:10万+ 数据格式:PDF、excel

    卓晴-信号与系统课件.pdf

    卓晴

    as-bundled-clients

    as-bundled-clients

    学习时最后的资料包括面试等信息

    学习时最后的资料包括面试等信息

    (源码)基于Spring Boot和Ant Design的雨选课系统.zip

    # 基于Spring Boot和Ant Design的雨选课系统 ## 项目简介 雨选课系统是一个基于Spring Boot和Ant Design框架构建的前后端分离的选课系统。该系统实现了学生选课、成绩查询、教师成绩修改、课程编辑、课程新增等功能。登录信息使用Redis存储,并支持课程图片的上传功能。 ## 项目的主要特性和功能 1. 用户登录与权限管理 学生、教师和管理员分别有不同的登录权限。 登录信息使用Redis进行存储。 2. 课程管理 学生可以查看可选课程列表,并进行选课和退选操作。 教师可以查看自己教授的课程,并修改学生成绩。 管理员可以编辑和新增课程。 3. 成绩管理 学生可以查询自己的成绩。 教师可以修改学生的成绩。 4. 图片上传 支持课程图片的上传和展示。 5. 日志记录 系统记录请求和响应的日志信息,便于问题追踪和性能分析。

    数据库期末作业基于Python+mysql的餐厅点餐系统源码+数据库+文档说明(高分项目)

    数据库期末作业基于Python+mysql的餐厅点餐系统源码+数据库+文档说明(高分项目),含有代码注释,满分大作业资源,新手也可看懂,期末大作业、课程设计、高分必看,下载下来,简单部署,就可以使用。该项目可以作为课程设计期末大作业使用,该系统功能完善、界面美观、操作简单、功能齐全、管理便捷,具有很高的实际应用价值。 数据库期末作业基于Python+mysql的餐厅点餐系统源码+数据库+文档说明(高分项目)数据库期末作业基于Python+mysql的餐厅点餐系统源码+数据库+文档说明(高分项目)数据库期末作业基于Python+mysql的餐厅点餐系统源码+数据库+文档说明(高分项目)数据库期末作业基于Python+mysql的餐厅点餐系统源码+数据库+文档说明(高分项目)数据库期末作业基于Python+mysql的餐厅点餐系统源码+数据库+文档说明(高分项目)数据库期末作业基于Python+mysql的餐厅点餐系统源码+数据库+文档说明(高分项目)数据库期末作业基于Python+mysql的餐厅点餐系统源码+数据库+文档说明(高分项目)数据库期末作业基于Python+mysql的餐厅

    江苏镇江两座小桥的技术状况评估与维修建议

    内容概要:本文针对镇江市丹徒区辛丰镇的两座小型桥梁(大叶二组滚水坝桥与东联组桥)进行了详细的技术状况评定和现状调查。主要内容包括:桥梁的基本参数描述、桥梁各部分的具体检查结果以及存在的具体病害及其原因分析,同时依据《公路桥梁技术状况评定标准》对每座桥梁分别给出了综合评分和技术状况等级,并提出了具体的维护与修复建议。大叶二组滚水坝桥技术状况良好(2类),但需要解决桥面铺装裂缝和桥墩的混凝土剥落问题;而东联组桥则需重点关注桥面施工不完整及护栏损坏等问题。 适用人群:桥梁管理人员、维护工作人员及城市基础设施规划相关人员。 使用场景及目标:适用于中小跨度桥梁的常规检查与维修决策制定过程中,旨在帮助专业人士快速掌握桥梁的实际状态,确保桥梁安全可靠运行。 其他说明:文中附有多张实拍图片用于直观展示桥梁现状及存在问题。

    基于套接字API开发的高性能高稳定性跨平台MQTT客户端,可以在嵌入式设备FreeRTOS LiteOS RTThre.zip

    c语言

Global site tag (gtag.js) - Google Analytics