`

JAVA各种排序方法及改良

JavaJ#Go 
阅读更多

插入排序：

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;
/**
 * @author treeroot
 * @since 2006-2-2
 * @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 2006-2-2
 * @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 2006-2-2
 * @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 2006-2-2
 * @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 2006-2-2
 * @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 2006-2-2
 * @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 2006-2-2
 * @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;
            }
        }

    }

 

 

  • algorithm.rar (13.6 KB)
  • 描述: 附件为以上方法必须用到的包，有朋友问到，现提供下载。
  • 下载次数: 58
分享到：
评论
4 楼 xyheqhd888 2009-03-27  
/*
* Created on 2006-2-2
*
* TODO To change the template for this generated file go to
* Window - Preferences - Java - Code Style - Code Templates
*/
package org.treeroot.util.algorithm;

import org.treeroot.util.algorithm.support.BubbleSort;
import org.treeroot.util.algorithm.support.HeapSort;
import org.treeroot.util.algorithm.support.ImprovedMergeSort;
import org.treeroot.util.algorithm.support.ImprovedQuickSort;
import org.treeroot.util.algorithm.support.InsertSort;
import org.treeroot.util.algorithm.support.MergeSort;
import org.treeroot.util.algorithm.support.QuickSort;
import org.treeroot.util.algorithm.support.SelectionSort;
import org.treeroot.util.algorithm.support.ShellSort;

/**
* @author treeroot
* @since 2006-2-2
* @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;
    }
}
及InsertSort类：
/*
* Created on 2006-2-2
*
* TODO To change the template for this generated file go to
* Window - Preferences - Java - Code Style - Code Templates
*/
package org.treeroot.util.algorithm.support;

import org.treeroot.util.algorithm.SortUtil;
/**
* @author treeroot
* @since 2006-2-2
* @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);
            }
        }       
    }
}

编译不能通过啊！晕ing!
3 楼 xyheqhd888 2009-03-27  
附件里的包对吗？怎么SortUtil包里引入InsertSort，BubbleSort等类包，而在InsertSort和BubbleSort里又要引入SortUtil包？这样互相引用结果是谁都不能编译通知啊！
2 楼 returnofking 2008-10-07  
－－－－－－－－－－－
wwglfy 2008-10-02
大哥，请教一个弱智的问题，org.rut.util.algorithm.SortUtil是从哪儿搞来的，我怎么找不到这个类，看到了给我回一个，谢谢！

－－－－－－－－－－－

兄弟，这不是一个弱智的问题，而是因我疏忽了没有提供这个包，不好意思！现在可以在附件处下载了，有兴趣可以看看..
1 楼 wwglfy 2008-10-02  
大哥，请教一个弱智的问题，org.rut.util.algorithm.SortUtil是从哪儿搞来的，我怎么找不到这个类，看到了给我回一个，谢谢！
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    JAVA经典算法各种排序算法

    Java经典算法 ，各种排序算法 老掉牙 河內塔 費式數列 巴斯卡三角形 三色棋 老鼠走迷官（一） 老鼠走迷官（二） 騎士走棋盤 八個皇后 八枚銀幣 生命遊戲 字串核對 雙色、三色河內塔 背包問題（Knapsack...

    Java-各种排序算法

    Java排序算法是编程领域中的重要知识点，特别是在处理数据集合时，高效的排序算法能显著提升程序的性能。这里我们将深入探讨几种常见的Java排序算法，包括冒泡排序、堆排序、插入排序、合并排序、快速排序以及选择...

    java开发经典算法

    排序方法Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - 改良的选择排序 快速排序法（一） 快速排序法（二） 快速排序法（三） 合并排序法 基数排序法 循序搜寻法（使用卫兵...

    java代码-java 归并排序（改良）未完成

    `main.java`文件很可能是实现归并排序算法的Java源代码，其中可能包含了类定义、方法实现以及测试用例。`README.txt`文件通常用于存放项目的说明、使用指南、作者信息或版本历史等。 要完全理解这个项目，你需要...

    java各种经典算法

    Shaker 排序法 - 改良的气泡排序 Heap 排序法 - 改良的选择排序 快速排序法（一） 快速排序法（二） 快速排序法（三） 合并排序法 基数排序法 搜寻 循序搜寻法（使用卫兵） 二分搜寻法（搜寻原则的代表）...

    改良的java排序法,不是一什么人都有会的。

    大家都来看看,要想学好java排序的话，希望您最好来看看。

    Java和C语言实现各种经典算法(含代码图例)

    Java和C语言实现各种经典算法(含代码图例) 老掉牙 河内塔 费式数列 巴斯卡三角形 三色棋 老鼠走迷官（一） 老鼠走迷官（二） 骑士走棋盘 八个皇后 八枚银币 生命游戏 字串核对 双色、三色河内塔 背包...

    十大经典排序——java实现（csdn）————程序.pdf

    4. 改良冒泡排序算法 在我们遍历的过程中，会发现从开始第一队到最后一对都没有发生交换，此时意味着，剩下这些待排序的元素已经是有序的数据，无需再次排序，所以我们可以引入一个标志，当遇到此情况的时候，直接...

    经典算法（C&JAVA实现）

    Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的氣泡排序 Heap 排序法 - 改良的選擇排序 快速排序法（一） 快速排序法（二） 快速排序法（三） 合併排序法 基數排序法 循序搜尋法（使用衛兵） 二分...

    经典算法（c&java版）

    • Shaker 排序法 - 改良的气泡排序 • Heap 排序法 - 改良的选择排序 • 快速排序法（一） • 快速排序法（二） • 快速排序法（三） • 合并排序法 • 基数排序法 搜寻 • 顺序搜索法（使用卫兵） • 二...

    经典常用算法(含代码)

    经典常用算法解析与实现，通过Java C语言分别实现各种算法，图文并茂，描述很详细！ 主要包括如下算法，很全面！ 河内塔 费式数列 巴斯卡三角形 三色棋 老鼠走迷官（一） 老鼠走迷官（二） 骑士走棋盘 八个...

    各种经典算法

    各种经典算法（总有一款你喜欢），河內塔 費式數列 巴斯卡三角形 三色棋 老鼠走迷官（一） 老鼠走迷官（二） 騎士走棋盤 八個皇后 八枚銀幣 生命遊戲 字串核對 雙色、三色河內塔 背包問題（Knapsack ...

    C和JAVA经典算法.rar

    「常見程式演算」主要收集一些常見的程式練習題目，您可以藉這些題目培養一些程式設計邏輯的感覺，對題目的分類只是個大概，方便索引而已，實作的部份是使用 C 及 Java。 老掉牙 河內塔 費式數列 巴斯卡...

    java 常见算法大全

    Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的氣泡排序 Heap 排序法 - 改良的選擇排序 快速排序法（一） 快速排序法（二） 快速排序法（三） 合併排序法 基數排序法 搜尋 循序搜尋法（使用衛兵）...

    3个著名语言运行速度测试（改良版）.zip

    这个改良版的测试可能包含了多个测试用例，如矩阵乘法、排序算法、字符串操作等，这些用例覆盖了各种常见的计算场景。通过对每个语言执行相同任务的时间记录，我们可以得出一个相对的运行速度比较。需要注意的是，...

    经典常用算法 河内塔

    Shaker 排序法 - 改良的气泡排序 Heap 排序法 - 改良的选择排序 快速排序法（一） 快速排序法（二） 快速排序法（三） 合并排序法 基数排序法 搜寻 循序搜寻法（使用卫兵） 二分搜寻法（搜寻原则的代表）...

    ACM经典算法 代码+详解

    Shaker 排序法 - 改良的氣泡排序 Heap 排序法 - 改良的選擇排序 快速排序法（一） 快速排序法（二） 快速排序法（三） 合併排序法 基數排序法 搜尋 循序搜尋法（使用衛兵） 二分搜尋法（搜尋原則的代表）...

Magicbox
Global site tag (gtag.js) - Google Analytics