算法-排序算法

Love The Way You Lie 2022-02-26 11:12 313阅读 0赞

**插入排序**

/**
    	 * 插入排序
    	 * @param arr
    	 */
    	public static <T extends Comparable<? super T>> void insertSort(T [] arr) {
    		
    		int j;
    		for(int i=1 ; i<arr.length; i++) {
    			T tmp = arr[i];
    			for(j=i; j>0 && tmp.compareTo(arr[j-1])<0; j--)
    				arr[j] = arr[j-1];
    			arr[j] = tmp;
    		}
    		
    	}

**并归排序**

/**
    	 * 并归排序
    	 * @param arr
    	 */
    	public static <T extends Comparable<? super T>> void sort(T [] arr) {
    		T[] tmp = (T[])new Comparable[arr.length];
    		mergeSort(arr, tmp, 0, arr.length-1);
    	}
    	
    	public static <T extends Comparable<? super T>> void mergeSort(T [] arr, T [] tmp, int left, int right) {
    		
    		if(left < right) {
    			int center = (left+right)/2;
    			mergeSort(arr, tmp, left, center);
    			mergeSort(arr, tmp, center+1, right);
    			merge(arr, tmp, left, center+1, right);
    		}
    		
    	}
    	
    	public static <T extends Comparable<? super T>> void merge(T [] arr, T [] tmp, int leftpos, int rightpos, int rightend) {
    		
    		int tmppos = leftpos;
    		int leftend = rightpos-1;
    		int eleNums = rightend-leftpos+1;
    		
    		while(leftpos <= leftend && rightpos <= rightend) {
    			if(arr[leftpos].compareTo(arr[rightpos]) <=0)
    				tmp[tmppos++] = arr[leftpos++];
    			else
    				tmp[tmppos++] = arr[rightpos++];
    		}
    		while(leftpos <= leftend)
    			tmp[tmppos++] = arr[leftpos++];
    		
    		while(rightpos<=rightend)
    			tmp[tmppos++] = arr[rightpos++];
    		
    		for(int i=0;i<eleNums; i++,rightend--) {
    			arr[rightend] = tmp[rightend];
    		}
    	}

**快速排序**

/**
    	 * 快速排序
    	 * @param arr
    	 */
    	public static <T extends Comparable<? super T>> void quicksort(T [] arr) {
    
    		sort(arr, 0, arr.length-1);
    	}
    	
    	public static <T extends Comparable<?super T>> int quickSort(T [] arr, int start, int end) {
    		
    		int mid = (start+end)/2;
    		T pivot = arr[mid];
    		
    		while(start <= end) {
    			while(arr[start].compareTo(pivot)<0)
    				start++;
    			while(arr[end].compareTo(pivot)>0)
    				end--;
    			if(start<=end) {
    				T tmp = arr[start];
    				arr[start] = arr[end];
    				arr[end] = tmp;
    				start++;
    				end--;
    			}
    		}
    		
    		return start;
    		
    	}
    	
    	public static <T extends Comparable<? super T>> void sort(T [] arr, int start, int end) {
    
    		int mid = quickSort(arr, start, end);
    		if(start<mid-1)
    			sort(arr, start, mid-1);
    		if(mid<end)
    			sort(arr, mid, end);
    	}