分治算法——快速排序、歸并排序算法(Java實作)

排序問題

對序列42，96，23，89，48，75，36，30，57，61用快速排序、歸并排序算法，從小到大排序。

算法實作：

import java.util.Arrays;
/**
 * 快速排序
 * @author 光
 *
 */
public class QuickSort {

	public static int getMiddle(int[] intArr, int low, int high) {
		int tmp = intArr[low];    //數組的第一個作為中軸數
		while (low < high) {
			while (low < high && intArr[high] > tmp) {
				high--;
			}
			intArr[low] = intArr[high];   //比中軸數小的記錄移到低端
			while (low < high && intArr[low] < tmp) {
				low++;
			}
			intArr[high] = intArr[low];   //比中軸大的記錄移到高端
		}
		intArr[low] = tmp;              //中軸記錄到尾
		return low;                   //傳回中軸的位置
	}
	
	public static void _quickSort(int[] intArr, int low, int high) {  
        if (low < high) {  
            int middle = getMiddle(intArr, low, high);  //将intArr數組進行一分為二  
            _quickSort(intArr, low, middle - 1);        //對低字表進行遞歸排序  
            _quickSort(intArr, middle + 1, high);       //對高字表進行遞歸排序  
        }  
    }
	public static void quick(int[] str) {  
        if (str.length > 0) {    //檢視數組是否為空  
            _quickSort(str, 0, str.length - 1);  
        }  
    } 
	
	public static void main(String[] args) {  
          
         int[] intArr={42,96,23,89,48,75,36,30,57,61}; 
         System.out.println("old: "+Arrays.toString(intArr));
         quick(intArr); 
         System.out.println("new: "+Arrays.toString(intArr));
    } 
}
           

import java.util.Arrays;
/**
 * 歸并排序
 * @author 光
 *
 */
public class Merge {
	 
    private static void sort(int[] array,int i,int j) {
        if(i<j){
            int middle=(i+j)/2;
            //遞歸處理相關的合并事項
            sort(array,i,middle);
            sort(array,middle+1,j);
            merge(array,i,middle,j);           
        }
    }
    /**
     * 合并相關的數組内容
     * 同時使合并後的數組仍然有序
     *
     */
    private static void merge(int[] array, int i, int middle, int j) {
        //建立一個臨時數組用來存儲合并後的資料
        int[] temp=new int[array.length];
        int m=i;
        int n=middle+1;
        int k=i;
        while(m<=middle&&n<=j){
            if(array[m]<array[n])
                temp[k++]=array[m++];
            else
                temp[k++]=array[n++];
        }
        //處理剩餘未合并的部分
        while(m<=middle){
            temp[k++]=array[m++];
        }
        while(n<=j){
            temp[k++]=array[n++];
        }
        //将臨時數組中的内容存儲到原數組中
        while(i<=j){
            array[i]=temp[i++];
        }
    }

    public static void main(String[] args) {
    	//需要進行排序的數組
    	int[] array={42,96,23,89,48,75,36,30,57,61};
    	//輸出原數組的内容
    	System.out.println("old: "+Arrays.toString(array));
    	//歸并排序操作
    	sort(array,0,array.length-1);
    	//輸出排序後的相關結果
    	System.out.println("new: "+Arrays.toString(array));
    }
}
           

輸出結果：

old: [42, 96, 23, 89, 48, 75, 36, 30, 57, 61]
new: [23, 30, 36, 42, 48, 57, 61, 75, 89, 96]