黑马程序员技术交流社区

标题: 几种简单排序算法 [打印本页]

---

作者: 无云    时间: 2015-8-30 01:11
标题: 几种简单排序算法
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;
    }
}

---

作者: cat73    时间: 2015-8-30 06:26
楼主可以去看看Array.sort的算法，那货才叫恐怖。。。

---

作者: zzq18217362451    时间: 2015-8-30 07:06
初级菜鸟，表示看不懂

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2