(快排实例)查询一个数组中第n大的元素

短命女 2022-06-08 08:42 116阅读 0赞

package cyd;
    /**
     * 查询一个数组中第n大的元素 
     * 借用了快速排序的思想，
     * 我先选定一个标定值 然后将数组等分小于这个数的放在左边 大于的放在右边  这时标定值的位置是正确的 我们将它返回去 跟我们的n比较
     * 如果返回值大于n我们 就只需要查左边的数据  如果小于n 就只需要查右边的数据   然后递归求解 即可
     * 
     * 只需要O(2n) 的时间复杂度 就能查到想要的结果
     *  复杂度 = n + n/2 + n/4 +n/8 ...   = O(2n)
     * @author 1
     *
     */
    public class SelectNum {
    	public static void main(String[] args) {
    		int[] arr = randomArr(1000, 0, 1000);
    		int quickSortgetNum = quickSortgetNum(arr,20);
    		System.out.println(quickSortgetNum);
    	}
    
    
    	
    	//快速排序
    		public static int quickSortgetNum(int[] arr,int n){
    			
    			return __quickSort(arr , 0, arr.length - 1,n -1 );
    		}
    		
    		
    		//递归实现快速排序  
    		//每次找到当前的中间值，然后等分左右，再继续从左右依次这样做 就实现了快速排序
    		private static int __quickSort(int[] arr, int l, int r, int n) {
    			
    			
    			int p = __partition(arr, l, r);
    			
    			System.out.println(p+"-----"+arr[p]);
    			//递归求解
    			if(p > n){
    				return __quickSort(arr, l, p - 1, n);
    			}else if(p < n){
    				return __quickSort(arr, p + 1, r, n);
    			}else{
    				return arr[p];
    			}
    			
    			
    		}
    		
    		//快速排序核心
    		private static int __partition(int[] arr, int l, int r) {
    			
    			//这是标准位置的值,最后排序完成左边的比这小右边的比这大
    			//初始版本  取第一个元素 ，但是有一个弊端 如果 数组本身近乎有序，那么大于当前值的就会非常多，导致右侧元素多，就会导致快速排序退化成O(n^2)级别的排序
    //			int p = arr[l];
    			
    			//改进  从 l 到   r 中随机取 一个数  与 起始位置交换作为起始位置，这时 就不会出现这种情况了
    			swap(arr, l , (int) (Math.round((Math.random()*(r - l) + l))));
    			int p = arr[l];
    			int j = l;
    			for(int i = l + 1; i <= r; i++){
    				if(arr[i] < p){
    					swap(arr, i , j + 1);
    					j++;
    				}
    			}
    			swap(arr, j , l);
    			
    			return j;
    		}
    		
    		//输出
    	    public static void printArr(int[] arr){
    	        for(int i = 0; i < arr.length; i++){
    	            if(i != arr.length - 1){
    	                System.err.print(arr[i]+",");
    	            }else{
    	                System.err.println(arr[i]);
    	            }
    
    
    	        }
    	    }
    
    
    	    /**
    	     * 生成随机数
    	     * @param size
    	     * @param rangeL
    	     * @param rangeR
    	     * @return
    	     */
    	    public static int[] randomArr(int size, int rangeL, int rangeR){
    
    
    	        if(rangeL >= rangeR){
    	            return null;
    	        }
    	        int arr[] = new int[size];
    
    
    	        for(int i = 0; i < size; i++){
    	            arr[i] = (int) (Math.round((Math.random()*(rangeR - rangeL ) + rangeL)));
    	            for(int j = 0; j <=i; j++ ){
    	                if(i != j){
    	                    if(arr[i] == arr[j] ){
    	                        i--;
    	                        break;
    	                    }
    	                }
    	            }
    	        }
    
    
    	        return arr;
    	    }
    
    
    	    public static boolean isSortArr(int[] arr){
    	        for(int i =0 ; i < arr.length - 1; i++){
    	            if(arr[i] > arr[i + 1]){
    	                return false;
    	            }
    	        }
    	        return true;
    	    }
    
    
    	    //交换
    	    public static void swap(int arr[], int leftNum, int rightNum){
    	        int temp = arr[leftNum];
    	        arr[leftNum] = arr[rightNum];
    	        arr[rightNum] = temp;
    	    }
    }