public static void main(String[] args) {
    int[] array = { 42, 20, 17, 13, 28, 14, 23, 15,3 };
    Test test = new Test();
    // test.bubbleSort(array);
    // test.selctionSort(array);
    // test.insertionSort(array);
    test.shellSort(array);
}

/**
 * 冒泡排序 - 遍历所有未排好序的数据，两两比较大小，把较小的往前移动
 * 
 * @param array
 */
public void bubbleSort(int[] array) {
    System.out.println("冒泡排序");
    int length = array.length;
    for (int i = 0; i < length - 1; i++) {
        for (int j = length - 1; j > i; j--) {
            if (array[j - 1] > array[j]) {
                array[j - 1] += array[j];
                array[j] = array[j - 1] - array[j];
                array[j - 1] -= array[j];
            }

        }
        System.out.println();
        System.out.println(Arrays.toString(array));
    }
}

/**
 * 选择排序 - 遍历所有未排好序的数据，记录数组中最小值的下标最后和未排序的最小下标交换数据
 * 
 * @param array
 */
public void selctionSort(int[] array) {
    System.out.println("选择排序");
    int length = array.length;
    for (int i = 0; i < length - 1; i++) {
        int index = i;
        for (int j = i + 1; j < length; j++) {
            if (array[index] > array[j]) {
                index = j;
            }
        }
        if (index != i) {
            array[i] += array[index];
            array[index] = array[i] - array[index];
            array[i] -= array[index];
        }
        System.out.println();
        System.out.println(Arrays.toString(array));
    }
}

/**
 * 插入排序 - 遍达未排序的前N个数据进行冒泡排序，N由循环决定
 * 
 * @param array
 */
public void insertionSort(int[] array) {
    System.out.println("插入排序");
    int length = array.length;
    for (int i = 0; i < length - 1; i++) {
        for (int j = i + 1; j > 0; j--) {
            if (array[j - 1] > array[j]) {
                array[j - 1] += array[j];
                array[j] = array[j - 1] - array[j];
                array[j - 1] -= array[j];
            }
        }
        System.out.println();
        System.out.println(Arrays.toString(array));
    }
}

/**
 * 希尔排序 - 对子序列分别进行排序
 * 
 * @param array
 */
public void shellSort(int[] array) {
    System.out.println(Arrays.toString(array));
    int lenth = array.length;
    int incre = lenth;
    while (true) {
        incre = incre / 2;
        for (int k = 0; k < incre; k++) { // 根据增量分为若干子序列
            for (int i = k + incre; i < lenth; i += incre) {
                for (int j = i; j > k; j -= incre) {
                    if (array[j] < array[j - incre]) {
                        array[j - incre] += array[j];
                        array[j] = array[j - incre] - array[j];
                        array[j - incre] -= array[j];
                    } else {
                        break;
                    }
                }
            }
        }
        System.out.println();
        System.out.println(Arrays.toString(array));
        if (incre == 1) {
            break;
        }
    }
}