- package code;
- 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;i++){
- a[i]=a[i++];
- }
- 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-1;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,long pivot){
- int leftPtr = left-1; // right of first elem
- int rightPtr = right+1; //left of pivot
- while(true){
- while(leftPtr < rightPtr && a[++leftPtr] < pivot); //nop
- while(rightPtr > leftPtr && a[--rightPtr] > pivot);//nop
- if(leftPtr >= rightPtr) break; // if pointers cross, partition done
- else{ // swap
- swap(leftPtr,rightPtr);
- }
- swap(leftPtr,right);
- }//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 <= 0){ // if size is 1,it's already sorted
- return;
- }else{ //size is 2 or larger
- long pivot = a[right];
- int partition = this.partitionIt(left, right, pivot);
- recQuickSort(left,partition-1); //sort left
- recQuickSort(partition+1,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使用快速排序
- long median = medianOf3(left,right);
- int partition = partitionIt(left, right, median);
- recQuickSort2(left,partition-1); //sort left
- recQuickSort2(partition+1,right);//sort right
- }
- }//end recQuickSort2
- private long 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 a[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
- }
- //该片段来自于http://www.codesnippet.cn/detail/3010201410861.html
来源: http://www.codesnippet.cn/detail/3010201410861.html