java 排序

package com.xiawenquan.test.comllections;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 各种排序算法： 冒择路(入)兮(稀)快归堆，桶式排序，基数排序 冒泡排序，选择排序，插入排序，稀尔排序，快速排序，归并排序，堆排序，桶式排序，基数排序
 */
@SuppressWarnings("unused")
public class TestComllections {

	public static void main(String[] args) {
		int[] list = new int[] { 1, 4, 6, 7, 9, 3, 2, 8 };
		// bubbleSort(list);
		// selectSort(list);
		// insertionSort(list);
//		insertionSort(list);
		
		
		int i = binarySearch(list, 9);
		System.out.println("i === " + i);
	}

	// 集合的自带的排序
	public static void run() {
		int[] intInt = { 1, 5, 7, 8, 4, 3, 9, 4 };

		Arrays.sort(intInt);
		for (int i = 0; i < intInt.length; i++) {
			System.out.println(intInt[i]);
		}
	}

	/**
	 * 一、冒泡排序(BubbleSort) 1. 基本思想：
	 * 两两比较排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。 2. 排序过程：
	 * 设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，
	 * 从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上， 重者在下为止。
	 */

	private static void bubbleSort(int[] list) {
		if (list != null && list.length > 0) {
			for (int i = 1; i < list.length; i++) {
				for (int j = 0; j < list.length - i; j++) {
					if (list[j] > list[j + 1]) {// 后一个数大于前一个数（升序）
						int temp = list[j + 1];
						list[j + 1] = list[j];
						list[j] = temp;
					}
				}

				/*
				 * for(int j = 0; j < list.length - i; j++){ if(list[j] < list[j
				 * + 1]){//前一个数大于后一个数（降序） int temp = list[j + 1]; list[j + 1] =
				 * list[j]; list[j] = temp; } }
				 */
			}

			// 打印出已经排序好的数组
			for (int k = 0; k < list.length; k++) {
				int i = list[k];
				System.out.println("i === " + i);
			}
		}
	}

	/**
	 * 二、选择排序
	 * 
	 * 1. 基本思想： 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 2.
	 * 排序过程： 【示例】： 初始关键字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 ［38 65 97 76 49 27
	 * 49] 第二趟排序后 13 27 ［65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49]
	 * 第四趟排序后 13 27 38 49 [49 97 65 76] 第五趟排序后 13 27 38 49 49 [97 97 76] 第六趟排序后
	 * 13 27 38 49 49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序结果 13 27
	 * 38 49 49 76 76 97
	 */

	private static void selectSort(int[] array) {
		if (array != null && array.length > 0) {
			for (int i = 0; i < array.length; i++) {
				int postion = i;
				for (int k = i + 1; k < array.length; k++) {// （升序）
					if (array[postion] > array[k]) {
						int temp = array[postion];
						array[postion] = array[k];
						array[k] = temp;
					}
				}

				/*
				 * for(int k = i + 1 ; k < array.length ; k++){//（降序）
				 * if(array[postion] < array[k]){ int temp = array[postion];
				 * array[postion] = array[k]; array[k] = temp; } }
				 */
			}

			// 打印出已经排序好的数组
			for (int k = 0; k < array.length; k++) {
				int i = array[k];
				System.out.println("i === " + i);
			}

		}
	}

	/***
	 * 
	 * 三、插入排序(Insertion Sort) 1. 基本思想：
	 * 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程：
	 * 
	 * 【示例】： [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49
	 * J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49
	 * J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49
	 * J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97]
	 */

	private static void insertionSort(int numlist[]) {

		for (int i = 1; i < numlist.length; i++) {
			int temp = numlist[i];
			int j = i;
			while (j > 0 && numlist[j - 1] >= temp) {
				numlist[j] = numlist[j - 1];
				--j;
			}
			numlist[j] = temp;
		}

		// 打印出已经排序好的数组
		for (int k = 0; k < numlist.length; k++) {
			int i = numlist[k];
			System.out.println("i === " + i);
		}
	}
	
	/**
	 * 二分法查找
	 * @param a
	 * @param value
	 * @return
	 */
	public static int binarySearch(int []a, int value) {

		int size = a.length;
		int low = 0;
		int high = size - 1;
		int mid;
		while (low <= high) {
			mid = (low + high) / 2;
			if (a[mid] < value) {
				low = low + 1;
			} else if (a[mid] > value) {
				high = high - 1;
			} else {
				return mid;
			}
		}
		return -1;
	}
}