电商网站建设源代码,wordpress 调查系统,建网站 铸品牌 做推广,大型广告公司网站建设文章目录 1.概念✅2.希尔排序#x1f388;3.代码实现✅3.1 直接写✨3.2 函数✨ 4.总结✅ 1.概念✅ 排序是数据处理的基本操作之一#xff0c;每次算法竞赛都很多题目用到排序。排序算法是计算机科学中基础且常用的算法#xff0c;排序后的数据更易于处理和查找。在计算机发展… 文章目录 1.概念✅2.希尔排序3.代码实现✅3.1 直接写✨3.2 函数✨ 4.总结✅ 1.概念✅ 排序是数据处理的基本操作之一每次算法竞赛都很多题目用到排序。排序算法是计算机科学中基础且常用的算法排序后的数据更易于处理和查找。在计算机发展的历程中在排序算法的研究一直深受人们重视出现了很多算法在思路、效率、应用等方面各有特色。通过学习排序算法读者可以理解不同算法的优势和局限性并根据具体情况选择最合适的算法以提高程序的性能和效率。学习排序算法还有助于培养逻辑思维和问题解决能力在解决其他类型的问题时也能够应用到类似的思维方法。
2.希尔排序 希尔排序Shell Sort是一种基于插入排序的排序算法可以看作是插入排序的改进版。它通过将数组分成若干个子数组每个子数组中的元素间隔为一个增量 gap来进行分组排序逐步缩小这个增量最后当增量为 1 时变成普通的插入排序。 以a[]{12, 54, 34, 2, 38} 中的6个数从小到大排序为例说明希尔排序的步骤 1gap 6/2 3对间距为3的数排序。共3组数的间距为3这四组数分别是{12 2}、{34, 3}、{54, 8}。分别在这3组数内部做插入排序。例如{12,2}做插入排序的结果是{34,3}。在这一轮每组内的数做插入排序时都要进入代码执行交换操作共执行3次。经过这一轮操作较大的数挪到了右边更靠近它们排序后的终止位置。如下图 2gap 3/2 1对间距为1的数排序实际上gap1的希尔排序就是基本的插入排序。不懂的看这篇文章 插入排序 假如说:a[]{12, 54, 34, 2, 38} 有8个数 当gap 4/2 2对间距为2的数排序。共有2组数的间距为2分别是{2, 8, 34, 0}、{3, 12, 34, 0}。分别做插入排序如下图 3.代码实现✅
3.1 直接写✨
#include stdio.hint main() {int arr[] {12, 11, 13, 5, 6,8}; // 原始数组int n sizeof(arr) / sizeof(arr[0]); // 数组大小int i; // 插入排序实现for ( i 1; i n; i) {int key arr[i]; // 当前待插入的元素int j i - 1;// 将大于key的元素移到右侧while (j 0 arr[j] key) {arr[j 1] arr[j];j--;}// 插入当前元素到正确的位置arr[j 1] key;}// 打印排序后的数组printf(排序过后的数组: \n);for ( i 0; i n; i) {printf(%d , arr[i]);}printf(\n);return 0;
}3.2 函数✨
#include stdio.h// 希尔排序函数
void shellSort(int arr[], int n) {int gap,i;// 确定初始增量for ( gap n / 2; gap 0; gap / 2) {// 从gap开始进行插入排序for ( i gap; i n; i) {int temp arr[i]; // 当前待排序的元素int j;// 移动大于temp的元素到gap位置for (j i; j gap arr[j - gap] temp; j - gap) {arr[j] arr[j - gap];}arr[j] temp; // 插入当前元素}}
}// 打印数组的函数
void printArray(int arr[], int n) {int i;for ( i 0; i n; i) {printf(%d , arr[i]);}printf(\n);
}int main() {int arr[] {12, 34, 54, 2, 3,8}; // 原始数组int n sizeof(arr) / sizeof(arr[0]); // 数组大小shellSort(arr, n); // 调用希尔排序函数printf(排序过后的数组: \n);printArray(arr, n); // 打印排序后的数组return 0;
}4.总结✅ 希尔排序在多大程度上改善了插入排序可以直接对比两个代码的计算量感兴趣的小伙伴自己思考一下。 根据严格的算法分析希尔排序的计算复杂度约为O(n^1.5)当n10^5时计算量约为3000万次远小于O(n^2)的100亿次。 最后概括希尔排序的思路。希尔排序是一种基于插入排序的排序算法它将一个序列分成若干个子序列对每个子序列使用插入排序然后在对整个序列使用一次插入排序。shellSort()函数使用gap对数组进行分组然后对每个子序列使用插入排序最后将整个序列使用插入排序在插入排序过程中每次将元素插到已经排好序的序列中而这个已经排好序的序列是由前面的插入排序操作得到的每次操作都相当于将元素插到一个较小的序列中因此可以更快地将元素插到正确的位置。 Perspective-takling
