public void swap(int[] arr, int a, int b) {
		if (a == b || arr == null || arr.length == 0) {
			return;
		}
		// 10^8=2;10^8(也就是2)^8=10;10^8^10=8; 连个相同的数异或为0,任何数异或0都为自身
		arr[a] = arr[a] ^ arr[b];
		arr[b] = arr[a] ^ arr[b];
		arr[a] = arr[a] ^ arr[b];
	}

	private static int[] arr = {3, 1, 39, 20, 12, 4, 99, 35, 48, 101, 100};
//	private static final int[] arr = {3, 1, 2};


	/**
	 * 冒泡
	 * 自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。
	 * 即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
	 * 优化: 如果没有改变,即排序完成
	 */
	public void bubbleSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			boolean exchanged = false;
			for (int j = 0; j < arr.length - 1 - i; j++) {
				if (arr[j] > arr[j + 1]) {
					exchanged = true;
					swap(arr, j, j + 1);
				}
			}
			if (!exchanged) {
				break;
			}
		}
	}

	/**
	 * 正向反向一起冒泡
	 */
	public void bubbleSort2(int[] arr) {

		for (int start = 0, end = arr.length - 1; start < end; start++, end--) {
			for (int i = start; i < end; i++) {
				if (arr[i] > arr[i + 1]) {
					swap(arr, i, i + 1);
				}
			}
			for (int i = end - 1; i > start; i--) {
				if (arr[i] < arr[i - 1]) {
					swap(arr, i, i - 1);
				}
			}
			System.out.println(Arrays.toString(arr));

		}
	}

	/**
	 * 选择排序
	 * 选出最小的一个数与第一个位置的数交换；
	 * 然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止
	 */
	public void selectSort(int[] arr) {
		int min;
		for (int i = 0; i < arr.length - 1; i++) {
			min = i;
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < arr[min]) {
					min = j;
				}
			}
			if (min != i) {
				swap(arr, i, min);
			}
			System.out.println(Arrays.toString(arr));
		}
	}


	public void quickSort(int[] arr, int start, int end) {
		if (start >= end) {
			return;
		}
		int partition = partition(arr, start, end);
		quickSort(arr, start, partition - 1);
		quickSort(arr, partition + 1, end);
	}


	public int partition(int[] arr, int start, int end) {
		if (start > end) {
			return 0;
		}
		int key = arr[start];
		while (start < end) {
			while (start < end && key <= arr[end]) {
				end--;
			}
			arr[start] = arr[end];
			while (start < end && key >= arr[start]) {
				start++;
			}
			arr[end] = arr[start];
		}
		arr[start] = key;
		System.out.println(Arrays.toString(arr));
		return end;
	}


	public void insertSort(int[] arr) {
		for (int right = 1; right < arr.length; right++) {
			int value = arr[right], left = right - 1;
			while (left >= 0 && arr[left] > value) {
				arr[left + 1] = arr[left];
				left--;
			}
			arr[left + 1] = value;
			System.out.println(Arrays.toString(arr));
		}
	}