连云港规划建设网站,镇江市建设工程管理处网站,专业点的网站制作公司,网站做哪些比较赚钱方法目录
前言
插入排序
直接插入排序
时空复杂度
直接插入排序的特性
希尔排序#xff08;缩小增量排序#xff09;
预排序
顺序排序
多组并排
小总结
直接插入排序
时空复杂度
希尔排序的特性 前言 字可能有点多#xff0c;但是真的理解起来真的没那么难#…目录
前言
插入排序
直接插入排序
时空复杂度
直接插入排序的特性
希尔排序缩小增量排序
预排序
顺序排序
多组并排
小总结
直接插入排序
时空复杂度
希尔排序的特性 前言 字可能有点多但是真的理解起来真的没那么难 记得一定要连起来看我把排序的实现过程拆开来讲述了 插入排序 基本思想每次将一个待排序的记录按其关键字大小插入到前面已经排好的子序列直到全部记录插入完成 分类直接插入排序、折半插入排序不再描述、希尔排序 注意事项解决排序的基本思想是先解决一次排序的内容然后再去解决整体的排序 直接插入排序
基本思想向有序数组中插入数据后使数组重新有序插入数据前数组已经有序了
实现步骤1、起初我们假设有序数组的范围为[0,end][0,end]并不是整个数组的长度只是数组中有序数组的长度end表示有序数组尾元素的下标tmp表示有序数组尾元素的下一个元素 2、判断tmp是否小于有序数组中的下标为end的元素如果小于则将下标为end的元素往后挪一位后续空间足够且均为空--end再次将此时下标为end的元素与tmp比较大于tmp则该元素也向后移动...... 3、如果tmp大于等于下标为end的元素那么证明它应该在当该元素的后面一位即下标为end1的位置break跳出循环然后进行赋值(a[end 1] tmp)
4、如果一直到最后有序数组中元素个数都大于tmp此时end的下标会变为-1跳出循环后将tmp的值放在有序数组的首元素位置即a[end 1] a[-1 1] a[0]处即可这也是为什么不在else中进行a[end1] tmp赋值的原因就是为了防止有序数组全部比较完后发现tmp需要位于有序数组首元素的位置而此时end值变为-1会导致跳出循环如果这时候赋值a[-1]是非法的倒不如和“如果中间出现了tmp大于等于下标为end的元素要跳出循环赋值的”情况放在一起 int end;
int tmp a[end 1];
while (end 0){if (tmp a[end]){a[end 1] a[end];--end;}else{break;}}
a[end 1] tmp;5、至此我们完成了将一个数据插入有序数组的过程那么我们该如何实现将整个无序数组通过直接插入排序变为有序呢答只需要一点点的改动
6、让我们为这段程序套上一层外壳
//直接插入排序
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];--end;}else{break;}}a[end 1] tmp;}}这就是完整的直接插入排序了其中InsertSort函数的两个参数int* a表示传入的无序数组int n表示整个数组的长度它与将一个数据插入有序数组的代码的区别在于外套了一层for循环以及将end赋值为i 7、for循环实现的效果是将数组中的每一个元素都遍历一遍并进行插入数组的操作i表示数组元素下标初始化i为0数组的长度为n所以数组元素下标i应该n-1即i n-1额为什么要写小于这是一个求闭区间中数字个数的数学问题(n-1) - (0) (1) n
8、将end赋值为i是为了配合外层的for循环当i0时我们将数组下标为0的元素视为一个有序数组然后接下来就是向有序数组中插入数据然后通过直接插入排序使数组重新变得有序的过程也就是我们第一个代码块中实现的效果
时空复杂度 最坏时间复杂度ON^2数组完全逆序1个无序需比较n次n个无序需比较n^2次 最好时间复杂度ON当个数为n的数组中只有一个数不满足有序 空间复杂度O1 直接插入排序的特性 1、元素集合越接近有序直接插入排序算法的时间效率越高 2、它是一种稳定的排序算法 希尔排序缩小增量排序
基本思想将待排序的序列分割成若干个子序列并对这些子序列进行插入排序每进行完一轮对子序列的插入排序就缩小它们之间的增量通过多次重复上述内容最终使整个序列变的十分的趋近于一个完整的有序序列预排序当它们之间的间隔缩小为1时再进行一次完整的直接插入排序即可将整个序列变为完整的有序序列直接插入排序 预排序 预排序有两种实现方式顺序排序和多组并排 顺序排序
实现步骤1、我们现在要做的不是将两个相邻的元素进行判断而是将下标间隔为gap的元素进行直接插入排序下图为进行一次的过程 int gap 3;
int end 0;
int tmp a[end gap];
while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}
a[end gap] tmp; 关于如何实现数字交换的解释这个过程其实很有趣首先tmp会记录每组中在后面的值当前面的值大于后面的值时前面的值会被赋值给后面的值得位置此时end也会像之前那样向前走如果初始end为0gap为3那么此时endend - gap -3 0跳出循环将存放后面值都tmp赋值给a[end gap] a[-3 3] a[0]这样就实现了交换 2、然后我们在第一次的基础上完成一轮的排序这时我们的end就得向前移动我们利用外层循环的i来实现它的移动规定在每次循环后i i gap然后令循环体中的end等于此时的i即可同时为了保证数组不会越界还需要规定i的取值不能超过n - gap因为每次循环i都会增加gap个有可能a[end]数组不越界但是a[end gap]后就数组越界了 int gap 3;
for(int i 0;in-gap;i gap)
{int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;
} 3、完成一轮后我们继续比较那些没有比较过的数再通过一层for循环控制此时内层for循环的i的值应该由j决定j每次循环后只会加一为啥要加一我真不想解释了
int gap 3;
for(int j 0;jgap;j)
{for(int i j;in-gap;i gap){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}
} 多组并排
图有点丑但是应该能理解吧~ int gap 3;
for(int i 0;in-gap;i)
{int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;
}
小总结 gap越大大的值更快的调到后面小的值可以更快的调到前面越不接近有序gap越小大和小的值跳的越慢但是越接近有序如果gap 1预排序就是插入排序 直接插入排序 通过上面的结论我们可以发现当gap1时就是预排序当gap 1时预排序就是直接插入排序且gap越接近于1排出来的队列就越有序那么我们将预排序中的gap最后经过多次的预排序后让它变为1就可以实现最总的希尔排序了gap肯定是先变为1然后进行一次直接插入排序后才会结束while循环的所以最后不需要再多写一个直接插入排序
int gap n;
while(gap 1)
{//gap gap / 2;gap gap / 3 1;for(int i 0;in-gap;i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}
} 一般情况下我们选择每次进行预排序时将gap/2以达到gap在经历多次预排序后变为1的目的gap的初始值无论是奇数还是偶数最后/2必然可以得到1但是我们更推荐令gap gap / 3 1这样可以实现更快的排序gap将更快的被变为1选择1是因为有些数比如18多次/3后会变为01可以将0变为1避免了这一问题 时空复杂度 最坏时间复杂度ON^2由于希尔排序的时间复杂度依赖于增量序列的函数这涉及数学上尚未解决的数学难题所以时间复杂度分析比较困难当n在某个特定范围时希尔排序的时间复杂度约为On^1.3最坏情况下希尔排序的时间复杂度为ON^2 最好时间复杂度 希尔排序的最好时间复杂度是有争议的因为它取决于增量序列的选择和具体实现方式。在经典的希尔排序算法中使用常见的希尔增量gap gap/2作为增量序列时最好情况下希尔排序可以达到接近O(n log n)级别的时间复杂度。这是因为较大间隔下元素会跳跃地进行比较和交换操作使得部分元素能够快速就位。 然而并没有一个通用且确定性质优良的最佳增量序列被找到。理论上存在一些特定情况下可以达到线性时间复杂度O(n) 的特殊增量序列选择方法。但在一般情况下并不能保证获得更好优化后的时间复杂度。 因此在实际应用中无法给出确切且普适可行地最佳时间复杂度定义。不同场景、不同数据集以及不同选取方式可能会导致差异结果。 需要注意在实际应用中对于大多数常见输入数据集来说即便在平均和最坏情况下希尔排序也能表现出相对较高效率并且相比于其他简单排序算法仍然具有改进之处。 空间复杂度O1 希尔排序的特性 希尔排序是对直接插入排序的优化当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在许多书中给出的希尔排序的时间复杂度都不固定 ~over~
