java的幾種常用排序方法集合

JAVA實作部分排序方法


public class SortTest {
	public static void main(String[] args) {
		int[] a = { 3, 5, 2, 1, 9, 10, 8, 7, 6, 1, 2, 4 }; 	
		System.out.print("數組原序：           ");	
		for (int k = 0; k < a.length; k++) {
			System.out.print(a[k] + " ");
		}
		System.out.println();
		
		// swap(int[]a ,int i,int j);交換方法
		int p=0;//0代表數組索引的第一個數字
		int q=2;//位置的交換
		swap(a,p,q);
		System.out.print("交換方法：           ");
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+" ");
		}
		System.out.println();		
		
		// bubbleSort(a);冒泡排序
		bubbleSort(a);
		System.out.print("冒泡排序：           ");
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+" ");
		}
		System.out.println();
		
		//selectSort(a);直接選擇排序
		selectSort(a);
		System.out.print("直接選擇排序： ");
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+" ");
		}
		System.out.println();
		
		// insertSort(a);插入排序方法
		insertSort(a);
		System.out.print("插入排序方法： ");
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+" ");
		}
		System.out.println();
		
		// reverse(a);反轉數組方法
		reverse(a);
		System.out.print("反轉數組方法： ");
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+" ");
		}
		System.out.println();

		// quitSort(int[] a, int low, int hight)快速排序法
		int low = 0;
		int hight=11;
		quitSort(a,low,hight);
		System.out.print("快速排序方法： ");
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+" ");
		}
		System.out.println();
		
	}

	/** * 交換方法 * @param a * @param i * @param j */
	public static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	/** * 冒泡排序 * @param a */
	public static void bubbleSort(int[] a) {
		for (int i = 0; i < a.length; i++) {
			for (int j = i; j < a.length; j++) {
				if (a[i] > a[j]) {
					swap(a, i, j);
				}
			}
		}
	}

	/**
	 * * 直接選擇排序法----選擇排序的一種 方法：每一趟從待排序的資料元素中選出最小（或最大）的一個元素， *
	 * 順序放在已排好序的數列的最後，直到全部待排序的資料元素排完。 性能：比較次數O(n^2),n^2/2 交換次數O(n),n *
	 * 交換次數比冒泡排序少多了，由于交換所需CPU時間比比較所需的CUP時間多，是以選擇排序比冒泡排序快。 *
	 * 但是N比較大時，比較所需的CPU時間占主要地位，是以這時的性能和冒泡排序差不太多，但毫無疑問肯定要快些。 * 
	 * * @param data *
	 * 要排序的數組 * @param sortType * 排序類型 * @return
	 */
	public static void selectSort(int[] data) {
		int index;
		for (int i = 0; i < data.length; i++) {
			index = i;
			for (int j = i + 1; j < data.length; j++) {
				if (data[index] > data[j]) {
					index = j;
				}
			} // 交換在位置i和index(最大值)兩個數
			swap(data, i, index);
		}
	}

	/**
	 * 插入排序方法：将一個記錄插入到已排好序的有序表（有可能是空表）中,進而得到一個新的記錄數增1的有序表。
	 * 性能：比較次數O(n^2),n^2/4 * 複制次數O(n),n^2/4 比較次數是前兩者的一般，而複制所需的CPU時間較交換少，
	 * 是以性能上比冒泡排序提高一倍多，而比選擇排序也要快。 * 
	 *  @param data     要排序的數組
	 *  @param sortType 排序類型
	 */
	public static void insertSort(int[] data) { // 比較的輪數
		for (int i = 1; i < data.length; i++) {
			// 保證前i+1個數排好序
			for (int j = 0; j < i; j++) {
				if (data[j] > data[i]) {
					// 交換在位置j和i兩個數
					swap(data, i, j);
				}
			}
		}
	}

	/**
	 * * 反轉數組的方法 * *
	 *  @param data * 源數組
	 */
	public static void reverse(int[] data) {
		int length = data.length;
		int temp = 0;
		// 臨時變量
		for (int i = 0; i < length / 2; i++) {
			temp = data[i];
			data[i] = data[length - 1 - i];
			data[length - 1 - i] = temp;
		}
	}

	/**
	 * * 快速排序 快速排序使用分治法（Divide and conquer）政策來把一個序列（list）分為兩個子序列（sub-lists）。
	 * 步驟為： 
	 *  1. 從數列中挑出一個元素，稱為 "基準"（pivot）， 
	 *  2. 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面 （相同的數可以到任一邊）。
	 *  	在這個分割之後，該基準是它的最後位置。這個稱為分割（partition）操作。
	 *  3. 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
	 *  	遞回的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。
	 * 		雖然一直遞回下去，但是這個算法總會結束，因為在每次的疊代（iteration）中， 
	 * 		它至少會把一個元素擺到它最後的位置去。
	 */
	public static void quitSort(int[] a, int low, int hight)// 快速排序法
	{
		int i, j, k = 0;
		if (low < hight)// 先儲存
		{
			i = low;
			j = hight;
			k = a[i];
			while (i < j) {
				while (i < j && a[j] > k) {
					j--;
				}
				if (i < j) {// 從後往前排序
					a[i] = a[j];
					i++;
				}
				while (i < j && a[i] < k) {
					i++;
				}
				if (i < j) {// 從前往後排序
					a[j] = a[i];
					j--;
				}
			}
			a[i] = k;
			quitSort(a, low, i - 1);
			quitSort(a, i + 1, hight);
		}
	}

}