排序算法

public static void insertSort(int[] array) {
    // 将第一个记录看成已经排序好的序列
    for(int i = 1; i < array.length; i++) {
        // 要插入的记录
        int temp = array[i];
        // 找到排序好的第一个记录进行比较
        int j = i - 1;
        // 如果到底了，或者找到了插入的位置
        while(j >= 0 && array[j] > temp) {
            // 后移，空出位置
            array[j + 1] = array[j];
            j--;
        }
        // 插入到j的后面
        if(j != i - 1) {
            array[j + 1] = temp;
        }
    }
}

public static void shellSort(int[] table) {
    // 增量最开始等于length/2，并逐渐减少
    for (int gap = table.length / 2; gap > 0; gap /= 2) {
        // 从gap个元素，逐个对其所在组进行直接插入排序操作
        for (int i = gap; i < table.length; i++) {
            int j = i;
            int temp = table[j];
            if (table[j] < table[j - gap]) {
                while (j - gap >= 0 && temp < table[j - gap]) {
                    // 移动法
                    table[j] = table[j - gap];
                    j -= gap;
                }
                table[j] = temp;
            }
        }
    }
}

public static void selectSort(int[] table) {
    int temp;
    for (int i = 0; i < table.length; i++) {
        for(int j = i + 1; j < table.length; j++) {
            if(table[j] < table[i]) {
                temp = table[j];
                table[j] = table[i];
                table[i] = temp;
            }
        }

    }
}

public static void bubbleSort(int table[]) {
    for (int i = 0; i < table.length; i++) {
        for(int j = 0; j < table.length-i-1; j++) {
            // 如果i位置比j位置大，则i往前移一个位置
            if(table[j] > table[j+1]) {
                int temp = table[j];
                table[j] = table[j+1];
                table[j+1] = temp;
            }
        }
    }
}

// 分区
public static int partition(int[] array, int left, int right) {
    int pivot = array[( left + right) / 2];
    int temp;
    while (left < right) {
        // 找到左边第一个比基准小的
        while (array[left] < pivot)
            left++;
        // 找到右边第一个比基准大的
        while (array[right] > pivot)
            right--;

        // 如果符合条件，则交换两边位置
        if(left < right) {
            temp= array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }
    // 返回基准点左边的
    return left;
}

// 快速排序
public static void quickSort(int[] array, int left, int right) {
    int index = partition(array, left, right);
    // 递归排序左边
    if(left < index -1) {
        quickSort(array, left, index -1);
    }
    // 递归排序右边
    if (index + 1 < right) {
        quickSort(array, index, right);
    }
}

public static void mergeSort(int[] array, int low, int high) {
        if(low < high) {
            int middle = (low + high) / 2;
            mergeSort(array, low, middle);
            mergeSort(array, middle + 1, high);

            merge(array, low, middle, high);
        }
    }

/**
 * 归并数组
 *
 * 将目标数组的所有元素拷贝到临时数组helper中，记下左右位置
 * 迭代访问helper，将左右两半中较小的元素复制到目标数组
 * 最后将余下所有的元素复制回目标数组
 */
public static void merge(int[] array, int low, int middle, int high){
    // 填充辅助数组
    int[] helper = new int[array.length];
    for (int i = 0; i <= high; i++) {
        helper[i] = array[i];
    }

    int helperLeft = low;
    int helperRight = middle + 1;
    int current = low;

    /**
     * 迭代访问helper数组，比较左右两半元素
     * 并将较小的元素复制到原先的数组中
     */
    while(helperLeft <= middle && helperRight <= high){
        if(helper[helperLeft] <= helper[helperRight]){
            array[current] = helper[helperLeft];
            helperLeft++;
        } else{
            array[current] = helper[helperRight];
            helperRight++;
        }
        current++;
    }

    /**
     * 将数组左半剩余元素复制到原先的数组中
     */
    int remaining = middle - helperLeft;
    for(int i = 0; i <= remaining; i++){
        array[current + i] = helper[helperLeft + i];
    }
}