65平米装修全包多少钱,seo技术博客,wordpress的数据库在哪里,沈阳优化网站文章目录 #x1f412;个人主页#x1f3c5;算法思维框架#x1f4d6;前言#xff1a; #x1f380;插入排序 时间复杂度O(n^2)#x1f387;1. 算法步骤思想#x1f387;2.动画实现#x1f387; 3.代码实现 #x1f380;希尔排序 时间复杂度O(n*logn~n^2)希尔排序的设… 文章目录 个人主页算法思维框架前言 插入排序 时间复杂度O(n^2)1. 算法步骤思想2.动画实现 3.代码实现 希尔排序 时间复杂度O(n*logn~n^2)希尔排序的设计依据1. 算法步骤思想2、动画演示3.代码实现 个人主页 算法思维框架 前言
本篇博客主要以介绍十大排序算法中的插入排序和希尔排序有详细的图解、动画演示、良好的代码注释帮助加深对这些算法的理解进行查漏补缺~
插入排序 时间复杂度O(n^2)
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴但它的原理应该是最容易理解的了因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前 扫描找到相应位置并插入。
1. 算法步骤思想 将待排序序列第一个元素看做一个有序序列把第二个元素到最后一个元素当成是未排序序 列。 从头到尾依次扫描未排序序列将扫描到的每个元素插入有序序列的适当位置。如果待插入的元素与有序序列中的某个元素相等则将待插入元素插入到相等元素的后面。 2.动画实现 3.代码实现 public void sort(int[] arr){if(arrnull||arr.length2){return;}//思路先分为有序区间【】与无序区间【】默认数组中第一个元素在有序区间内找到待插入元素insertVal与有序区间的最后一个元素比较//如果insertVal此有序的值有序值向后覆盖往前接着比直到找到插入即可如果找到头都没有放到队首for (int i 1; i arr.length ; i) {//【无序区间】int insertValarr[i];boolean flagtrue;//判断是否找到了for (int j i-1; j 0 ; j--) {//【有序区间】if(insertValarr[j]){//向后覆盖arr[j1]arr[j];}else {//找到了arr[j1]insertVal;flagfalse;//判断已经找到了break;}}//如果找到头都没有最小的if(flag){arr[0]insertVal;}}}希尔排序 时间复杂度O(n*logn~n^2)
希尔排序Shell Sort 是一种插入排序的改进版本它通过将待排序的元素分成若干个子序列对每个子序列进行插入排序最终逐步缩小子序列的长度直到整个序列变为有序。
希尔排序的时间复杂度取决于选择的间隔序列。一般而言希尔排序的最坏时间复杂度为O(n^2)其中n是要排序的元素个数。但在实际应用中希尔排序通常表现得比这个理论上界更好它的平均时间复杂度可以在O(n log n)到O(n^2)之间。
总体而言希尔排序在某些特定情况下可以比其他简单的排序算法更加高效但在大多数情况下现代排序算法如快速排序或归并排序更常被使用因为它们具有更好的平均时间复杂度。
希尔排序的设计依据 • 插入排序在对几乎已经排好序的数据操作时效率高即可以达到线性排序的效率 • 但插入排序一般来说是低效的因为插入排序每次只能将数据移动一位 希尔排序的基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录基本有序时再对全体记录进行依次直接插入排序。 1. 算法步骤思想 选择一个增量序列 t1t2……tk其中 ti tj, tk 1 按增量序列个数 k对序列进行 k 趟排序 每趟排序根据对应的增量 ti将待排序列分割成若干长度为 m 的子序列分别对各子表进 行直接插入排序。仅增量因子为 1时整个序列作为一个表来处理表长度即为整个序列的长 度。 2、动画演示
希尔排序的动画演示
3.代码实现 public void sort(int[] arr){if(arrnull||arr.length2){return;}//思路先以arr.length/2的步长分组每一个组进行插入排序// 再以arr.length/2/2的步长分组每一个组进行插入排序直到步长为1进行整个数组的插入排序//【希尔排序的优势在于插入排序对 部分有序的序列 排序非常高效】for (int k arr.length/2; k 1; k/2) {//计算步长//i表示第一组中第二个元素【也就是无序区间的第一个元素】//里面是一个插入排序for (int j k; j arr.length ; j) {//每加一次就换一个组进行一‘步’插入排序直到数组末尾int insertValarr[j];//每个组的无序区间待插入的元素boolean flagtrue;for (int i j-k; i 0; i-k) {//因为每k个步长的元素为一组,每组有序区间的最后一个元素if(arr[i]insertVal){arr[ik]arr[i];}else {//找到待插入的位置了arr[ik]insertVal;flagfalse;break;//退出循环}}//验证极端情况待插入值是这个组中最小的if(flag){arr[j%k]insertVal;}}}}
