排序算法 - 希尔排序(Shell Sort)

by LauCyun Aug 08,2014 21:20:18 4,559 views

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
  • 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位

 

1 算法思想

先取一个正整数\(gap_{1}<n\)作为第一个增量,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;然后,取第二个增量\(gap_{2}<gap_{1}\),重复上述的分组和排序,直至所取的增量\(gap_{i}=1\),即所有记录放在同一组中进行直接插入排序为止。

下面以一组待排序的8个数据[69, 65, 90, 37, 92, 6, 28, 54]演示希尔排序的过程,如图1所示。

图1 希尔排序过程

2 算法实现

C++

#include<iostream>

using namespace std;
const int N = 8;
using ElemType = int;

void ShellSort(ElemType *array, int n);
void Show(ElemType *array);

void ShellSort(ElemType *array, int n) {
    int gap, i, j;
    ElemType temp;
    for (gap = n >> 1; gap > 0; gap >>= 1) {
        cout << "gap = " << gap << endl;
        for (i = gap; i < n; i++) {
            cout << "i = " << i << " => ";
            for (j = i - gap; j >= 0; j -= gap) {
                if (array[j] > array[j + gap]) {
                    temp = array[j];
                    array[j] = array[j + gap];
                    array[j + gap] = temp;
                }
            }
            Show(array);
        }
        cout << endl;
    }
}

void Show(ElemType *array) {
    for (int i = 0; i < N; i++) {
        printf("%-4d", array[i]);
    }
    cout << endl;
}

int main() {
    ElemType array[N] = {69, 65, 90, 37, 92, 6, 28, 54};
    cout << "排序前:" << endl;
    Show(array);
    cout << "排序过程:" << endl;
    ShellSort(array, N);
    cout << "排序结果:" << endl;
    Show(array);
    return 0;
}

Python

 #!/usr/bin/env python
# -*- coding: utf-8 -*-


def shell_sort(list):
    n = len(list)
    # 初始步长
    gap = n >> 1
    while gap > 0:
        for i in range(gap, n):
            # 每个步长进行插入排序
            temp = list[i]
            j = i
            # 插入排序
            while j >= gap and list[j - gap] > temp:
                list[j] = list[j - gap]
                j -= gap
            list[j] = temp
        # 得到新的步长
        gap = gap >> 1
    return list


unsortedArray = [69, 65, 90, 37, 92, 6, 28, 54]
print(shell_sort(unsortedArray))

 

3 算法过程演示

如果显示不正常,请戳这里

 

4 稳定性

由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。

 

5 复杂度分析

5.1 增量序列的选择

Shell排序的执行时间依赖于增量序列。

好的增量序列的共同特征:

  • 最后一个增量必须为1;
  • 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

有人通过大量的实验,给出了较好的结果:当\(n\)较大时,比较和移动的次数约在\(n^{1.25}\)\(n^{1.6}\)之间。

5.2 Shell排序的时间性能优于直接插入排序

希尔排序的时间性能优于直接插入排序的原因:

  • 当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
  • 当n值较小时,\(n\)\(n^2\)的差别也较小,即直接插入排序的最好时间复杂度\(O(n)\)和最坏时间复杂度\(O(n^2)\)差别不大。
  • 在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量\(gap_{i}\)逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按\(gap_{i-1}\)作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。

因此,希尔排序在效率上较直接插入排序有较大的改进。

空间复杂度:\(O(n)\)

 

6 参考文档

(全文完)

Tags