做一个网站得做多少个页面,免费有趣的网址,1688阿里巴巴国际站首页,做网站需要哪些技术人员插入排序#xff0c;是一种简单直观的排序算法#xff0c;工作原理是将一个记录插入到已经排好序的有序表中#xff0c;从而形成一个新的、记录数增1的有序表。在实现过程中#xff0c;它使用双层循环#xff0c;外层循环对除了第一个元素之外的所有元素#xff0c;内层循… 插入排序是一种简单直观的排序算法工作原理是将一个记录插入到已经排好序的有序表中从而形成一个新的、记录数增1的有序表。在实现过程中它使用双层循环外层循环对除了第一个元素之外的所有元素内层循环对当前元素和已排序序列中的元素进行比较并找到正确的位置来插入。 实际在我们平时玩的扑克牌游戏中就用到了插入排序的思想 一、直接插入排序 当插入第i(i1)个元素时前面的array[0],array[1]..array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2]..的排序码顺序进行比较找到插入位置即将arrayl]插人原来位置上的元素顺序后移。 具体实现代码如下
void InsertSort(int* a, int n)
{for (size_t 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];}else{break;}--end;}a[end 1] tmp;}
}void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void TestInsertSort()
{int a[] { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestInsertSort();return 0;核心代码解析
外层循环遍历数组中的每个元素从第二个元素开始下标为1。内层循环从当前元素的下一个元素开始向前遍历直到遇到一个比当前元素小的元素或者到达数组的开头。在内层循环中将当前元素与找到的较小元素交换位置。当内层循环结束时将当前元素插入到正确的位置。
实现结果如下 直接插入排序的特性总结 1.元素集合越接近有序直接插入排序算法的时间效率越高 2.时间复杂度:O(N个2) 3.空间复杂度:O(1)它是一种稳定的排序算法 4.稳定性:稳定 二、希尔排序 希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。 具体实现代码如下
void ShellSort(int* a, int n)
{int gap n;while (gap 1){gap gap / 3 1;for (int i 0; i n - 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;}}
}void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void TestShellSort()
{int a[] { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };ShellSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestShellSort();return 0;
}
核心代码解析
定义一个函数ShellSort接收一个整型指针a和整数n作为参数其中a指向待排序的数组n表示数组的长度。初始化间隔gap为n。当gap大于1时执行以下操作 a. 更新gap的值将其除以3并加1。 b. 使用for循环遍历数组从0到n-gap。 i. 初始化end为当前下标i。 ii. 将a[endgap]的值赋给临时变量tmp。 iii. 使用while循环当end大于等于0时执行以下操作 1) 如果tmp小于a[end]则将a[end]的值赋给a[endgap]并将end减去gap。 2) 否则跳出while循环。 iv. 将tmp的值赋给a[endgap]。当gap不再大于1时排序完成。 实现结果如下 希尔排序的特性总结 1.希尔排序是对直接插入排序的优化。 2.当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比. 3.希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的希尔排序的时间复杂度都不固定 4.稳定性不稳定
引用 《数据结构(C语言版)》--- 严蔚敏 《数据结构-用面相对象方法与C描述》--- 殷人昆 结语插入排序的相关分享到这里就结束了希望对大家的学习会有帮助如果大家有什么问题或者不同的见解欢迎大家的留言~~~
