public class LongArray {
private long[] a;
private int nElems;
public LongArray(int max){
a = new long[max];
nElems=0;
}
//线性查找
public int find(long searchKey){
for(int j=0;j<nElems;j++){
if(a[j] == searchKey)
return j;
}
return -1;
}
//二分查找
public int find(long searchKey,long key){
int lowerBound = 0;
int upperBound = nElems-1;
int curIn;
while(true){
curIn = (lowerBound+upperBound)/2;
if(searchKey==a[curIn]){
return curIn; //find it
}else if(upperBound<lowerBound){
return -1; //can't find it
}else{
if(searchKey<a[curIn]){
upperBound = curIn-1;
}else{
lowerBound = curIn+1;
}
}
}
}
//递归二分查找
public int recFind(long searchKey ,int lowerBound,int upperBound){
int curIn;
curIn = (lowerBound + upperBound)/2;
if(a[curIn] == searchKey){
return curIn;
}
else if(lowerBound > upperBound){
return -1; //can'nt find it
}
else{
if(a[curIn] < searchKey){
return recFind(searchKey,curIn+1,upperBound);
}else{
return recFind(searchKey,lowerBound,curIn-1);
}
}
}
//size
public int size(){
return nElems;
}
//insert
public void insert(long value){
a[nElems] = value;
nElems++;
}
//delete
public boolean delete(long value){
int j;
for(j=0;j<nElems;j++){
if(value==a[j])break;
}
if(j==nElems){
return false;
}else{
for(int i = j;i<nElems-1;i++){
a[i]=a[i+1];
}
nElems--;
return true;
}
}
//display
public void display(){
System.out.println("array is :");
for(int j=0;j<nElems;j++){
System.out.println(a[j]);
}
}
//冒泡排序
public void bubbleSort(){
int out ,in;
for(out=nElems-1;out>1;out--){
for(in=0;in<out;in++){
if(a[in]>a[in+1]){
long temp;
temp = a[in];
a[in] = a[in+1];
a[in+1] = temp;
}
}
}
}
//选择排序
public void selectionSort(){
int out,in,min;
for(out=0;out<nElems;out++){
min = out;
for(in=out+1;in<nElems;in++){
if(a[in]<a[min]){
min = in;
}
}
long temp = a[out];
a[out] = a[min];
a[min] = temp;
}
}
//插入排序
public void insertionSort(){
int in,out;
for(out=1;out<nElems;out++){
long temp = a[out];
in = out;
while(in>0&&a[in-1]>=temp){
a[in]=a[in-1];
--in;
}
a[in]= temp;
}
}
//+++++++++++++++++++有问题++++++++++
//归并排序
/*归并两个有序数组*/
public static long[] mergerApp(long[] arrayA,long[] arrayB){
long[] arrayC = new long[arrayA.length+arrayB.length];
int aDex = 0,bDex = 0,cDex = 0;
while(aDex<arrayA.length && bDex <arrayB.length){ //neither array empty
if(arrayA[aDex] < arrayB[bDex])
arrayC[cDex++] = arrayA[aDex++];
else
arrayC[cDex++] = arrayB[bDex++];
}
while(aDex < arrayA.length){
arrayC[cDex++] = arrayA[aDex++];
}
while(bDex < arrayB.length){
arrayC[cDex++] = arrayB[bDex++];
}
return arrayC;
}//end mergerApp
//希尔排序
public void shellSort(int increment){
int inner,outer;
long temp;
int h = 1; // find initial value of h
while(h <= nElems/increment) h = h*increment+1;
while(h>0){ //decreasing h ,until h = 1
for(outer = h;outer < nElems;outer++){
temp = a[outer];
inner = outer; // one subpass(eg 0,4,8)
while(inner > h-1&&a[inner-h] >= temp){
a[inner] = a[inner-h];
inner -= h;
}//end for
a[inner] = temp;
}//end while(h>0)
h = (h-1)/increment; //decrease
}//end shellSort()
}
//划分
public int partitionIt(int left,int right,int pivot){
int leftPtr = left-1; // right of first elem
int rightPtr = right+1; //left of pivot
while(true){
while(leftPtr < rightPtr && a[++leftPtr] < a[pivot]); //nop
while(leftPtr < rightPtr && a[--rightPtr] > a[pivot]);//nop
// if pointers cross, partition done
if(leftPtr >= rightPtr)
{ break;}
else{
//使用++param的原因
swap(leftPtr,rightPtr);
}
}//end while
return leftPtr;
}//end partitionIn
public void swap(int dex1, int dex2) // swap two elements
{
long temp = a[dex1]; // A into temp
a[dex1] = a[dex2]; // B into A
a[dex2] = temp; // temp into B
} // end swap
//快速排序1(递归实现)
public void recQuickSort(int left,int right){
if(right<=left){ // if size is 1,it's already sorted
return;
}else{ //size is 2 or larger
int pivot = right;
int partition = this.partitionIt(left, right, pivot);
recQuickSort(left,partition-1); //sort left
recQuickSort(partition,right);//sort right
}
}
//快速排序2(对于中枢pivot的选取采用三数据取中值的方法)
public void recQuickSort2(int left,int right){
int size = right-left+1;
if(size<=3){
manualSort(left,right);
}else{ //数组长度大于3使用快速排序
int median = medianOf3(left,right);
int partition = partitionIt(left, right, median);
recQuickSort2(left,partition-1); //sort left
recQuickSort2(partition,right);//sort right
}
}//end recQuickSort2
private int medianOf3(int left, int right) {// return pivot
int center = (left+right)/2;
if(a[left] > a[center]){
swap(left,center);
}
if(a[left]> a[right]){
swap(left,right);
}
if(a[center] > a[right]){
swap(center,right);
}
swap(center,right-1);
return right-1;
}
private void manualSort(int left,int right){
int size = right-left+1;
if(size==1)return; //no sort necessary
if(size==2){
if(a[left]>a[right]){
swap(left,right);
}
return;
}
if(a[left]>a[left+1]){
swap(left,left+1);
}
if(a[left]>a[right]){
swap(left,right);
}
if(a[left+1]>a[right]){
swap(left+1,right);
}
}//end manualSort
public long[] getLongArray(){
return this.a;
}
} |
|
收藏
淘帖
踩
