快速排序算法(java实现)

Bertha 。 2022-03-01 16:20 194阅读 0赞

### 一.思想: ###

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另一部分的所有数据都要小,然后再用递归方法对着两部分分别进行快速排序,当每一部分不能再细分时完成排序.

### 二,解释 ###

1.  初始数组

l = 0, h = 7, k = 6

2.一趟排序(对于每一趟排序都分为两部分,先是从右边找比自己小的,后是从左边找比自己大的)

I = 0, h = 6, k = 6

I = 2, h = 6, k = 6

注意:只要l < h,排序还要进行下去,直到不满足循环条件为止,此时一趟排序完成,然后对左右两部分递归上述操作即可

### 三.代码 ###

package 快速排序;
    
    public class FastSort {
    
    	public static void main(String[] args) {
    		// TODO 自动生成的方法存根
    		
    		int []a = {6, 4, 7, 9, 2, 8, 1, 10};
    		
    		for(int i = 0; i < a.length; i++){
    			System.out.print(a[i] + " ");
    		}
    		
    		System.out.println();
    		
    		sort(a, 0, a.length-1);
    		
    		for(int i = 0; i < a.length; i++){
    			System.out.print(a[i] + " ");
    		}
    
    	}
    	
    	
    	public static void sort(int []a, int low, int high){
    		
    		int l = low;
    		
    		int h = high;
    		
    		int k = a[low];
    		
    		
    		while(l < h){
    			
    			while(l < h && a[h] >= k){
    				h--;
    			}
    			
    			if(l < h){
    				
    				int temp = a[h];
    				
    				a[h] = a[l];
    				
    				a[l] = temp;
    				
    				l++;
    				
    			}
    			
    			while(l < h && a[l] <= k){
    				l++;
    				
    			}
    			
    			if(l < h){
    				
    				int temp = a[l];
    				
    				a[l] = a[h];
    				
    				a[h] = temp;
    			
    				h--;
    			}
    			
    		}
    		
    		if(l-1 > low)
    			sort(a, low, l-1);
    		
    		if(h+1 < high)
    			sort(a, h+1, high);
    		
    	}
    
    }

输出:

![2019032312173058.png][]

[2019032312173058.png]: /images/20220301/1c778dd369bf44a4bf36129d15f06803.png