sort.java

算法中经典问题

package sort;
import java.util.*;

public class sort {
    int size;
    int []matrix;
    public sort(int size_) {
        size=size_;
        Random random=new Random();
        matrix=new int[size];
        for( int i=1;i<matrix.length;i++ )
            matrix[i]=random.nextInt(size);
    }

    void InsertSort()
    {
        for(int i=2;i<matrix.length;i++)
            if(matrix[i]<matrix[i-1])
            {
                matrix[0]=matrix[i];
                matrix[i]=matrix[i-1];
                int j=0;
                for( j=i-2; matrix[j]>matrix[0] && j>0;j-- )
                    matrix[j+1]=matrix[j];
                matrix[j+1]=matrix[0];
            }
    }

    void BubbleSort(int[] matrix1)
    {
        boolean swap=false;
        for( int i=1;i<matrix1.length;i++ )
        {
            int j;
            for(j=1;j<matrix1.length-i;j++){
                if (matrix1[j] > matrix1[j + 1]) {
                    int temp = matrix1[j];
                    matrix1[j] = matrix1[j + 1];
                    matrix1[j + 1] = temp;
                    swap = true;
                }
            }
            if( swap==false )
                break;
        }

    }

    int Partition(int []matrix_,int low,int high)
    {
        int mid=(low+high)/2;
        int temp=(matrix_[low]<matrix_[high]?matrix_[low]:matrix_[high]);
        matrix_[0]=(temp>matrix_[mid]?temp:matrix_[mid]);
        while(low<high)
        {
            while(low<high && matrix_[high]>=matrix_[0])
                high--;
            matrix_[low]=matrix_[high];

            while(low<high && matrix_[low]<=matrix_[0])
                low++;
            matrix_[high]=matrix_[low];
        }
        matrix_[low]=matrix_[0];
        return low;

    }

    void Qsort(int[] matrix_,int low,int high)
    {
        if(low<high)
        {
            int partition = Partition(matrix_, low, high);
            Qsort(matrix_, low, partition - 1);
            Qsort(matrix_, partition + 1, high);
        }
    }

    void QuickSort(int []matrix_)
    {
        Qsort(matrix_,1,matrix_.length-1);
    }

    void HeapAdjust(int[] matrix_,int s,int m)
    {
        int rc=matrix_[s];
        for( int j=s*2;j<m;j*=2)
        {
            if(matrix_[j]<matrix_[j+1])
                j++;
            if( matrix_[j]<rc) break;
            matrix_[s]=matrix_[j];
            s=j;
        }
        matrix_[s]=rc;
    }

    void HeapSort(int[] matrix)
    {
        for(int i=(matrix.length-1)/2;i>0;i--)
            HeapAdjust(matrix,i,matrix.length-1);

        for(int i=matrix.length-1;i>0;i--)
        {
            int temp=matrix[1];
            matrix[1]=matrix[i];
            matrix[i]=temp;
            HeapAdjust(matrix,1,i-1);
        }
    }
}