首页 > 代码库 > 数据结构——八大排序算法

数据结构——八大排序算法

驱动程序:

public class Main {

    public static void main(String[] args) {
        int[] array={2,0,3,4,1,9,6,8,7,5};
        print(Sort.bubbleSort(array, true));//冒泡
        print(Sort.InsertionSort(array, true));//插入
        print(Sort.mergeSort(array,true, "recursion"/*circulate*/));//归并
        print(Sort.quickSort(array, true));//快速
        print(Sort.radixSort(array, true));//基数
        print(Sort.selectionSort(array, true));//选择
        print(Sort.shellSort(array, true, "Hibbard"/*Sedgewick*/));//希尔
        print(Sort.heapSort(array, true));//堆排序
    }
    
    private static void print(int[] array) {
        for(int i:array){
            System.out.print(i+" ");
        }
        System.out.println();
    }
}

实现算法:

import java.util.ArrayList;

public class Sort {
    
    private static void swap(int[] array,int i1,int i2){//交换
        int tmp=array[i1];
        array[i1]=array[i2];
        array[i2]=tmp;
    }
//-----------------------冒泡排序---------------------------------------------------------------------    
    public static int[] bubbleSort(int[] array,boolean sequence){
        int[] newArray=array.clone();
        for(int i=newArray.length-1;i>=0;i--){
            boolean flag = false;
            for(int j=0;j<i;j++){
                if(sequence^newArray[j]<newArray[j+1]){
                    swap(newArray,j,j+1);
                    flag=true;
                }
            }
            if(!flag){
                break;
            }
        }
        return newArray;
    }
    
//-----------------------快速排序---------------------------------------------------------------------
    public static int[] quickSort(int[] array,boolean sequence){
        int[] newArray=array.clone();
        quick(newArray,0,newArray.length-1,sequence);
        return newArray;
    }
    
    private static void quick(int[] array,int left,int right,boolean sequence) {
        if(3<=right-left){
            int pivot=pivot(array, left, right, sequence);
            int i=left;
            int j=right-1;
            while(i<=j){
                for(;sequence^array[i]>pivot;++i){}
                for(;sequence^array[j]<pivot;--j){}
                if(i<j){
                    swap(array,i,j);
                }
            }
            int end=sequence^array[i]>pivot?i:j;
            swap(array, end, right-1);
            quick(array, left, end-1, sequence);
            quick(array, end+1, right, sequence);
        }else{
            InsertionSort(array,left,right,sequence);
        }
    }
    
    private static int pivot(int[] array,int left,
                             int right,boolean sequence) {//得到主元
        int center=(left+right)/2;
        if(sequence^array[right]>array[left]){
            swap(array, right, left);
        }
        if(sequence^array[center]>array[left]){
            swap(array, center, left);
        }else if(sequence^array[right]>array[center]){
            swap(array, right, center);
        }
        swap(array,center,right-1);
        return array[right-1];
    }
//-----------------------插入排序---------------------------------------------------------------------    
    public static int[] InsertionSort(int[] array,boolean sequence){
        int[] newArray=array.clone();
        InsertionSort(newArray,sequence,1);
        return newArray;
    }
    private static void InsertionSort(int[] array,boolean sequence,
                                      int interval){//interval=间隔
        //用在希尔排序的插入排序算法
        for(int i=interval;i<array.length;i+=interval){
            int tmp=array[i];
            for(int j=i;;j-=interval){
                if(j==0||sequence^tmp<array[j-interval]){
                    array[j]=tmp;
                    break;
                }else{
                    array[j]=array[j-interval];
                }
            }
        }
    }
    private static void InsertionSort(int[] array,int left,int right,
                                        boolean sequence){
        //用在快速排序的插入排序算法
        for(int i=left;i<right+1;i++){
            int tmp=array[i];
            for(int j=i;;j--){
                if(j==0||sequence^tmp<array[j-1]){
                    array[j]=tmp;
                    break;
                }else{
                    array[j]=array[j-1];
                }
            }
        }
    }

//-----------------------选择排序----------------------------------------------------------------------    
    public static int[] selectionSort(int[] array,boolean sequence){
        int[] newArray=array.clone();
        for(int i=0;i<newArray.length-1;i++){
            int position=i;
            for (int j = i+1; j < newArray.length; j++) {
                if(sequence^newArray[position]<newArray[j]){
                    position=j;
                }
            }
            swap(newArray, i, position);
        }
        return newArray;
    }
    

//-----------------------堆排序----------------------------------------------------------------------    
    public static int[] heapSort(int[] array,boolean sequence){
        int[] heap=array.clone();
        biuldHeap(heap,sequence);
        int[] newArray=new int[array.length];
        for(int i=0;i<heap.length;i++){
            newArray[i]=popHeapTop(heap,sequence,heap.length-1-i);
        }
        return newArray;
    }
    
    private static void biuldHeap(int[] array,boolean sequence) {
        for(int i=(array.length-1)/2;i>=0;i--){
            int j=i;
            int tmp;
            while(j*2+1<=array.length-1){
                tmp=j*2+2>array.length-1||sequence^array[j*2+1]>array[j*2+2]
                   ?j*2+1:j*2+2;
                if(sequence^array[j]<array[tmp]){
                    swap(array, j, tmp);
                }
                j=tmp;
            }
        }
    }
    private static int popHeapTop(int[] array,boolean sequence,int size) {
        int top=array[0];
        array[0]=array[size];
        for(int i=0,tmp;i*2+1<=size-1;i=tmp){
            tmp=i*2+2>size-1||sequence^array[i*2+1]>array[i*2+2]
                 ?i*2+1:i*2+2;
            if(sequence^array[i]<array[tmp]){
                swap(array, i, tmp);
            }else{
                break;
            }
            i=tmp;
        }
        return top;
    }
    
//-----------------------希尔排序----------------------------------------------------------------------    
    public static int[] shellSort(int[] array,boolean sequence,
                                    String sequenceName){
        int[] newArray=array.clone();
        ArrayList<Integer> list=new ArrayList<>();//第一种方法
        if(sequenceName.equals("Hibbard")){
            list=hibbard(newArray);
        }else if(sequenceName.equals("Sedgewick")){//第二种方法
            list=sedgewick(newArray);
        }
        for(int i=list.size()-1;i>=0;i--){
            InsertionSort(newArray,sequence,list.get(i));
        }
        return newArray;
    }

    private static ArrayList<Integer> hibbard(int[] array){//第一种增量算法
        int value=http://www.mamicode.com/1;
        ArrayList<Integer> hibbard=new ArrayList<>();
        for(int i=1;;i++){
            value=http://www.mamicode.com/(int)(Math.pow(2, i)-1);
            if(value<array.length){
                hibbard.add(value);
            }else{
                break;
            }
        }
        return hibbard;
    }
    
    private static ArrayList<Integer> sedgewick(int[] array){//第二种增量算法
        int value=http://www.mamicode.com/1;
        ArrayList<Integer> sedgewick=new ArrayList<>();
        sedgewick.add(value);//公式第一项是-1,我也很无奈啊
        for(int i=2;;i++){
            value=http://www.mamicode.com/(int) (Math.pow(4,i)-3*Math.pow(2,i)+1);
            if(value<array.length){
                sedgewick.add(value);
            }else {
                break;
            }
        }
        return sedgewick;
    }

//-----------------------归并排序----------------------------------------------------------------------    
    public static int[] mergeSort(int[] array,boolean sequence,String way){
        int[] newArray=array.clone();
        int[] tmpArray=new int[newArray.length];
        if(way.equals("recursion")){
        merageRecursion(newArray,tmpArray,0,newArray.length-1,sequence);
        }else if(way.equals("circulate")){
            int cnt=1;
            while(cnt<newArray.length){
                merageCirulate(newArray, tmpArray, cnt, sequence);
                cnt*=2;
                merageCirulate(tmpArray, newArray, cnt, sequence);
                cnt*=2;
            }
        }
        return tmpArray;
    }
    
    private static void merageCirulate(int[] array,int[] tmpArray,
                                    int cnt,boolean sequence) {//循环
        int i;
        String way="circulate";
        for(i=0;i<=array.length-2*cnt;i+=2*cnt){
            merage(array, tmpArray, i,i+cnt, i+2*cnt-1, sequence,way);
        }
        if(i+cnt<array.length){
            merage(array, tmpArray, i,i+cnt, array.length-1, sequence,way);
        }else{
            for(int j=i;j<array.length;j++){
                tmpArray[j]=array[j];
            }
        }
        
    }
    
    private static void merageRecursion(int[] array,int[] tmpArray,int left,
                                        int rightEnd,boolean sequence) {//递归
        int center;
        String way="recursion";
        if(left<rightEnd){
            center=(rightEnd+left)/2;
            merageRecursion(array, tmpArray, left, center, sequence);
            merageRecursion(array, tmpArray, center+1, rightEnd, sequence);
            merage(array,tmpArray,left,center+1,rightEnd,sequence,way);
        }
    }
    
    private static void merage(int[] array,int[] tmpArray,int left,int right,int rightEnd,
                                boolean sequence,String way) {
        int leftEnd=right-1;
        int tmp=left;
        int start=left;
        while(left<=leftEnd&&right<=rightEnd) {
            if(sequence^array[left]<array[right]){
                tmpArray[tmp++]=array[right++];
            }else{
                tmpArray[tmp++]=array[left++];
            }
        }
        while (right<=rightEnd) {
            tmpArray[tmp++]=array[right++];
        }
        while (left<=leftEnd) {
            tmpArray[tmp++]=array[left++];
        }
        if(way.equals("recursion")){
            for(int i=rightEnd;i>=start;i--){
                array[i]=tmpArray[i];
            }
        }    
    }
//-----------------------基数排序----------------------------------------------------------------------
    public static int[] radixSort(int[] array,boolean sequence){
        int ten=10;//十进制
        int max=MaxFigure(array);
        int[][] buckets=new int[ten][array.length];
        int[] cnts =new int[ten];
        for(int i=0;i<array.length;i++){
            int value=http://www.mamicode.com/array[i];
            int row=value%10;
            buckets[row][cnts[row]]=value;
            cnts[row]++;
        }
        for(int i=0;i<max+1;i++){
            int[][] buffer=new int[ten][array.length];
            int[] cntsBuffer=new int[ten];
            for(int j=0;j<ten;j++){
                for(int k=0;k<cnts[j];k++){
                    int value=http://www.mamicode.com/buckets[j][k];
                    int row=value/(int) Math.pow(10,i)%10;
                    buffer[row][cntsBuffer[row]]=value;//几位上的数字
                    cntsBuffer[row]++;
                }
            }
            buckets=buffer.clone();
            cnts=cntsBuffer.clone();
        }
        int[] newArray=new int[array.length];
        if(sequence){
            newArray=buckets[0];
        }else {
            for(int i=0,j=array.length-1;j>=0;j--,i++){
                newArray[i]=buckets[0][j];
            }
        }
        return newArray;
    }
    

    private static int MaxFigure(int[] array) {//求数组中最大数的最大位数       个位=1
        int maxValue=http://www.mamicode.com/array[0];//最大数
        int figure;
        for(int i=1;i<array.length;i++){
            if(array[i]>maxValue){
                maxValue=http://www.mamicode.com/array[i];
            }
        }
        for(figure=1;maxValue>=10;figure++){
            maxValue/=10;
        }
        return figure;
    }
}

 

数据结构——八大排序算法