一些辅助函数。

/**
 * 辅助函数：用于交换两个值
 *
 * @param array
 * @param a
 * @param b
 */
public static void exchange(int[] array, int a, int b) {
    int tmp = array[a];
    array[a] = array[b];
    array[b] = tmp;
}
/**
 * 辅助函数：用于比较大小
 *
 * @param valueA
 * @param valueB
 * @return
 */
public static Boolean less(int valueA, int valueB) {
    return valueA < valueB;
}

选择排序

基本思路：首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组中的第二个元素交换位置。如此往复，直到将整个数组排序。

/**
 * 选择排序算法
 *
 * @param array
 * @return
 */
public static int[] selection(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int min = i;
        for (int j = i + 1; j < array.length; j++) {
            if (less(array[j], array[min])) min = j;
        }
        exchange(array, i, min);
    }
    return array;
}

比较次数和交换次数

第一轮循环比较 次、第二轮循环比较 次、第三轮循环比较 次 … 第 轮循环比较 次。

所以是一个以 ，，公差为 ，一共 项的等差数列。

求和为。

从代码中可以知道一共交换次数为 N 次。

插入排序

基本思路：通过构建有序序列，对于未排序的数据，在已排序序列中从后往前扫描，找到相应的位置插入并插入。需要反复地把已排序元素逐步向后挪位，为最新的元素提供插入空间。

/**
 * 插入排序算法
 * @param array
 * @return
 */
public static int[] Insertion(int[] array) {
    for (int i = 1; i < array.length; i++) {
        for (int j = i; j > 0  && less(array[j], array[j - 1]); j--) {
            exchange(array, j, j - 1);
        }
    }
    return array;
}

比较的次数和交换次数

最坏情况

数列是一个降序数组。

第一轮循环比较 次、第二轮循环比较 次、第三轮循环比较 次 … 第 轮循环比较 次。

所以是一个以 ，，公差为 ，一共 项的等差数列。

求和为。

因为每次比较都需要交换，所有交换次数也是 。

最好情况

数组是一个升序数组。

交换次数为 次，比较次数为 （因为每轮循环都只会比较一次）。

平均情况

把最好的情况和最差情况求和平均。

平均比较次数 。
平均交换次数 。

希尔排序

基本思路：将待排序的数组元素按小标的一定增量分组，分成多个子序列，然后对各个子序列进行直接的排序算法排序；然后依次缩减增量再进行排序，直到增量为 1 时，进行最后一次直接插入排序，排序结束。

讲解视频 ShellSort.mp4

/**
 * 希尔排序算法
 * @param array
 * @return
 */
public static int[] ShellSort(int[] array) {
    int N = array.length;
    int h = 1;
    if(h < N / 3) h = h * 3 + 1;
    while (h >= 1){
        for(int i = h; i < N; i++) {
            for(int j = i; j >= h && less(array[j], array[j-h]); j -= h) {
                exchange(array, j, j - h);
            }
         }
        h = h / 3;
    }
    return array;
}

交换次数和比较次数不会算。。。。

参考：

• 《算法》（第四版）第 2 章 初级排序算法
• 排序：希尔排序（算法）