冒泡排序，选择排序，插入排序，归并排序

package com.sort;

import org.junit.Test;

public class SortTest {
	int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7, 6, 5, 4, 3, 2, 1 };

	@Test
	public void testMapPao() {
		// maoPaoSort(arr);
		// xuanzeSort(arr);
		// insertSort(arr);
		// mergeSort(arr, 0, (arr.length - 1) / 2, arr.length - 1);
                quickSort(arr,0,arr.length-1)
		printArr(arr);
	}

	public static void printArr(int[] arr) {
		for (int i : arr) {
			System.out.print(i + ",");
		}
	}

	/**
	 * 冒泡
	 * 
	 * @param arr
	 */
	public static void maoPaoSort(int[] arr) {
		int len = arr.length;
		int temp;
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len - 1 - i; j++) {
				if (arr[j] > arr[j + 1]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
	}

	/**
	 * 选择
	 * 
	 * @param arr
	 */
	public static void xuanzeSort(int[] arr) {
		int len = arr.length;
		int temp;
		for (int i = 0; i < len - 1; i++) {
			int index = i;
			for (int j = i + 1; j < len; j++) {
				if (arr[j] < arr[index]) {
					index = j;
				}
			}
			if (index != i) {
				temp = arr[i];
				arr[i] = arr[index];
				arr[index] = temp;
			}
		}
	}

	/**
	 * 插入
	 * 
	 * @param arr
	 */
	private void insertSort(int[] arr) {
            for (int i = 1; i < arr.length; i++) {
                int tempIndex = 0;
                int tempValue = arr[i];
                for (int j = i - 1; j >= 0; j--) {
                    if (tempValue < arr[j]) {
                        arr[j + 1] = arr[j];
                    } else {
                        tempIndex = j + 1;
                        break;
                    }
                }
                arr[tempIndex] = tempValue;
            }
        }

	/**
	 * 归并
	 * 
	 * @param arr
	 * @param left
	 * @param center
	 * @param right
	 */
	public static void mergeSort(int[] arr, int left, int center, int right) {
		// base
		if (left == right) {
			return;
		}

		// merge
		mergeSort(arr, left, (left + center) / 2, center);
		mergeSort(arr, center + 1, (center + 1 + right) / 2, right);

		// detail
		int[] sortArr = new int[right + 1 - left];
		int curLeft = left;
		int curRight = center + 1;
		int index = 0;
		while (curLeft <= center && curRight <= right) {
			if (arr[curLeft] <= arr[curRight]) {
				sortArr[index++] = arr[curLeft++];
			} else {
				sortArr[index++] = arr[curRight++];
			}
		}

		while (curLeft <= center) {
			sortArr[index++] = arr[curLeft++];
		}

		while (curRight <= right) {
			sortArr[index++] = arr[curRight++];
		}

		for (int i = 0; i < sortArr.length; i++) {
			arr[left + i] = sortArr[i];
		}
	}

    /**
     * 快速排序简易实现
     * @param arr
     * @param begin
     * @param end
     */
    public static void quickSort(int[] arr, int begin, int end) {
        //base
        if (begin >= end) {
            return;
        }
        //detail
        int leftIndex = begin;
        int rightIndex = end - 1;
        int tempIndex = end;

        while (leftIndex < rightIndex) {
            while (leftIndex < rightIndex && arr[leftIndex] < arr[tempIndex]) {
                leftIndex++;
            }
            while (rightIndex > leftIndex && arr[rightIndex] >= arr[tempIndex]) {
                rightIndex--;
            }
            if (rightIndex != leftIndex) {
                int temp = arr[leftIndex];
                arr[leftIndex] = arr[rightIndex];
                arr[rightIndex] = temp;
            }
        }

        //leftIndex = rightIndex
        if (arr[leftIndex] >= arr[tempIndex]) {
            int temp = arr[leftIndex];
            arr[leftIndex] = arr[tempIndex];
            arr[tempIndex] = temp;
        } else {
            leftIndex = tempIndex;
        }
        //merge
        quickSort(arr, begin, leftIndex - 1);
        quickSort(arr, leftIndex + 1, end);
    }

}

冒泡排序：http://baike.sogou.com/v111984.htm?fromTitle=冒泡排序

选择排序：http://baike.sogou.com/v7538686.htm?fromTitle=选择排序

插入排序：http://baike.sogou.com/v7832934.htm?fromTitle=插入排序

归并排序：http://baike.sogou.com/v8340582.htm?fromTitle=归并排序