排序.md

排序

方法中的參數設置

1. 這個方法的功能是什麼?
2. 這個方法實現過程是否有未知內容參與運算?

交換元素順序

1. 定義兩個元素a、b。
2. 聲明一個變量x將a取出且暫時存放a元素。
3. 將b元素放入a元素原始位置(賦值)。
4. 將存放a元素的變量x放入b元素原始位置。

遍歷數組

• 要對數組中的元素進行打印或操作，可利用遍歷數組獲取元素。
• 利用循環，由角標為0的元素循環到最後一個元素。

反轉數組

• 把數組先分一半，把遍歷到的元素先取出，與對應的元素交換位置。
• 減1 的目的是為了對應要交換的角標數 減x 的目的是為了減掉已經被交換過的角標

常見排序

選擇排序

• 外循環: 由角標為0的元素開始循環到最後一個元素。
• 內循環: 由起始循環元素後一個元素開始，每一個元素都與第一個進行比較。

效能較高的選擇排序

• 外循環: 由角標為0的元素開始循環到最後一個元素。
• 內循環:

1. 初始化兩變量分別存放外循環循環到的元素與其角標值。
2. 將循環到的元素與其後面一個元素做比較。
3. 如果循環到的元素較後面一個元素大，則將兩變量分別重新賦值為後面的元素與其角標值。
4. 接下去比較，如果角標x不等於存放角標值的變量，則將角標為x的元素與變量中的元素交換位置。

冒泡排序

• 外循環: 由角標為0的元素開始循環到最後一個元素。
• 內循環: 由第0個元素開始，每一個元素都與後面一個元素進行比較。

• 減1原因為避免最後一個元素與後面的空元素比較，造成越界。 減x原因為每比較完一次則將完成比較的元素消掉，不重覆比較。

Java API自帶排序功能

• 直接Import java.util* 並調用其Arrays.sort()方法 。

Example:

import java.util.Arrays;

public class ArraySort {

	public static void main(String[] args) {
		
		int[] arr = {3, 30, 53, 67, 89, 23, 51, 17, 88};
		
		printArr(arr);

		selectSort(arr);//選擇排序
		
		printArr(arr);
		
		bubbleSort(arr);//冒泡排序
		
		printArr(arr);
		
		bestSort(arr);//排序效能最好的方法
		
		printArr(arr);
		
		Arrays.sort(arr);//Java API自帶由小到大排序方法
		
		printArr(arr);
		
		reverseArr(arr);//反轉數組
		
		printArr(arr);
		
	}

交換元素順序

	
	public static void changePos(int arr[], int a, int b) {
		
		if(arr[a] > arr[b]) {
			int temp = arr[a];
			arr[a] = arr[b];
			arr[b] = temp;
		}
	}
}

遍歷數組

	public static void printArr(int[] arr) {
		
		for(int i = 0; i < arr.length; i++) {
			
			System.out.print(arr[i] + "\t");

		}

		System.out.println();
	}

反轉數組

	public static void reverseArr(int[] arr) {
		//把數組先分一半，把遍歷到的元素先取出，與對應的元素交換位置
		for(int x = 0; x < arr.length/2; z++) {
			
			int temp = arr[x];
			arr[x] = arr[arr.length - 1 - x];
			arr[arr.length - 1 - x] = temp;
			//減 1 的目的是為了對應要交換的角標數
			//減 x 的目的是為了減掉已經被交換過的角標
		}
	}
	

選擇排序

	public static void selectSort(int[] arr) {
		//外循環: 由角標為0的元素開始循環到最後一個元素。
		//內循環: 由起始循環數後一個元素開始，每一個數都與第一個元素進行比較。
		for(int x = 0; x < arr.length - 1; x++) {
			
			for(int y = x + 1; y < arr.length; y++) {
				
				changePos(arr, x, y);
			}
		}
	}

效能較好的選擇排序

	public static void bestSort(int[] arr) {
		
		for(int x = 0; x < arr.length - 1; x++) {
            //定義一變量，賦值角標為x的元素
            //定義一變量，賦值x角標數
			int num = arr[x];
			int index = x;
			
			//與角標為x的後面一個元素做比較
			for(int y = x + 1; y < arr.length; y++) {
				/*
				如果角標為x的元素大於後面一個元素，
				則變量num重新賦值為角標為y的元素，
				並且將變量index重新賦值為角標數y
				*/
				if(num > arr[y]) {
					num = arr[y];
					index = y;
				}
				
				/*
				如果變量index不等於原來定義的角標數x，
				則將角標為x的元素與角標數為變量index的元素交換位置
				*/
				if(index != x) {
					changePos(arr, x, index);
				}
			}
		}
	}

---

冒泡排序

	public static void bubbleSort(int[] arr) {
		//外循環: 由角標為0的元素開始循環到最後一個元素。
		/*內循環: 由第0個元素開始，每一個數都與後面一個元素進行比較。
		         減1原因為避免最後一個元素與後面的空元素比較，造成越界。
		 		 減x原因為每比較完一次則將完成比較的元素消掉，不重覆比較。
		 */
		for(int x = 0; x < arr.length - 1; x++) {
			
			for(int y = 0; y < arr.length - 1 - x; y++) {
				
				changePos(arr, y, y + 1);
			}
		}
	}