希尔排序算法（Java实现）

希尔排序也称为缩小增量排序，它的基本思想是：

通过将待排序的元素分为若干子序列，利用直接插入排序思想对子序列进行排序；
然后将该子序列缩小，接着对子序列进行直接插入排序；
按照这种思想，直到所有的元素都按照关键字有序排列。

假设待排序的元素有 n 个，对应的关键字分别是 a₁,a₂,…,a_n，设距离（增量）为 c₁=4 的元素为同一个子序列，则元素的关键字 a₁,a₅,…,a_i,a_i+5,…,a_n-5 为一个子序列，同理，关键字 a₂,a₆,…,a_i+1,a_i+6,…,a_n-4 为一个子序列。然后分别对同一个子序列的关键字，利用直接插入排序进行排序。

之后，缩小增量，令 c₂=2，分别分别对同一个子序列的关键字进行插入排序。以此类推，最后令增量为 1，这时只有一个子序列，对整个元素进行排序。

例如，利用希尔排序的算法思想，对元素的关键字序列(56,22,67,32,59,12,89,26,48,37) 进行排序，其排序过程如下图所示。

图 1 希尔排序过程

希尔排序算法描述如下：

public void ShellInsert(int c)
// 对顺序表 L 进行一次希尔排序，c 是增量
{
    int t, j;
    for (int i = c; i < length; i++) // 将距离为 c 的元素作为一个子序列进行排序
    {
        if (data[i] < data[i - c]) // 若后者小于前者，则需要移动元素
        {
            t = data[i];
            j = i - c;
            while (j > - 1 && t < data[j]) {
                data[j + c] = data[j];
                j -= c;
            }
            data[j + c] = t;  // 依次将元素插入正确的位置
        }
    }
}

public void ShellInsertSort(int delta[], int m)
// 希尔排序，每次调用算法 ShellInsert，delta 是存放增量的数组
{
    for(int i = 0; i < m; i++) // 进行 m 次希尔插入排序
        ShellInsert(delta[i]);
}

对希尔排序的分析是一件非常复杂的事情，问题主要在于希尔排序选择的增量，但是经过大量的研究，当增量的序列为 2^m-k+1-1时，其中 m 为排序的次数，1≤k≤t，其时间复杂度为 O(n^3/2)。

希尔排序的空间复杂度为 O(1)。因此，说明希尔排序是一种不稳定的排序算法。

希尔排序算法（Java实现）

相关文章