佛山建网站做网站买域名多少钱

当前位置： 首页 > news >正文

佛山建网站,做网站买域名多少钱,有没有免费看的视频,专门找事做的网站本篇博客给大家带来的是排序的知识点, 由于时间有限, 分两天来写, 上篇主要实现 前四种排序算法: 直接插入, 希尔, 选择, 堆排。 文章专栏: Java-数据结构 若有问题 评论区见 欢迎大家点赞 评论 收藏 分享 如果你不知道分享给谁,那就分享给薯条. 你们的支持是我不断创作的动力 … 本篇博客给大家带来的是排序的知识点, 由于时间有限, 分两天来写, 上篇主要实现 前四种排序算法: 直接插入, 希尔, 选择, 堆排。 文章专栏: Java-数据结构 若有问题 评论区见 欢迎大家点赞 评论 收藏 分享 如果你不知道分享给谁,那就分享给薯条. 你们的支持是我不断创作的动力 . 目录 王子公主请阅 1.排序的概念及应用 1.1 排序的概念 1.3 常见的排序算法

1. 常见排序算法的实现(默认排升序) 2.1 插入排序 2.1.1基本思想 2.1.2 直接插入排序 直接插入排序具体操作:  2.1.3 希尔排序(缩小增量排序) 2.2 选择排序 2.2.1基本思想 2.2.3 堆排序 王子公主请阅 1.排序的概念及应用 1.1 排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性 假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j] 且 r[i] 在 r[j] 之前而在排序后的序列中 r[i] 仍在 r[j] 之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序 数据元素全部放在内存中的排序。 外部排序 数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 1.3 常见的排序算法 2. 常见排序算法的实现(默认排升序) 2.1 插入排序 2.1.1基本思想 直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到 一个新的有序序列 。实际中我们玩扑克牌时就用了插入排序的思想。 如下模拟动图:  2.1.2 直接插入排序 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序 此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置 将array[i]插入原来位置上的元素顺序后移 如下图:  直接插入排序具体操作:  第一步 理清思路:  当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序 此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置 将array[i]插入原来位置上的元素顺序后移 第二步具体步骤:  1.   定义 tmp 保存 排序前 i 下标对应的值.  for(i) 为 外循环, for(j) 为  内循环 , j i -1 . 2.   遍历数组,  在内循环中,  tmp 与  array[ j ] 进行比较,, 若是 tmp 小 则  [ j 1] [ j ]; 若是 tmp 大 则 直接 break;   3.    在外循环中  将 最后 j 1 位置的值 赋为 tmp值 , [ j 1 ] tmp;   第三步  画图理解 , 一目了然 : 第四步  代码实现:  /*** 时间复杂度:* 最好情况:数据完全有序的时候 1 2 3 4 5 :O(N)* 最坏情况:数据完全逆序的时候 5 4 3 2 1 :O(N^2)* 结论: 数据越有序,排序越快, * 场景: 现在有一组基本有序的数据,那么用哪个排序好点? - 直接插入排序.* 空间复杂度: O(1)* 稳定性: 稳定的排序* 一个本身就是稳定的排序 是可以实现为不稳定的排序的* 相反 一个本身就不稳定的排序 是不可以实现为稳定的排序的.** param //直接插入排序/public static void insertSort(int[] array) {for (int i 1; i array.length; i) {int tmp array[i];int j i-1;for (; j 0; j–) {if(array[j] tmp) { // 会变成不稳定的array[j1] array[j];}else {//array[j1] tmp; 执行了一次break;}}//当j-1时,a[j1]tmp这条语句没被执行,所以再写一次array[j1] tmp; //执行了两次, 故把第一次屏蔽.}} 最后总结:  1. 元素集合越接近有序直接插入排序算法的时间效率越高 2. 时间复杂度O(N^2) 3. 空间复杂度O(1)它是一种稳定的排序算法 4. 稳定性稳定  2.1.3 希尔排序(缩小增量排序) 希尔排序本质上 就是 在对直接插入排序做优化。 第一步 了解基本思想:  先选定一个整数 gap 把待排序文件中所有记录分成多个组 此处 gap 通常都是 初始化成 gap array.length/2; 所有 距离为 gap 的记录 分 在同一组内并对每一组内的记录进行直接插入排序。 每进行一次直接插入排序 gap / 2 重复上述分组和排序的工作。当 gap   1  时所有记录在同一组内进行直接插入排序 。 第二步 画图辅助理解:  第三步 具体步骤: 具体步骤与 直接插入排序的大体相同, 将 外循环条件换成for (int i gap; i array.length; i), 外循环中 j i - gap 而不是 - 1;   同时, 内循环变成for (; j 0; j - gap) 赋值条件变为array[jgap] tmp; 最后在直接插入排序外加一层 gap / 2 的循环 就大功告成了. 第四步  代码实现:  /** 希尔排序** 时间复杂度:* n^1.3 - n^1.5* 空间复杂度: O(1)** 稳定性: 不稳定* param //shell*/public static void shellSort(int[] array) {int gap array.length;while(gap 1) {gap / 2;shell(array,gap);}//gap / 2;不用写 因为gap2或3时, gap/2 1.已经进行了直接插入排序.}private static void shell(int[] array,int gap) {for (int i gap; i array.length; i) {int tmp array[i];int j i-gap;for (; j 0; j - gap) {if(array[j] tmp) {array[jgap] array[j];}else {break;}}array[jgap] tmp;}} 最后 希尔排序的特性总结:  1. 希尔排序是对直接插入排序的优化。 2. 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。 3. 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的希尔排序的时间复杂度都不固定O(n^1.25) ~ O(1.6 * n^1.25) 4. 稳定性不稳定 2.2 选择排序 2.2.1基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 如下模拟动图:  第一步 理清思路: 在元素集合 array[ i ] ~ array[ n-1 ] 中选择关键码最 小 的数据元素 若它不是这组元素中的 第一个 元素则将它与这组元素中的最后一个第一个元素交换 在剩余的 array[ i ]  ~ array[ n-2 ] array[ i1 ]  ~  array[ n-1 ] 集合中重复上述步骤直到集合剩余 1 个元素 第二步 具体步骤:  1.  写个双层循环, for( i ) 为 外层循环,  for( j ) 为外层循环, 定义minIndex   i , j i 1; 2.   [minIndex] 与 [ j ] 比较, 当[minIndex] [ j ] 时  二者交换.  第三步  代码实现: /*** 选择排序** 时间复杂度:* 最好: O(N^2)* 最坏: O(N^2)空间复杂度:O(N)** 稳定性: 不稳定** param array/public static void selectSort(int[] array) {for (int i 0; i array.length-1; i) {int minIndex i;for (int j i1; j array.length; j) {if(array[j] array[minIndex]) {minIndex j;}}swap(array,minIndex,i);}}public static void swap(int[] array,int i,int j) {int tmp array[i];array[i] array[j];array[j] tmp;} 选择排序有 第二种写法,  反正都要遍历一遍数组, 不如把最大值和最小值都找出来, 最小的往最前放, 最大的往最后放.  第二种写法步骤:  1.  定义 left 0, right array.length-1, i left 1; minIndex maxIndex 0; 2.   while( left right )循环,  i 在循环中, 遍历数组 找到最小元素下标 和 最大元素下标, 出循环 与 minIndex 和 maxIndex 交换.   3. 出循环后 考虑一个特殊情况 , 当 left 0 下标 对应的值就是最大值时, 第二步出循环后的交换操作 将最大值交换到minIndex下标处了. 需要 再将 maxIndex 标记到最大值. 第二种写法代码实现: public static void swap(int[] array,int i,int j) {int tmp array[i];array[i] array[j];array[j] tmp;}//选择排序的第二种写法.public static void selectSort2(int[] array) {int left 0;int right array.length-1;while(left right) {int minIndex left;int maxIndex left;for (int i left; i right; i) {if(array[i] array[minIndex]) {minIndex i;}if(array[i] array[maxIndex]) {maxIndex i;}}swap(array,left,minIndex);//有一种情况是maxIndex原本就在left位置上,上面的交换将最大值交换到minIndex下标处了.导致后续的排序不正确.if(maxIndex left) {maxIndex minIndex;}swap(array,right,maxIndex);left;right–;}} 第四步 直接选择排序的特性总结: 1. 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用 2. 时间复杂度O(N^2) 3. 空间复杂度O(1) 4. 稳定性不稳定 2.2.3 堆排序 堆排序 (Heapsort) 是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 第一步  具体步骤: 1. 排升序, 建大堆 , 向下调整算法 , parent 从 (array.length - 1)/2 开始 减到 1  2. 将最后一个元素与首元素交换, 除末尾元素外, 其余元素调整成大根堆 3. 定义一个end array.length - 1; while (end 0) 循环中进行 2 步骤. 第二步  代码实现:  /*堆排序 时间复杂度:O(N)O(N*logN) 约等于 O(NlogN)** 如果都以最坏的情况来看,堆排序是目前来说最快的,希尔排序其次. 假设希尔排序为O(N^1.3) 当N越大时,logN趋于不变所以,堆排序O(NlogN)要快一些.** 空间复杂度:O(1) 稳定性:不稳定*/public static void heapSort(int[] array) {//建大堆createBigHeap(array);//O(N)int end array.length-1;//O(N*logN)while(end 0) {swap(array,0,end);shiftDown(array,0,end);end–;}}private static void createBigHeap(int[] array) {for (int parent (array.length-1-1)/2; parent 0; parent–) {shiftDown(array,parent,array.length);}}private static void shiftDown(int[] array,int parent,int end) {int child (parent*2)1;while(child end) {//保证右子树存在并且当右子树大的时候,child来到右子树的下标.if(child1 end array[child1] array[child]) {child;}if(array[child] array[parent]) {swap(array,child,parent);parent child;child parent*21;}else {//本身就是大根堆break;}}} 第三步   堆排序的特性总结: 1. 堆排序使用堆来选数效率就高了很多。 2. 时间复杂度O(N*logN) 3. 空间复杂度O(1) 4. 稳定性不稳定