物流企业网站,成都在哪建设网站,wordpress中国优化,网站网页设计心得#x1f4f7; 江池俊#xff1a; 个人主页 #x1f525;个人专栏#xff1a; ✅数据结构冒险记 ✅C语言进阶之路 #x1f305; 有航道的人#xff0c;再渺小也不会迷途。 文章目录 一、排序的概念二、直接插入排序2.1 基本思想2.2 适用说明2.3 过程图示2.4 代码实现2.… 江池俊 个人主页 个人专栏 ✅数据结构冒险记 ✅C语言进阶之路 有航道的人再渺小也不会迷途。 文章目录 一、排序的概念二、直接插入排序2.1 基本思想2.2 适用说明2.3 过程图示2.4 代码实现2.5 直接插入排序特性总结 三、希尔排序缩小增量排序3.1 算法步骤3.2 代码实现3.3 希尔排序的特性总结 一、排序的概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。内部排序数据元素全部放在内存中的排序。外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 二、直接插入排序
2.1 基本思想
插入排序一般也被称为直接插入排序。 对于少量元素的排序它是一个有效的算法。
直接插入排序是一种简单的插入排序法其基本思想是
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。
实际中我们玩扑克牌时就用了插入排序的思想
2.2 适用说明
插入排序的平均时间复杂度是 O(n^2)空间复杂度为常数阶 O(1)具体时间复杂度和数组的有序性是有关联的。
插入排序中当待排序数组是有序时是最优的情况只需当前数跟前一个数比较一下就可以了这时一共需要比较 N-1 次时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的此时需要比较次数最多最坏的情况是 O(n^2)。
2.3 过程图示 假设前面 n-1(其中 n2)个数已经是排好顺序的现将第 n 个数插到前面已经排好的序列中然后找到合适自己的位置使得插入第 n 个数的这个序列也是排好顺序的。 按照此法对所有元素进行插入直到整个序列排为有序的过程称为插入排序。
从小到大的插入排序整个过程如图示
第一轮从第二位置的 6 开始比较比前面 7 小交换位置。 第二轮第三位置的 9 比前一位置的 7 大无需交换位置。 第三轮第四位置的 3 比前一位置的 9 小交换位置依次往前比较。 第四轮第五位置的 1 比前一位置的 9 小交换位置再依次往前比较。 …
就这样依次比较到最后一个元素。
最终效果
2.4 代码实现
// 直接插入排序
// 时间复杂度O(N^2) 逆序
// 最好的情况O(N) 顺序有序
void InsertSort(int* a, int n)
{// [0, end] end1for (int i 0; i n - 1; i){int end i;int temp a[end 1]; while (end 0) {if (temp a[end]){ a[end 1] a[end]; --end; }else{break;}}a[end 1] temp; }
}void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void TestInsertSort()
{int a[] { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestInsertSort();return 0;
}2.5 直接插入排序特性总结
元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定 三、希尔排序缩小增量排序
希尔排序也称缩小增量排序算法是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的
插入排序在对几乎已经排好序的数据操作时效率高即可以达到线性排序的效率但插入排序一般来说是低效的因为插入排序每次只能将数据移动一位
希尔排序的基本思想是首先选择一个整数作为增量gap将待排序序列分成若干个子序列每个子序列的元素之间距离为增量。然后对每个子序列进行插入排序。接下来逐渐减小增量重复上述分组和排序的过程。当增量减小到 1 时就是直接插入排序所有记录都在同一组内排好序。 3.1 算法步骤
希尔排序的算法步骤可以分为以下两步
预排序这一步的目的是通过分组和子序列排序使整个数组接近有序。 选择一个初始的增量gap。将数组分成若干个子数组每个子数组的元素之间的距离为gap。对每个子数组进行直接插入排序。随着增量的减小子数组之间的距离会逐渐缩短。 直接插入排序当增量减至 1 时对整个数组进行直接插入排序使数组完全有序。
希尔排序的时间复杂度与初始增量gap的选择和减小策略有关。选择合适的增量序列可以使得希尔排序的性能接近于最佳可能的线性时间复杂度。当前gap的减小策略以gap gap/3 1较好其它减小策略如gap gap/2 也可行但唯一一点就是要保证最后gap的值最终能够减小到 1。
3.2 代码实现 希尔排序
//void ShellSort(int* a, int n)
//{
// int gap n;
//
// // gap 1时是预排序目的让数组接近有序
// // gap 1是直接插入排序目的是让数组有序
// while (gap 1)
// {
// //gap gap / 2;
// gap gap / 3 1;
// // 一组一组排
// for (int j 0; j gap; j)
// {
// for (int i j; i n - gap; i gap)
// {
// int end i;
// int temp a[end gap];
// while (end 0)
// {
// if (temp a[end])
// {
// a[end gap] a[end];
// end - gap;
// }
// else
// {
// break;
// }
// }
// a[end gap] temp;
// }
// }
// }
//}// 希尔排序优化为多组并排减少一层循环关键在于i的变化
// O(N^1.3)
void ShellSort(int* a, int n)
{int gap n;// gap 1时是预排序目的让数组接近有序// gap 1是直接插入排序目的是让数组有序while (gap 1){// 保证最后gap的结果为1//gap gap / 2;gap gap / 3 1;// 多组并排for (int i 0; i n - gap; i){int end i; int temp a[end gap]; while (end 0){if (temp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] temp;}}
}void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void TestShellSort()
{int a[] { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };ShellSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestShellSort();return 0;
}3.3 希尔排序的特性总结
希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样进行直接插入排序就会很快。这样整体而言可以达到优化的效果。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在许多书中给出的希尔排序的时间复杂度都不固定 《数据结构(C语言版)》— 严蔚敏 《数据结构-用面相对象方法与C描述》— 殷人昆 稳定性不稳定因为在分组时无法保证相同的值被分在同一组所以在与排序时有可能发生相同的值对应位置的变化。 【八大排序】系列正在火热跟新中大家敬请期待
