【基础算法】希尔排序法&C++实现|[实例过程详细分析]-创新互联
目录
创新互联公司-专业网站定制、快速模板网站建设、高性价比喀什网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式喀什网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖喀什地区。费用合理售后完善,10多年实体公司更值得信赖。●希尔排序法
1.简要介绍
2.图形化演示
3.代码如下
4.结果如下
●希尔排序法 1.简要介绍
希尔排序算法是基于插入排序法的思想,其又被称为希尔排序或者缩小增量排序。它的具体流程如下:(结合希尔排序算法代码段理解)
for (int r = n / 2; r >= 1; r /= 2) //化组排序
{
for (int i = r; i< n; i++)
{
int temp = arr[i];
int j = i - r;
while (j >= 0 && temp< arr[j])
{
arr[j + r] = arr[j];
j -= r;
}
arr[j + r] = temp;
}
}
①将有n个元素的数组分成n/2个数字序列(化组操作)。进行第一次循环:第1个数据和第n/2+1个数字序列为一个比较对,判断是否执行while循环,若执行则进行循环操作(插入排序思想);反之,则将n/2+1数字放回原位。进行第二次循环:第2个数据和第n/2+2个数字序列为一个比较对,判断是否执行while循环,若执行则进行循环操作(插入排序思想);反之,则将n/2+2数字放回原位。操作如上......(插入排序法:http://t.csdn.cn/ukSxu)
②一整次循环使每一个序列对排好顺序
③然后,再将这有n个元素的数组分成n/4个序列(化组操作),再次进行排序
④不断重复上述流程,随着序列减少,直到变为一个序列对,也就完成了整个排序过程
2.图形化演示(在下面的图中,虚线表示不符合while循环判断,实线表示符合并执行while循环判断,实线下面的数字符号为执行了几次的while循环。红色箭头的temp在每次的while判断语句中为每一个数字序列比较对中的值,它在每次循环中是进行后移的。结合代码和输出结果对下面的过程进行理解)
初始状态:
第一次化组:
第二次化组:
第三次化组:
结束状态:
3.代码如下#includeusing namespace std;
#define size 10
class shellsort {
public:
void shellsort_1();
void showresult();
int arr[size];
};
void shellsort::shellsort_1()
{
int x=0;
for (int r = size / 2; r >= 1; r /= 2) //化组排序
{
for (int i = r; i< size; i++)
{
int temp = arr[i];
int j = i - r;
while (j >= 0 && temp< arr[j])
{
arr[j + r] = arr[j];
j -= r;
}
arr[j + r] = temp;
}
//测试代码
x++;
cout<< "第"<< x<< "步排序的结果:";
for (int i = 0; i< size; i++)
{
cout<< arr[i]<< " ";
}
cout<< endl;
}
}
void shellsort::showresult()
{
for (int i = 0; i< size; i++)
{
cout<< arr[i]<< " ";
}
cout<< endl;
}
void text()
{
shellsort ss;
cout<< "请输入要排序的10个数:"<< endl;
for (int i = 0; i< size; i++)
{
cin >>ss.arr[i];
}
ss.shellsort_1();
cout<< "排序后的10个数为:"<< endl;
ss.showresult();
}
int main()
{
text();
}
4.结果如下 你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
本文题目:【基础算法】希尔排序法&C++实现|[实例过程详细分析]-创新互联
标题链接:http://pwwzsj.com/article/pehhs.html