1. 冒泡排序

描述

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

代码

 /**
 * 冒泡排序
 * 
 * @param array
 * @return
 */
public static int[] bubbleSort(int[] array) {

    if (array.length == 0) {
        return array;
    }

    for (int i=1; i < array.length; i++) {// 执行多少次数组的走访
        for (int j=0; j< array.length-i; j++) {// array.length-i: 每次走访最后一个元素的索引，j不能取这个值
            if (array[j] > array[j+1]) {
                int temp = array[j+1];
                array[j+1] = array[j];
                array[j] = temp;
            }
        }
    }

    return array;
}

2. 选择排序

描述

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

代码

/**
 * 选择排序
 *
 * @param array
 * @return
 */
public static int[] selectionSort(int[] array) {

    if (array.length == 0) {
        return array;
    }

    for (int i=0; i<array.length-1; i++) {// 确定待选择序列的起始位置

        int minIndex = i; // 默认最小的数为待选择序列的起始元素

        // 从待选择序列中找出最小元素的索引
        for (int j = i+1; j<array.length; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }

        // 将最小的元素与待选择序列的起始元素进行交换
        int temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }

    return array;
}

3.插入排序

描述

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

代码

/**
 * 插入排序
 *
 * @param array
 * @return
 */
public static int[] insertionSort(int[] array) {

    if (array.length == 0) {
        return array;
    }

    for (int i=1; i<array.length; i++) {// 默认初始已排序的序列为仅包含索引为0的元素的序列

        int j = i;
        while (j >0 && array[j] < array[j-1]) {
            int temp = array[j-1];
            array[j-1] = array[j];
            array[j] = temp;
            j--;// 交换之后继续和前一个数进行对比
        }

    }

    return array;
}

4. 希尔排序

描述

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

代码

/**
 * 希尔排序
 *
 * @param array
 * @return
 */
public static int[] shellSort(int[] array) {

    if (array.length == 0) {
        return array;
    }

    int gap = array.length / 2;
    while (gap > 0) {
        for (int i = gap; i < array.length; i++) {
            int j = i;
            while (j-gap>=0 && array[j] < array[j-gap]) {
                int temp = array[j-gap];
                array[j-gap] = array[j];
                array[j] = temp;
                j -= gap;
            }
        }

        gap /= 2;
    }

    return array;
}

5. 快速排序

描述

快速排序（Quicksort）是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

代码

/**
 * 快速排序
 *
 * @param array
 * @param start
 * @param end
 * @return
 */
public static int[] quickSort(int[] array, int start, int end) {

    if (start >= end) {
        return array;
    }

    int low = start;
    int high = end;
    int middleValue = array[low];

    while (low < high) {
        // high左移
        while (low < high && array[high] >= middleValue) {
            high--;
        }
        array[low] = array[high];

        // low右移
        while (low < high && array[low] < middleValue) {
            low++;
        }
        array[high] = array[low];
    }

    // 从循环退出: low == high
    array[low] = middleValue;

    // 对low左边的列表进行快速排序
    quickSort(array, start, low - 1);
    // 对low右边的列表进行快速排序
    quickSort(array, low + 1, end);

    return array;
}

6. 归并排序

描述

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

代码

/**
 * 归并排序
 * 
 * @param array
 * @return
 */
public static int[] mergeSort(int[] array) {

    if (array.length < 2)
        return array;

    int mid = array.length / 2;
    int[] left = Arrays.copyOfRange(array, 0, mid);
    int[] right = Arrays.copyOfRange(array, mid, array.length);

    return merge(mergeSort(left), mergeSort(right));
}

/**
 * 归并: 将两段排序好的数组结合成一个排序数组
 *
 * @param left
 * @param right
 * @return
 */
private static int[] merge(int[] left, int[] right) {

    int[] result = new int[left.length + right.length];
    for (int index =0, i=0, j=0; index < result.length; index++) {
        if (i >= left.length)
            result[index] = right[j++];
        else if (j >= right.length)
            result[index] = left[i++];
        else if (left[i] > right[j])
            result[index] = right[j++];
        else
            result[index] = left[i++];
    }

    return result;
}