操作数组的常用方式二-----排序、查找

/**
 * 操作数组的常用方式
 */
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("]");
	}

}