738      阿裏雲  技術社區[雲棲]

操作數組的常用方式二-----排序、查找

/**
 * 操作數組的常用方式
 */
public class ArrayDemo {

	public static void main(String[] args) {

		int[] arr = new int[] { 1, 3, 10, 2, 5, 7, 8 };

		// 排序前
		System.out.println("--------------------排序前--------------------");
		printArray(arr);
		// 選擇排序
		// selectSort(arr);
		// 冒泡排序
		bubbleSort(arr);
		System.out.println("--------------------排序後--------------------");
		printArray(arr);
		
		// 普通查找法
		System.out.println(arrayIndexOf(arr, 10));
		//二分法查找方式1
		System.out.println(searchElIndex(arr, 5));
		//二分法查找方式2
		System.out.println(searchElIndex2(arr, 5));

	}

	/**
	 * 選擇排序（每一輪將第一個元素和數組中的每個元素進行比較）
	 * @param arr 待排序的數組
	 */
	public static void selectSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[i] > arr[j]) {
					/*
					 * 調換元素的位置 方式1：使用臨時變量
					 */
					/*int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;*/

					/*
					 * 方式2，將相比的兩數做加減運算。
					 * 如：int[] arr = {2,1}; 
					 * arr[0] = arr[0] + arr[1]; ==》3=2+1; 
					 * arr[1] = arr[0] - arr[1]; ==》2=3-1;
					 * arr[0] = arr[0] - arr[j]; ==》1=3-2;
					 */
					/*arr[i] = arr[i] + arr[j];
					arr[j] = arr[i] - arr[j];
					arr[i] = arr[i] - arr[j];*/

					swap(arr, i, j);
				}
			}
		}
	}

	/**
	 * 冒泡排序（兩個相鄰的數進行比較）
	 * @param arr 待排序的數組
	 */
	public static void bubbleSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) { // 控製比較的次數
			for (int j = 0; j < arr.length - i - 1; j++) { // -i:比較的元素減少  -1:為了避免拋ArrayIndexOutOfBoundsException
				if (arr[j] > arr[j + 1]) {
					/*int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;*/
					
					swap(arr, j, j+1);
					
				}
			}
		}
	}
	
	/**
	 * 將數組中的兩個元素交換位置
	 * @param arr 待交換元素位置的數組
	 * @param index1 元素下標1
	 * @param index2 元素下標2
	 */
	public static void swap(int[] arr, int index1, int index2) {
		int temp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = temp;
	}
	
	/**
	 * 二分法查找一個元素在數組中的下標
	 * @param arr 數組
	 * @param key 要查找的元素
	 * @return 找到返回元素在數組中的下標，沒找到則返回-1
	 */
	public static int searchElIndex(int[] arr, int key) {
		int min,max,mid;
		min = 0;
		max = arr.length - 1;
		mid = (min + max) / 2;
		
		while (arr[mid] != key) {
			if (key > arr[mid]) {
				min = mid + 1;
			} else if (key < arr[mid]) {
				max = mid - 1;
			} 
			
			if (min > max) 
				return -1; 
			
			mid = (min + max) / 2;
		}
		
		return mid;
	}
	
	/**
	 * 二分法查找一個元素在數組中的下標
	 * @param arr 數組
	 * @param key 要查找的元素
	 * @return 找到返回元素在數組中的下標，沒找到則返回-1
	 */
	public static int searchElIndex2(int[] arr, int key) {
		int min,max,mid;
		min = 0;
		max = arr.length - 1;
		
		while (min <= max) {
			
			mid = (min + max) >> 1;
			
			if (key > arr[mid]) {
				min = mid + 1;
			} else if (key < arr[mid]) {
				max = mid - 1;
			} else {
				return mid;
			}
		}
		
		return -1;
	}
	
	/**
	 * 查找一個元素在數組中的位置，該函數可以查找未經排序數組的第一個元素所在數組中的下標
	 * @param arr 查找的數組
	 * @param key 查找的元素
	 * @return 如果找到則返回該元素在數組中的下標，沒找到則返回-1
	 */
	public static int arrayIndexOf(int[] arr, int key) {
		for(int i = 0; i < arr.length; i++) {
			if (arr[i] == key) 
				return i;
		}
		return -1;
	}

	/**
	 * 打印數組
	 * @param arr 待打印的數組
	 */
	public static void printArray(int[] arr) {
		System.out.print("[");
		for (int i = 0; i < arr.length; i++) {
			if (i < arr.length - 1) {
				System.out.print(arr[i] + ",");
			} else {
				System.out.print(arr[i]);
			}
		}
		System.out.println("]");
	}

}

最後更新：2017-04-02 06:52:18

  上一篇： JAVA猜數遊戲程序小研究

  下一篇： 十進製轉換成二進製、八進製、十六進製的通用方法