数据结构与算法篇-希尔排序
时间:2021-09-10 16:31:49
手机看文章
扫描二维码
随时随地手机看文章
[导读]01—希尔排序算法思想希尔排序也是一种插入排序,是简单插入排序改进后的一个更高效版本,同时也是首批突破O(n^2)算法之一。希尔排序算法思想:希尔排序是按照下标增量进行分组,对每组使用插入排序算法进行排序,随着增量减少,每组包含的关键字越来越多,增量减到1时,整个序列被分为一组,...
01—希尔排序算法思想
希尔排序也是一种插入排序,是简单插入排序改进后的一个更高效版本,同时也是首批突破O(n^2)算法之一。希尔排序算法思想:希尔排序是按照下标增量进行分组,对每组使用插入排序算法进行排序,随着增量减少,每组包含的关键字越来越多,增量减到1时,整个序列被分为一组,算法终止。我们以增序排序为例,希尔排序基本步骤:选择初始增量gap = length / 2,缩小增量继续以gap = gap / 2的方式进行,直到增量gap = 1为止,增量的每次变化都会将原始序列划分为若干组,分别对每一组进行插入排序,每一次通过增量划分组进行插入排序宏观上小的数移到了前面,大的数移到了后面,最后增量gap = 1进行插入排序后就是最终的有序序列。本文会以图解的方式详细介绍希尔排序算法的整个工作过程。原始序列
增量gap = 4分组图
增量gap = 4排序结果图
增量gap = 2分组图增量gap = 2排序结果图
增量gap = 1分组图
增量gap = 1排序结果图
02—希尔排序算法实现希尔排序完整源码如下:
//插入排序
void insert_sort(int *arr, int length, int start, int gap){
if(arr == NULL || length <= 0 || start < 0 || gap <= 0){
return;
}
int i = 0, j = 0;
int value = 0;
for(i = start; i < length - gap; i = gap){
value = arr[i gap];
for(j = i; j >= start; j -= gap){
if(value < arr[j]){
arr[j gap] = arr[j];
}else{
break;
}
}
arr[j gap] = value;
}
}
//希尔排序
void shell_sort(int *arr, int length){
if(arr == NULL || length <= 0){
return;
}
int gap = 0, start = 0;
int count = 0;
for(gap = length / 2; gap > 0; gap /= 2){
start = 0;
for(count = 0; count < length / gap; count ){
insert_sort(arr, length, start, gap);
start ;
}
}
}
现在写一个小程序验证算法的正确性,代码如下:#include
#include "shell_sort.h"
int main() {
int i = 0;
printf("希尔排序结果\n");
int arr[7] = {8, 23, 64, 12, 0, 5, 6};
shell_sort(arr, 7);
for(i = 0; i < 7; i ){
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
编译运行输出如下:
希尔排序结果
0 5 6 8 12 23 64
算法完全正确!
版权申明:内容来源网络,版权归原创者所有。除非无法确认,都会标明作者及出处,如有侵权烦请告知,我们会立即删除并致歉。谢谢!