Skip to content

Latest commit

 

History

History
192 lines (144 loc) · 4.97 KB

排序.md

File metadata and controls

192 lines (144 loc) · 4.97 KB

排序

方法中的參數設置

  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);
			}
		}
	}