Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2554082
  • 博文数量: 709
  • 博客积分: 12251
  • 博客等级: 上将
  • 技术积分: 7905
  • 用 户 组: 普通用户
  • 注册时间: 2005-07-17 00:00
个人简介

实现有价值的IT服务

文章存档

2012年(7)

2011年(147)

2009年(3)

2008年(5)

2007年(74)

2006年(431)

2005年(42)

分类: Java

2006-08-28 11:07:33

用Java实现几种常见的排序算法
作者:treeroot

用Java语言实现的各种排序,包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。

插入排序:

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            for(int j=i;(j>0)&&(data[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            for(int j=data.length-1;j>i;j--){
                if(data[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 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 2006-2-2
 * @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                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            for(int j=i;(j>=inc)&&(data[j]                SortUtil.swap(data,j,j-inc);
            }
        }
    }

}

快速排序:

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]           while((r!=0)&&data[--r]>pivot);
           SortUtil.swap(data,l,r);
        }
        while(l        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;
       
%2

阅读(789) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~