/**
 * 插入排序：直接插入排序
 */
public static void inlineSort(int[] data) {
    int j, tmp;
    for (int i = 1; i < data.length; i++) {
        //若data[i]大于等于有序区中所有的元素则data[i]不动
        if (data[i] < data[i - 1]) {
            //把当前元素复制一份副本
            tmp = data[i];
            //找插入位置
            for (j = i - 1; j > -1 && tmp < data[j]; j--) {
                //元素后移
                data[j + 1] = data[j];
            }
            //插入data[i]到正确位置
            data[j + 1] = tmp;
        }
    }
}

/**
 * 插入排序：希尔排序
 */
public static void shellSort(int[] data) {
    //计算最大分组间隔
    int increment = 1;
    while (increment <= data.length / 3) {
        increment = increment * 3 + 1;
    }

//按照增量序列对顺序表data希尔排序
    for (; increment > 0; increment = (increment - 1) / 3) {
        shellInsert(data, increment);
    }
}

/**
 * 希尔排序中的一趟插入排序
 *
 * @param data      待排序数组
 * @param increment 当前增量
 */
private static void shellInsert(int[] data, int increment) {
    int j, tmp;
    //将data[dk+1...]分别插入有序区
    for (int i = increment; i < data.length; i++) {
        if (data[i] < data[i - increment]) {
            //把当前元素复制一份副本
            tmp = data[i];
            j = i - increment;
            while (j > -1 && tmp < data[j]) {
                //元素后移，查找插入位置
                data[j + increment] = data[j];
                //查找前一记录
                j = j - increment;
            }
            //插入data[i]到正确位置
            data[j + increment] = tmp;
        }
    }
}

/**
 * 交换排序：冒泡排序
 *
 * @param data 待排序数组
 */
public static void bubbleSort(int[] data) {
    int tmp;
    for (int i = 0; i < data.length; i++) {
        for (int j = 0; j < data.length - 1; j++) {
            if (data[j] > data[j + 1]) {
                tmp = data[j + 1];
                data[j + 1] = data[j];
                data[j] = tmp;
            }
        }
    }
}

/**
 * 交换排序：快速排序（划分交换排序），是对冒泡排序的一种改进。
 *
 * @param data 待排序数组
 */
public static void quickSort(int[] data, int low, int high) {
    if (low < high) {
        //做一次划分排序
        int p = partition(data, low, high);
        //对左区间递归排序
        quickSort(data, low, p - 1);
        //对右区间递归排序
        quickSort(data, p + 1, high);
    }
}

/**
 * 一趟划分算法
 *
 * @param data 待排序数组
 * @param i    划分区间
 * @param j    划分区间
 * @return
 */
private static int partition(int[] data, int i, int j) {
    //用区间的第一个记录为基准
    int tmp = data[i];
    while (i < j) {
        while (i < j && data[j] >= tmp) {
            //从j所指的位置起向前（左）搜索
            j--;
        }
        if (i < j) {
            data[i] = data[j];
            i++;
        }
        while (i < j && data[i] <= tmp) {
            //从i所指的位置起向后（右）搜索
            i++;
        }
        if (i < j) {
            data[j] = data[i];
            j--;
        }
    }
    //基准记录tmp位于最终排序的位置i上
    data[i] = tmp;
    return i;
}

/**
 * 选择排序：直接选择排序
 *
 * @param data 待排序数组
 */
public static void straightSelectSort(int[] data) {
    int k, tmp;
    //做length-1趟排序
    for (int i = 0; i < data.length - 1; i++) {
        //设k为第i趟排序中关键字最小的记录位置
        k = i;
        //在[i...length-1]选择关键字最小的记录
        for (int j = i + 1; j < data.length; j++) {
            if (data[j] < data[k]) {
                //若有比data[k]小的记录则记住该位置
                k = j;
            }
        }
        if (k != i) {
            //与第i个记录交换
            tmp = data[i];
            data[i] = data[k];
            data[k] = tmp;
        }
    }
}

/**
 * 选择排序：堆排序，是对直接选择排序法的一种改进。
 *
 * @param data 待排序数组
 */
public static void heapSort(int[] data) {
    int i, tmp;
    for (i = (data.length - 1) / 2; i >= 0; i--) {
        sift(data, i, (data.length - 1));
    }
    for (i = (data.length - 1); i >= 1; i--) {
        tmp = data[0];
        data[0] = data[i];
        data[i] = tmp;
        sift(data, 0, i - 1);
    }
}

/**
 * 调整为大根堆
 *
 * @param data 待排序数组
 * @param i    开始
 * @param h    结束
 */
private static void sift(int[] data, int i, int h) {
    int x = data[i];
    int j = 2 * i;
    while (j <= h) {
        if (j < h && data[j] < data[j + 1]) {
            j++;
        }
        if (x >= data[j]) {
            break;
        }
        data[i] = data[j];
        i = j;
        j = 2 * i;
    }
    data[i] = x;
}

/**
 * 归并排序
 *
 * @param data 待排序数组
 * @param n    待排序数组长度
 */
public static void mergeSort(int[] data, int n) {
    if (n < 2) {
        return;
    }
    int mid = n / 2;
    int[] l = new int[mid];
    int[] r = new int[n - mid];

for (int i = 0; i < mid; i++) {
        l[i] = data[i];
    }
    for (int i = mid; i < n; i++) {
        r[i - mid] = data[i];
    }
    mergeSort(l, mid);
    mergeSort(r, n - mid);

merge(data, l, r, mid, n - mid);
}

/**
 * 合并结果
 *
 * @param a
 * @param l
 * @param r
 * @param left
 * @param right
 */
private static void merge(int[] a, int[] l, int[] r, int left, int right) {

int i = 0, j = 0, k = 0;
    while (i < left && j < right) {
        if (l[i] <= r[j]) {
            a[k++] = l[i++];
        } else {
            a[k++] = r[j++];
        }
    }
    while (i < left) {
        a[k++] = l[i++];
    }
    while (j < right) {
        a[k++] = r[j++];
    }
}