各种排序算法java实现(2)

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;

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有