欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

java的快速排序

程序员文章站 2024-01-20 19:49:34
...

写了2个形式的,原理差不多,都是找基数,递归到一个结束。但是细节和交换上有所不同。

相关code

package day20180728;

public class QuickSort{
    
    public static void quickSort(int[] arr,int lt,int rt)
    {
    //只有一个元素的时候,递归出口
        if(lt>=rt)
            return;
        
       int temp=arr[lt];
       int st=lt,end=rt;
       
       while(st<end)
       {
           while(st<end&&temp<=arr[end])
           {
               end--;
           }
           
           while(st<end&&temp>=arr[st])
           {
               st++;
           }
           
           if(st<end)
           {
           int tag=0;
           tag=arr[end];
           arr[end]=arr[st];
           arr[st]=tag;
           }
           
        System.out.println("每一次左右轮换的结果为");
           display(arr);
           System.out.println();
           System.out.println("#########");
       }
        arr[lt]=arr[st];
        arr[st]=temp;
        
        System.out.println("基数为:"+st);
        
        System.out.println("基数定位的结果为:");
        System.out.println("------****-------");
        display(arr);
        System.out.println("++++++++++");
        
       //递归基数的左边部分。
        quickSort(arr,lt,st-1);    
        quickSort(arr,st+1,rt);

    }
    
    
    public static void display(int[] arr)
    {
        
        
        for(int elem:arr)
            System.out.print(elem+" ");
    }
    
    
    
    public static void main(String[] args)
    {
        
        int[] arr= {11,6,8,22,33,78,65,0};
        
        quickSort(arr,0,arr.length-1);
        
    
        
        display(arr);
        

            
    

        
    }
}

结果

每一次左右轮换的结果为
11 6 8 0 33 78 65 22 
#########
每一次左右轮换的结果为
11 6 8 0 33 78 65 22 
#########
基数为:3
基数定位的结果为:
------****-------
0 6 8 11 33 78 65 22 ++++++++++
每一次左右轮换的结果为
0 6 8 11 33 78 65 22 
#########
基数为:0
基数定位的结果为:
------****-------
0 6 8 11 33 78 65 22 ++++++++++
每一次左右轮换的结果为
0 6 8 11 33 78 65 22 
#########
基数为:1
基数定位的结果为:
------****-------
0 6 8 11 33 78 65 22 ++++++++++
每一次左右轮换的结果为
0 6 8 11 33 22 65 78 
#########
每一次左右轮换的结果为
0 6 8 11 33 22 65 78 
#########
基数为:5
基数定位的结果为:
------****-------
0 6 8 11 22 33 65 78 ++++++++++
每一次左右轮换的结果为
0 6 8 11 22 33 65 78 
#########
基数为:6
基数定位的结果为:
------****-------
0 6 8 11 22 33 65 78 ++++++++++
0 6 8 11 22 33 65 78 

另外一个版本
code如下

package day20180728;

public class qSort {
    
    
    public static void ksort(int[] arr,int left,int right)
    {
        if(left>=right)
            return ;
        int tag=arr[left];
        int i=left,j=right;
        
        while(i<j)
        {
            
            while(i<j&&arr[i]<=arr[j])
            {
                j--;
            }
            
            if(i<j)
            {
                int temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
                i++;
            }
            
            while(i<j&&arr[j]>=arr[i])
            {
                i++;
            }
            
            if(i<j)
            {
                int temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
                j--;
            }
                    
        }
        
        System.out.println("基数i为:"+i);
        
        System.out.println("基数定位的结果为:");
        System.out.println("------////-------");
        display(arr);
       
         System.out.println("/////////////");
           //递归基数的左边部分。
         ksort(arr,left,i-1);    
            ksort(arr,i+1,right);
    }
    
    
    public static void display(int[] arr)
    {
        
        
        for(int elem:arr)
            System.out.print(elem+" ");
    }
    

    public static void main(String[] args) {
    
        int[] arr= {11,66,8,22,33,78,65,0};
        ksort(arr,0,arr.length-1);
        
        display(arr);
        
        
    }

}

结果

基数i为:2
基数定位的结果为:
------////-------
0 8 11 22 33 78 65 66 /////////////
基数i为:0
基数定位的结果为:
------////-------
0 8 11 22 33 78 65 66 /////////////
基数i为:3
基数定位的结果为:
------////-------
0 8 11 22 33 78 65 66 /////////////
基数i为:4
基数定位的结果为:
------////-------
0 8 11 22 33 78 65 66 /////////////
基数i为:7
基数定位的结果为:
------////-------
0 8 11 22 33 66 65 78 /////////////
基数i为:6
基数定位的结果为:
------////-------
0 8 11 22 33 65 66 78 /////////////
0 8 11 22 33 65 66 78 

快速排序设计到了递归,有点不好理解,相关东西可以网上多查看一下