lintcode 整数排序 1和2

Love The Way You Lie 2022-07-16 11:07 108阅读 0赞

package cn.edu.tju.cs.bigdata.chc;
    
    
    
    public class 整数排序1 {
    	/**
    	 * @author 小锦囊
    	 * 冒泡排序
    	 */
    	public void sortIntegersMaoPao(int[] A){
    		for(int i = 0; i < A.length; i++){
    			for(int j = i + 1; j< A.length; j++){
    				if(A[i] > A[j]){
    					int tmp = A[i];
    					A[i] = A[j];
    					A[j] = tmp;
    				}
    			}
    		}
    	}
    	
    	/**
    	 * @author 小锦囊
    	 * </br> 插入排序， 从前向后遍历  i， 
    	 * </br> i向前面排好序的进行插入 
    	 * @return void 空
    	 * @param A
    	 */
    	public void sortIntegersChaRu(int[] A){
    		for(int i = 0; i < A.length; i++){
    			while(i > 0 && A[i-1] > A[i]){
    				int tmp = A[i-1];
    				A[i-1] = A[i];
    				A[i]= tmp;
    				i--;
    			}
    		}
    	}
    	/**
    	 * @author 小锦囊
    	 * @return void 空
    	 * 选择排序 从前向后遍历i
    	 * </br>从i+1到尾选择最小的，与i交换
    	 * @param A
    	 */
    	public void sortIntegerSelect(int[] A){
    		for(int i = 0 ; i < A.length; i++){
    			int cur = i;
    			for(int j = cur; j < A.length; j++){
    				if(A[cur] > A[j]){
    					cur = j;
    				}
    			}
    			if(cur != i){
    				int tmp = A[cur];
    				A[cur] = A[i];
    				A[i] = tmp;
    			}
    		}
    	}
    	
    	
    	public void sortIntegers2Merge(int[] A){
    	       if(A==null || A.length <=1)
    	            return;
    	        int low = 0;
    	        int high = A.length - 1;
    	        mergeSort(A,low,high);
    	 	
    	}
        public void mergeSort(int[] A,int low ,int high){
            if(low>=high)
                return;
            int mid = low + (high - low)/2;
            mergeSort(A,low,mid);
            mergeSort(A,mid+1,high);
            merge(A,low,mid,high);
        }
        public void merge(int[] A,int low,int mid,int high){
            int len = high - low + 1;
            int[] C = new int[len];
            int i = low;
            int j = mid + 1;
            int k = 0;
            while(i<=mid && j<= high){
                if(A[i]>A[j]){
                    C[k++] = A[j];
                    j++;
                }else{
                    C[k++] = A[i];
                    i++;
                }
            }
            while(i<=mid){
                C[k++] = A[i];
                i++;
            }
            while(j<=high){
                C[k++] = A[j];
                j++;
            }
            for(k=0;k<len;k++){
                A[low+k] = C[k];
            }
        }
    	
    	/**
    	 * @author 小锦囊
    	 * return void 空
    	 * 
    	 * @param A
    	 */
    	public void sortIntegers2QuickSort(int[] A){
    		quickSort(A, 0, A.length - 1);
    	}
    	public void quickSort(int[] A ,int start , int end){
    		if(start >= end)return;
    		int pivot = partition(A, start, end);
    		quickSort(A, start, pivot - 1); //注意
    		quickSort(A, pivot + 1, end);//注意
    	}
    	public int partition(int[] A , int start, int end){
    		int pivot = A[start];
    		int i = start , j = end;
            while(i < j) {
                while(i<j && A[j] >= pivot) {
                    j--;
                }
                if(i<j) {
                    A[i] = A[j];
                }
                while(i<j  && A[i] <= pivot) {
                    i++;
                } 
                if(i<j) {
                    A[j] = A[i];
                }
            }
            A[i] = pivot;
            return i;
    	} 
    	
    	/**
    	 * @author 小锦囊
    	 * @return void
    	 * @param A 一个整数数组
    	 * </br>输出整数数组
    	 */	
    	public void printArray(int[] A){
    	
    		for(int i : A){
    			System.out.print(i + " ");
    		}
    	}
    	public static void main(String[] args){
    		整数排序1 sort = new 整数排序1();
    		int[] A = {3, 2, 1, 4, 5};
    		System.out.println("冒泡排序：");
    		sort.sortIntegersMaoPao(A);
    		sort.printArray(A);
    		System.out.println("\n插入排序：");
    		int[] B = {3, 2, 1, 4, 5};
    		sort.sortIntegersChaRu(B);
    		sort.printArray(B);
    		System.out.println("\n选择排序：");
    		B = new int[]{3, 2, 1, 4, 5};
    		sort.sortIntegerSelect(B);
    		sort.printArray(B);
    		System.out.println("\n快速排序：");
    		B = new int[]{5,3,4,2};
    		sort.sortIntegers2QuickSort(B);
    		sort.printArray(B);
    		System.out.println("\n归并排序：");
    		B = new int[]{5,3,4,2};
    		sort.sortIntegers2Merge(B);
    		sort.printArray(B);
    		
    		
    	}
    }