[数据结构与算法]排序算法（java）

1、插入排序

插入排序由 $N?1$ 趟排序组成，对于 $p=1$ 到 $N?1$ 趟，插入排序保证位置 $0$ 到 $p$ 上的元素为已排序状态。

• 排序思路是，在第 $p$ 趟时，将位置 $p$上的元素向左移动，直到在前$p+1$ 个元素中找到正确位置。

public static void insertionSort(int[] array){
        int j;
        for (int p = 1; p < array.length; p++){
            int tmp = array[p];
            for (j = p; j > 0 && tmp < array[j - 1]; j--) {
                array[j] = array[j - 1];
            }
            array[j] = tmp;
        }
    }

2、希尔排序

• 又称作为缩减增量排序，通过比较一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减少，直到比较相邻的元素为最后一趟排序为止。
• 希尔排序使用一个序列为 $h_1$，$h_2$，…，$h_t$ 叫作增量序列，只要 $h_1=1$ 任何增量序列都是可行的，只不过有些增量序列更好。Shell建议（但是不好）的序列是 $h_t=?N/2?$，$h_k=?h_{k+1}/2?$，使用希尔增量的最坏情形是 $O(N^2)$。
• 但希尔增量未必互素，Hibbard 提出了一个增量序列$1，3，7，\dots 2^k?1$。这些增量没有公因子，最坏情形为$O(N^{3/2})$，但还有更优的增量序列。
• 一趟 $h_k$ 排序就是对 $h_k$ 个小数组进行插入排序。

public static void shellsort(int[] a){
        int j;
        for (int gap = a.length / 2; gap > 0; gap = gap / 2) {
            for (int i = gap; i < a.length; i++){
                int tmp = a[i];
                for (j = i; j >= gap && tmp < a[j - gap]; j -= gap){
                    a[j] = a[j - gap];
                }
                a[j] = tmp;
            }
        }
    }

3、堆排序

(未完待续）

参考文献：Data Structures and Algorithm Analysis in Java, Third Edition, Mark Allen Weiss.