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

免费设计商标的网站哪里的wordpress主题比较好

news 2025/11/16 23:20:08

免费设计商标的网站,哪里的wordpress主题比较好,seo网络优化是做什么的,wordpress 简洁目录一、快速排序 (1)hoare版本 ①思路 ②过程图示 ③思考 ④代码实现 ⑤代码解释 #xff08;2#xff09;挖坑法 ①思路 ②过程图示 ③思考 ④代码实现 ⑤代码解释 #xff08;3#xff09;lomuto前后指针 ①思路 ②过程图示 ③思考 ④代码实现 ⑤代…目录一、快速排序 (1)hoare版本 ①思路 ②过程图示 ③思考 ④代码实现 ⑤代码解释 2挖坑法 ①思路 ②过程图示 ③思考 ④代码实现 ⑤代码解释 3lomuto前后指针 ①思路 ②过程图示 ③思考 ④代码实现 ⑤代码解释 4快速排序的复杂度 5非递归版本 ①代码实现 ②代码解释二、写在最后一、快速排序我们上次学到了快速排序的递归方式但是找基准值的函数_QuickSort如何实现呢 (1)hoare版本 ①思路首先创建左右指针来寻找基准值。具体步骤为一个指针从左到右找出比基准值大的数据另一个指针从右到左找出比基准值小的数据交换两者的位置进入下一次循环。 ②过程图示 1. 首先key指向第一个数据left指向第二个数据right指向最后一个数据 2.right从右向左遍历找比key小的数据3left从左向右遍历找比key大的数据7 3.将两者交换位置 4..right往后走一步left往前走一步此时两者相遇 5.right向左找比key小的数据3left向右找比key大的数据9此时left走到了right右边跳出循环 6.将right位置和key位置的数据交换位置此时right位置的数据就是我们要找的key值基准值 7.基准值为6此时基准值左侧的数据比其小右侧的数据比其大。 ③思考 1.若leftright是否继续循环场景1过程图示中的例子此处不再赘述。假设leftright时不再进行循环则此时得到基准值为6但是不满足“基准值左边都是小于它的数据基准值右边都是大于它的数据”。场景2 1. 首先key指向第一个数据left指向第二个数据right指向最后一个数据 2.right从右向左遍历找比key小的数据3left从左向右遍历找比key大的数据7 3.将两者交换位置 4.right往后走一步left往前走一步此时两者相遇 5.right找到了比基准值的数据6left找到了比基准值的数据6此时left走到了right右边跳出循环 6.将right位置和key位置的数据交换位置此时right位置的数据就是我们要找的key值基准值 7.基准值为6此时基准值左侧的数据比其小右侧的数据比其大或等于。场景3 1. 首先key指向第一个数据left指向第二个数据right指向最后一个数据 2.right从右向左遍历找比key小的数据3left从左向右遍历找比key大的数据7 3.将两者交换位置 4.right往后走一步left往前走一步此时两者相遇 5.right找到了比基准值小的数据4left找到了比基准值大的数据7此时left走到了right右边跳出循环 6.将right位置和key位置的数据交换位置此时right位置的数据就是我们要找的key值基准值 7.基准值为6此时基准值左侧的数据比其小右侧的数据比其大。通过场景1我们得出leftright仍继续循环否则在“相遇值大于key值”的情况下会出错 2.当left或right指向的值与key相等时是否进行交换我们以数组{666866}为例 1假设left或right指向的值与key相等时交换在第三次交换中left和right相遇我们不跳出循环思考1中已经解释。因此得到基准值为6。 2假设left或right指向的值与key相等时不交换 1. 首先key指向第一个数据left指向第二个数据right指向最后一个数据 2.right从右向左遍历找比key小的数据没找到且越界了此时left在right右边跳出循环 3.将right位置与key交换right和key在同一个位置相当于没交换 4.基准值为6那么没有左子树。如果left或right指向的值与key相等时不交换对于这种情况分割后数据的个数为n、n-1、n-2……并不是我们理想的类似于二叉树的分割效率较低。我们得出left或right指向的值与key相等时应该交换否则效率会降低 ④代码实现 int _QuickSort(int* arr, int begin, int end) {int left begin;int right end;int key left;left;while(left right){while(left right arr[right] arr[key]){right--;}while(left right arr[left] arr[key]){left;}if(left right){swap(arr[left], arr[right--]);}}swap(arr[right], arr[key]);return right;} ⑤代码解释首先我们让left位于第二个数据位置right位于最后一个数据的位置假设key为第一个数据。在leftright的情况下right从右向左找小于基准值的数据left从左向右找大于基准值的数据当两者均找到时交换位置不要忘记让两者继续遍历直至leftright跳出循环。 2挖坑法 ①思路创建两个指针left和right第一个数据的位置为“坑”。right从右向左找出比基准值小的数据放入“坑”中当前位置变成新的“坑”接着lleft从左向右找出比基准值大的数据放入“坑”中当前位置又变成新的“坑”。以此循环……最后将最开始“坑”位置的值放入当前位置的坑中当前位置即基准值。 ②过程图示我们以数组{612793}为例 1.首先left、hole指向第一个数据right指向最后一个数据 2.right找到比基准值小的数据3将该位置的数据放入原来的坑中该位置变成新的“坑” 3.left找到比新基准值大的数据7将该位置的数据放入原来的坑中该位置变成新的“坑” 4..right找到比新基准值的数据7将该位置的数据放入原来的坑中该位置变成新的“坑” 5.将最开始坑位置的数据放在当前坑中当前数据为基准值。 ③思考 1.若leftright是否继续循环假设leftright继续循环我们得到基准值为6不满足“基准值左边都是小于它的数据基准值右边都是大于它的数据”。因此若leftright时不继续循环 2.当left或right指向的值与key相等时是否将其设为新的“坑” 假设当left或right指向的值与key相等时将其设为新的“坑” 我们可以看到如果将其设为新的坑会降低效率。因此当left或right指向的值与key相等时不必将其设为新的“坑” ④代码实现 int _QuickSort(int* arr, int left, int right) {int mid arr[left];int hole left;int key arr[hole];while(left right){while(left right arr[right] key){right--;}arr[hole] arr[right];hole right;while(left right arr[left] key){left;}arr[hole] arr[left];hole left;}arr[hole] key;return hole; } ⑤代码解释创建两个指针left和right第一个数据的位置为“坑”。在leftright的情况下right从右向左找出比基准值小的数据放入“坑”中当前位置变成新的“坑”接着lleft从左向右找出比基准值大的数据放入“坑”中当前位置又变成新的“坑”。以此循环……最后将最开始“坑”位置的值放入当前位置的坑中返回当前位置即基准值。 3lomuto前后指针 ①思路创建前后两个指针从左向右找比基准值小的数据进行交换使小的数据都排在基准值的左边。 ②过程图示我们以数组{612793}为例 1. prev指向第一个数据cur指向第二个数据位置key指向第一个数据位置 2.此时cur指向的数据小于key但是prev的下一个数据为cur 3.让cur往后走一步 4.此时cur指向的数据也小于key但是prev的下一个数据仍为cur 5.让cur继续往后走一步 6.此时cur指向的数据小于key且prev的下一个数据不为cur我们让prev和cur位置的数据交换位置 7.cur继续往后走此时越界跳出循环 8.让key和prev位置的数据交换 9.此时prev位置的数据就是我们要找的基准值prev左边的数据都比它小prev右边的数据都比它大。 ③思考 1.当curright是否继续循环当然继续循环在这个代码中cur相当于在前面遍历需要遍历到每个元素而right位置的元素就是最后一个元素。 2.如果cur和key指向的元素相同cur和prev是否交换其实两者情况的结果是一样的。解释我们以数组{66666}为例如果相等不交换如果相等交换因此相等交不交换都是一样的要么递归左区间要么递归右区间二叉树理想下为递归左右区间。对于全部相等的数组复杂度都很高。 ④代码实现 int _QuickSort(int* arr, int left, int right) {int prev left;int cur left 1;int key left;while(cur right){if(arr[cur] arr[key] prev ! cur)//如果prev和cur相同就不进行交换{swap(arr[cur], arr[prev]);}cur;}swap(arr[key], arr[prev]);return prev; } ⑤代码解释我们先假定第一个元素是基准值用cur来递归数组的每一个元素如果小于或小于等于基准值我们设法将它放在前面即将其放在cur前面的prev位置prev是一直在的循环进行。最后将key和prev交换位置返回的prev即为基准值。 4快速排序的复杂度 1.时间复杂度O(N*logN) 2.空间复杂度O(logN)。 5非递归版本需要借助数据结构——栈。 ①代码实现 void QuickSortNonR(int* arr, int left, int right) {Stack st;//初始化StackInit(st);//入栈StackPush(st, right);StackPush(st, left);while(!StackEmpty(st)){int begin StackTop(st);StackPop(st);int end StackTop(st);StackPop(st);//新数组int key begin;int prev begin;int cur begin 1;//找基准值while(cur end){if(arr[cur] arr[key] prev ! cur){swap(arr[prev], arr[cur]);}cur;}swap(arr[key], arr[prev]);key prev;//右子树if(key 1 end){StackPush(st, end);StackPush(st, key 1);}//左子树if(begin key -1){StackPush(st, key - 1);StackPush(st, begin);}}StackDestroy(st); } ②代码解释首先非递归实现排序我们用到栈也就是说用栈来模拟递归。二、写在最后至此我们已经学习了插入排序、选择排序、交换排序还剩下最后一个归并排序我们下期见~

查看全文

http://www.dnsts.com.cn/news/159604.html