考研数据结构编程 ch08排序 —— 希尔排序
2021/7/17 12:05:35
本文主要是介绍考研数据结构编程 ch08排序 —— 希尔排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
希尔排序
一、算法思想 (按递增排序)
- 1、关键
- ① 将数据根据 增量(步长)d,划分成若干个更差数列,每一个等差数列相当于一个子表。
- ② 第i子表:(a[i],a[i+d],a[i+2d]);i的取值范围: [1,d]。
- ③ 当步长d为1时,希尔排序就变成了直接插入排序。
- 2、注意!a[0]比较特殊。
- 3、在划分完子表之后,对各个子表进行直接插入排序。
- 4、增量d会改变,d=d/2,每轮循环d变成原来的二分之一,知道d为1。
// ! 希尔排序 void ShellSort(int arrList[], int n) { int i, j, d; // ! 注意,此时a[0]只是暂存单元,不是哨兵;当j<=0时,插入位置已到 for (d = n / 2; d >= 1; d /= 2) // ! 增量d改变 { // ! 每一轮,让增量d去划分子表,比如: (a[1], a[1+d], a[1+2d], ...) // ! 每一子表里,使用直接插入排序 for (i = d + 1; i <= n; i++) // ! 直接插入排序就是从第2个元素开始遍历的 { if (arrList[i] < arrList[i - d]) // ! 将a[i]插入有序增量子表 { arrList[0] = arrList[i]; for (j = i - d; j > 0 && arrList[j] > arrList[0]; j -= d) { arrList[j + d] = arrList[j]; } arrList[j + d] = arrList[0]; } } } }
二、具体测试代码
#include <iostream> using namespace std; // ! 希尔排序 void ShellSort(int arrList[], int n) { int i, j, d; // ! 注意,此时a[0]只是暂存单元,不是哨兵;当j<=0时,插入位置已到 for (d = n / 2; d >= 1; d /= 2) // ! 增量d改变 { // ! 每一轮,让增量d去划分子表,比如: (a[1], a[1+d], a[1+2d], ...) // ! 每一子表里,使用直接插入排序 for (i = d + 1; i <= n; i++) // ! 直接插入排序就是从第2个元素开始遍历的 { if (arrList[i] < arrList[i - d]) // ! 将a[i]插入有序增量子表 { arrList[0] = arrList[i]; for (j = i - d; j > 0 && arrList[j] > arrList[0]; j -= d) { arrList[j + d] = arrList[j]; } arrList[j + d] = arrList[0]; } } } } int main() { int a[] = {0, 38, 49, 65, 97, 76, 13, 27, 49}; ShellSort(a, 8); cout << "数组的元素个数: " << sizeof(a) / 4 << endl; for (int i = 0; i <= 8; i++) { cout << "a[" << i << "]: " << a[i] << " "; } return 0; }
这篇关于考研数据结构编程 ch08排序 —— 希尔排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding