网站建设代理合同,模板网站建设多少钱,市场调查报告模板及范文,桂林北站到阳朔标题#xff1a;[数据结构] 排序#插入排序希尔排序
水墨不写bug 目录
#xff08;一#xff09;插入排序
实现思路#xff1a;
插入排序实现#xff1a;
#xff08;二#xff09;希尔排序
希尔排序的基本思想#xff1a;
希尔排序的实现#xff1a; 正…标题[数据结构] 排序#插入排序希尔排序
水墨不写bug 目录
一插入排序
实现思路
插入排序实现
二希尔排序
希尔排序的基本思想
希尔排序的实现 正文开始 排序是日常生活中常见的对数据的需求排序有多重不同的方法每一种方法都有各自的优缺点本文来为你介绍两个思路类似的排序方法插入排序和希尔排序。
一插入排序 时间复杂度ON^2 空间复杂度O1 特点元素越接近有序插入排序的效率越高。 稳定性稳定 实现思路 主要过程 对于区间一个有序区间 [0,end] 将区间后的一个元素 nums[end1] 插入到有序区间内。 由于nums[end1]在移动元素时会被覆盖需要一个临时变量tem暂时存储 nums[end1]具体来说将tem与nums[end]进行比较如果 tem nums[end] 则将end处的数据后移 nums[end1] nums[end] 并将end--继续比较。 如果 temnums[end] 说明已经到达要插入的位置直接break。 在出循环之后将tem插入正确的位置即可: nums[endgap] tem 整体实现注意事项 1.在实现过程中可以先写内层循环完成内层逻辑再写外层循环。 2.对于内层循环进行循环的条件是 end0 ,由于外层循环end从0开始如果内层进行循环的条件是end0,那么如果end 0就无法进入循环。 3.如何确定外层循环的区间 左区间从零开始对于最大的区间由于要将最后一个元素size-1位置插入到前面的区间 [0,size-2]内所以end最大可取 size-2 。 则区间为 [0,size-2](两闭区间)或者[0,size-1)(左闭右开区间)。 插入排序实现 #includeiostream
#includevector
using namespace std;void InsertSort(vectorint nums)
{//外层循环end从0开始遍历for (int i 0; i nums.size()-1; i){//[0,end] end1int end i;int tem nums[end 1];//内层循环end0时要进入循环while (end 0){if (nums[end] tem){nums[end 1] nums[end];--end;}elsebreak;}nums[end 1] tem;}
}
void Print(vectorint v)
{for (const auto e : v)cout e ;cout endl;
}
int main()
{vectorint nums { 55,9,8,6,7,59,75,89,12,50 };Print(nums);InsertSort(nums);Print(nums);return 0;
} 二希尔排序 希尔排序简单来说就是对插入排序的优化它与插入排序的整体思路是一致的。想要写好希尔排序就必须要讲究一个层次感你需要明白希尔排序的几层循环到底是在干什么。 希尔排序的基本思想 分组 将数组中间距为gap的数据分为一组如图所示gap 3 可以将一组数据分为gap组 我们将每一组数据看做是一个小组group对于每一个小组想要将他们排序自然需要移动由于小组内部数据相距gap所以移动的步幅也是gap。 希尔第一层次 也就是插入排序内层循环的逻辑唯一不同的是将步幅从1改为gap。 实现的操作 将一个数据 nums[endgap] 插入到已经有序的区间 [0,end] 内部并在插入后使整个区间保持有序。 由于nums[endgap]在移动元素时会被覆盖需要一个临时变量tem暂时存储 nums[endgap]具体来说将tem与nums[end]进行比较如果 tem nums[end] 则将end处的数据后移 nums[endgap] nums[end] 并将end-gap继续比较。 如果 temnums[end] 说明已经到达要插入的位置直接break。 在出循环之后将tem插入正确的位置即可: nums[endgap] tem 实现参考 int end;
int tem nums[end gap];
while (end 0)
{if (tem nums[end]){nums[end gap] nums[end];end - gap;}elsebreak;
}
nums[end gap] tem; 希尔第二层次 也就是插入排序外层循环的逻辑。 实现的操作 由于随着插入的进行区间不断扩大第二层次作用是不断改变区间的右端和定位并保存需要插入的元素 nums[endgap] 。 实现参考 for (int i 0; i n - gap; i gap)
{int end i;int tem nums[end gap];while (end 0){if (tem nums[end]){nums[end gap] nums[end];end - gap;}elsebreak;}nums[end gap] tem;
} 希尔第三层次 前两层次实现了对一个group的排序第三层就是要实现对所有group的排序。 实现的操作 外层创造循环变量j对区间起点 i 制造偏移量 for (int j 0; j gap; j)
{for (int i j; i n - gap; i gap){int end i;int tem nums[end gap];while (end 0){if (tem nums[end]){nums[end gap] nums[end];end - gap;}elsebreak;}nums[end gap] tem;}
} 希尔第四层次 前三层次完成了对某一特定gap下的预排序。第四层次就是要通过gap来逐渐让数组接近有序。 gap的意义是让数据跳动的步幅增大不同的大小的gap拥有不同的效果 如果gap较大数据跳动的步幅更大数据的移动更快但是更不容易接近有序。 对于较小的gap数据步幅减小数据移动的较慢但是更容易接近有序当gap取可取得的最小值1时整个排序逻辑就会退化为插入排序。 实现的操作 通过特定的策略逐渐减小gap。 经过研究gap每次除三效果最好但是为了避免gap小于1于是在每次除三后再加上1这样就是一种gap的取值策略。
void ShellSort(vectorint nums)
{int n nums.size();int gap n;while (gap 1){gap gap / 3 1;//....}
} 希尔排序的实现 void ShellSort(vectorint nums)
{int n nums.size();int gap n;while (gap 1){gap gap / 3 1;for (int j 0; j gap; j){for (int i j; i n - gap; i gap){int end i;int tem nums[end gap];while (end 0){if (tem nums[end]){nums[end gap] nums[end];end - gap;}elsebreak;}nums[end gap] tem;}}}
} 完~
未经作者同意禁止转载
