当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 理解希尔排序

理解希尔排序

2018年05月29日  | 移动技术网IT编程  | 我要评论

天雅服装大厦,天歌三生情三世劫,石家庄市人力资源和社会保障局网站

我的博客链接：理解希尔排序

最近回顾了一下 《The C Programming Language》，其中提到了一个用来演示 for 循环的小例子，如下：

/** shell sort */
void shellsort(int[], int);

int main()
{
    int a[] = {1,23,34,24,32,25,31,3,36,40};
    int b[] = {32,31,30,29,28,27,26,25,24,23};
    shellsort(b, 10);
}

void shellsort(int v[], int n)
{
    int gap, i, j, temp;

    for(gap = n/2; gap > 0; gap /= 2) {
        for(i = gap; i<n; i++) {
            for(j=i-gap; j>=0 && v[j] > v[j+gap]; j-=gap) {
                temp = v[j];
                v[j] = v[j+gap];
                v[j+gap] = temp;
            }
        }
    }
}

这是一个希尔排序的例子，以每次 n/2 为步长，比较步长两边的元素的大小，步长是从大到小的，也就是说，一开始直接比较相距较远的两个元素，如果是逆序，则直接交换，比基于相邻比较的排序（冒泡排序，交换排序）跨越了更多的中间位置；然后最终步长为1能够保证所有元素都能正确被排序。步长为1时，退化为交换排序，但是其实这时序列是已经经过排序的，所以要比一开始就用交换排序要好。

希尔排序是第一批跨越 O(n2) 复杂度的排序算法之一。它是一种不稳定的排序算法，其性能与步长的取值有很大关系，Wikipedia上有关于各种步长选择下的性能比较：Shellsort#Gap_sequences。

为了帮助理解希尔排序的排序过程，可以看这个演示视频(需FQ)： Shell Sort Algorithm Example

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网