返回 登录
0

快速排序算法与其它排序算法的笔记(Java)

快速排序排序相对于普通排序算法效率很高,特别是对于大数据优势体现的相当明显下面是java程序主程序:

public class Sort {
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int size=10000000;//千万数据
        long[] SJ=new long[size];
        Random random1 = new Random();//获得随机数
        JC jc=new JC();
        for(int i=0;i<size;i++)
        {
            SJ[i]=random1.nextInt();
           //System.out.println(random1.nextInt());
        }
        System.out.print("请输入选择:");
        int c;
        Scanner input =new Scanner(System.in);
        c=input.nextInt();
        switch(c)
        {
            case 1:   //普通排序算法     
                long startTime=System.currentTimeMillis();   //获取开始时间
                SelectSort s1=new SelectSort();
                s1.Select(SJ, size);
                long endTime=System.currentTimeMillis(); //获取结束时间
                System.out.println("普通排序运行时间: "+(endTime-startTime)+"ms");
                break;
            case 2: //快速排序算法
                startTime=System.currentTimeMillis();   //获取开始时间
                QuickSort s2=new QuickSort();
                s2.Qsort(0,size-1,SJ);
                endTime=System.currentTimeMillis(); //获取结束时间
                if(jc.PD(SJ,size))//判断是否有序
                        System.out.println("快速排序运行时间: "+(endTime-startTime)+"ms");
                break;
        }
        // TODO code application logic here

QuickSort//快速排序

public class QuickSort {
    public int  Fdsort(int low,int high,long SJ[])
    {
       long s=SJ[low];
        long flag=SJ[low];
        while(low<high)
        {
            while(low<high && SJ[high]>=flag) --high;
            SJ[low]=SJ[high];
            while(low<high && SJ[low]<=flag) ++low;
            SJ[high]=SJ[low];
        }
        SJ[low]=flag;
        return low;

    }
    public void Qsort(int low,int high,long SJ[])
    {
        if(low<high)
        {
            int flag=Fdsort(low,high,SJ);
            Qsort(low,flag-1,SJ);
            Qsort(flag+1,high,SJ);
        }
    }

}

计算结果:(tool:notebeans)
请输入选择:2
快速排序运行时间: 1469ms
普通选择排序基本上运算不出来

评论