用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<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;
}
}
}
分享到:
相关推荐
java 实现归并排序,有代码实现,复杂度分析,基本步骤,适合初学者吧,
java 中文姓氏 排序
java实现中文排序,按数字字母汉字的顺序进行排序
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
主要介绍了Java实现拖拽列表项的排序功能,非常不错,具有参考借鉴价值,需要的朋友可以参考下
源码经过测试,绝对可以执行!主要包括插入排序、选择排序、希尔排序、冒泡排序和最佳排序等。
Java ip 地址排序Java ip 地址排序Java ip 地址排序Java ip 地址排序
各种排序算法java实现各种排序算法java实现各种排序算法java实现各种排序算法java实现各种排序算法java实现
各种排序算法 JAVA代码实现 所有排序算法 JAVA代码实现
堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用...
Java排序算法实现 Java排序算法实现 Java排序算法实现
堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆...
堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆...
用Java语言实现的各种排序 用Java语言实现的各种排序
java实现的各种排序法,冒泡排序法,插入排序法,选择排序法和快速排序法,代码中还包括各种排序法效率的检验,既可以用来学习,又可以做项目是用来参考。
Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C
java实现的插入排序 都是静态的例子 很简单
Java实现计数排序不是C,Java实现计数排序不是C,Java实现计数排序不是C
java实现的冒泡排序 很简单一看就懂