做网站和做app的区别网站建设电商考试

做网站和做app的区别,网站建设电商考试,站长工具seo,wordpress输出文章目录 直接插入排序和希尔排序 直接插入排序 ​编辑 单趟 全过程 希尔排序 简单版本希尔排序 完整版希尔排序 选择排序 算法简介 代码实现 直接插入排序和希尔排序 直接插入排序实际上可以视作是希尔排序的组件#xff0c;所以我这里将直接插入排序和希尔排序放到一…目录直接插入排序和希尔排序直接插入排序​编辑单趟全过程希尔排序简单版本希尔排序完整版希尔排序选择排序算法简介代码实现直接插入排序和希尔排序直接插入排序实际上可以视作是希尔排序的组件所以我这里将直接插入排序和希尔排序放到一起了直接插入排序下面是直接插入排序的升序例子我们可以看到直接插入排序就是将一个值“拿出来”将他和他将要插入的值的前一个值依次对比如果拿出来的值小于该值就将拿出来的值插入到前面比较过的位置此时break如果拿出来的值大于该值就将对比后的值向后挪继续向前遍历单趟void InsertSort(int* arr, int n) { int end;//按下不表芝士拿出来的值的上一个值的下标 int temp arr[end 1]; while (end 0) { //当arr[end]大于temp是继续遍历 if (arr[end] temp) { arr[end 1] arr[end]; end--; } else { break; } } arr[end 1] temp; }这里我将最后插入做了统一处理当在end0时找到了合适的插入位置此时end1位置上的数已经移动到了上一个end1的位置上按照此时的位置就是end2,相当于是此时end1上的值是无效的此时我们将temp赋值给arr[end1]当在end0的范围内都没有找到合适得插入位置此时end-1(刚刚跳出循环)end1正好是0没有越界也符合实际此时temp是最小的插到最前面。全过程void InsertSort(int* arr, int n) { for (int begin 0; begin n - 1; begin) { int end begin; int temp arr[end 1]; while (end 0) { //当arr[end]大于temp是继续遍历 if (arr[end] temp) { arr[end 1] arr[end]; //这一步是挪动arr中的值 end--; } else { break; } } arr[end 1] temp; //这里将所有的情况统一处理并处理了end -1的边界情况 } }这里相当于是每次都对begin1(也是end1)的数据进行排序所以for循环是这样写的for (int begin 0; begin n - 1; begin)这里的直接插入排序实际上改几下就是希尔排序希尔排序希尔排序Shell Sort全称“缩小增量排序”Diminishing Increment Sort是插入排序的一种更高效的改进版本直接插入排序在碰到全是逆序的数据使会变得非常的坑这时希尔排序就通过将数据大踏步的向后调整的预排序使数据更趋向于有序从而大大减少了计算量希尔排序的本质是分组。它不再把数组看作一个整体而是根据一个“增量”gap将数组分割成若干个子序列这个过程中所有的值都被遍历了一遍。希尔排序通过让元素“跳跃式”地向最终位置移动大幅减少了数据交换和移动的次数简单版本希尔排序我们先写一个gap3的只进行一次预排序的希尔排序void ShellSort(int* arr, int n) { int gap 3; for(int i 0; i gap; i)//分组写法 { for (int begin i; begin n - gap; begin gap) { int end begin; int temp arr[end gap]; while (end i) { if (arr[end] temp) { arr[end gap] arr[end]; end--; } else { break; } } arr[end gap] temp; } } for (int begin 0; begin n - 1; begin) { int end begin; int temp arr[end 1]; while (end 0) { if (arr[end] temp) { arr[end 1] arr[end]; end--; } else { break; } } arr[end 1] temp; } }这个希尔排序只进行了一次粗排而且gap也是写死的这实际上是不够完善的对于大量的数据只进行这一次预排序显然是不够的这时我们就应该将gap写成动态的完整版希尔排序这里的gap取值也是有讲究的gap取得大一点跳得更快但是排的数据有序性较差gap取得小一点跳得更慢但是排的数据有序性较好学术界经过研究得出每次gap除3是最好的整个排序算下来的时间复杂度是O(n^1.3)void ShellSort(int* arr, int n) { int gap n / 3 1; //这里的do_while是一个小巧思当gap1时可以只进行一次排序,在首个gap do { //先使用再改变gap for (int j 0; j gap; j) { for (int i j; i n - gap; i gap) { int end i; int temp arr[end gap]; while (end j)//这里是一个边界条件我们应该将预排序视作是划分了一个新的组 { if (arr[end] temp) { arr[end gap] arr[end]; end - gap; } else { break; } } arr[end gap] temp; } } gap gap / 3 1; } while (gap 1); }选择排序算法简介选择排序是一种简单直观的排序算法。它的工作原理是在未排序序列中找到最小或最大元素将其存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小或最大元素放到已排序序列的末尾重复以上步骤直到所有元素均排序完毕代码实现void SelectSort(int* arr, int n) { int begin 0, end n - 1; while (begin end) { int max begin, min begin; for (int i begin 1; i end; i) { if (arr[max] arr[i]) { max i; } if (arr[min] arr[i]) { min i; } } Swap(arr[begin], arr[min]); if (begin max) max min; Swap(arr[end], arr[max]); begin; end--; } }这里有一步需要解释一下if (begin max) max min;这一步是为了处理beginmax的边界情况示例arr [5, 1, 4, 2, 3]第一轮循环begin 0,end 4max 0(arr[0]5是最大值)min 1(arr[1]1是最小值)如果没有这一步的话直接交换arr[begin]和arr[min]会导致max指向的值被移动后面的逻辑就错了。