希尔排序算法C/C++代码图文讲解 |
您所在的位置:网站首页 › 字符排序c语言代码 › 希尔排序算法C/C++代码图文讲解 |
希尔排序又称“缩小增量排序”,是插入排序的一种。直接插人排序,当待排序的记录个数较少且待排序序列的关键字基本有序时,效率较高。希尔排序基于以上两点,从“减少记录个数”和“序列基本有序”两个方面对直接插入排序进行了改进。 (1)步骤: 1. 先选定一个小于N的整数gap作为第一增量,然后将所有距离为gap的元素分在同一组,并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量,重复上述操作… 2. 当增量的大小减到1时,就相当于整个序列被分到一组,进行一次直接插入排序,排序完成。 (2)特点: 1. 缩小增量 2. 多遍插入排序 3. 时间复杂度:O(n 1.3 n^{1.3}n 1.3 ) 4. 空间复杂度:O(1) 5. 稳定性:不稳定 (3)动图演示: 这里重要的是理解分组思想,每一个组其实就是一个插入排序,相当于进行多次插入排序。 (4)C语言代码实现如下: #include #include #include int shell_sort(int arr[],int n) { register int i, j, tmp; int step; for(step = n/2; step > 0;step /= 2)/*增量步长*/ { /*step = 4 2 1*/ for(i = step; i = 0 && tmp |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |