java实现快速排序算法

比眉伴天荒 2023-05-29 13:19 3阅读 0赞

**快排基本思想：首先选定一个轴值（就是比较的基准）将待排序的记录划分为两个独立的部分，左侧记录的关键码都是小于基准或等于轴值得，右侧记录的关键码都是大于或等于轴值，然后再针对这两部分分别重复上述过程**

**首先实现快排一次划分的关键代码：**

public class Parti {
    	public int partition(int[] r,int first,int end){
    		int i,j;
    		i=first;j=end;                        //初始化
    		while(i<j){
    			while(i<j&&r[i]<=r[j])  j--;      //右侧扫描
    			if(i<j){                          //将较小的记录交换到前面
    				int temp;
    				temp=r[i];
    				r[i]=r[j];
    				r[j]=temp;
    			}
    			while(i<j&&r[i]<r[j]){
    				i++;                           //左侧扫描
    			}
    			if(i<j){                           //将较大的记录换到后面
    				int temp;
    				temp=r[i];
    				r[i]=r[j];
    				r[j]=temp;
    			}
    		}
    		return i;//
    	}
    }

**接下来实现调用**

public class Tp {
    	static Parti p=new Parti();
    
    	public static void quick(int[] r,int first,int end){    //利用递归反复划分
    		if(first<end){
    			int pivot=p.partition(r, first, end);           //调用划分函数
    			quick(r,first,pivot-1);
    			quick(r,pivot+1,end);
    		}
    	}
    	public static void main(String[] args) {
    		int r[]={12,25,36,63,21,32,56,11};
    		System.out.println("待排序的记录序列是：");
    		for(int i=0;i<8;i++){
    			System.out.print(r[i]+"  ");
    		}
    		quick(r,0,7);
    		System.out.println("\n"+"排序好的记录是：");
    		for(int i=0;i<8;i++){
    			System.out.print(r[i]+"  ");
    		}
    
    	}
    
    }

**运行TP.java实现效果如下：**

![20191106154228386.png][]

[20191106154228386.png]: https://img-blog.csdnimg.cn/20191106154228386.png