西维科技做网站怎么样网络规划与设计就业前景

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

西维科技做网站怎么样,网络规划与设计就业前景,有高并发 高访问量网站开发,玩具电子商务网站建设论文目录 快速排序 一. 快速排序递归的实现方法

1. 左右指针法 步骤思路 为什么要让end先走#xff1f;
2. 挖坑法 步骤思路
3. 前后指针法 步骤思路 二. 快速排序的时间和空间复杂度
4. 时间复杂度
5. 空间复杂度 三. 快速排序的优化方法
6. 三数取中优化
7. 小区…目录 快速排序 一. 快速排序递归的实现方法
8. 左右指针法 步骤思路 为什么要让end先走
9. 挖坑法 步骤思路
10. 前后指针法 步骤思路 二. 快速排序的时间和空间复杂度
11. 时间复杂度
12. 空间复杂度 三. 快速排序的优化方法
13. 三数取中优化
14. 小区间优化 四. 使用栈来实现非递归快排 步骤思路 归并排序 ​编辑 一. 归并排序的递归实现 步骤思路 二. 时间复杂度与空间复杂度
15. 时间复杂度
16. 空间复杂度 三. 非递归实现归并排序 步骤思路 排序算法的稳定性 快速排序 一. 快速排序递归的实现方法
17. 左右指针法 步骤思路 (假设排升序)将数组a最左边的下标用begin记录下来最右边用end记录下来定义一个key为begin或end (假设key定义为begin)end先向左查找找到a[key]的数停下begin再向右查找找到a[key]的值停下此时将begin指向的值与end指向的值交换以此类推直到end的值begin将此时的a[key]与begin与end相遇坐标的值交换我们发现此时的a[key]左边的值都比其小右边的值都比其大那就说明key所指向的值在数组中已经排好位置了 如以下代码即完成了单趟 int key left;int begin left, end right;while (begin end){while (a[end] a[key] begin end){end–;}while (a[begin] a[key] begin end){begin;}Swap(a[begin], a[end]);}Swap(a[key], a[begin]); 我们在end和begin寻找比a[key]大或小的值的时候不要忘记也要判断循环成立的条件 既然key已经在数组排好位置我们接下来递归就不需要加上key了只需要递归key的左右区间即可直到递归的区间左边与右边相等即只有一个数 完整代码如下 void QuickSort1(int* a, int left,int right) {if (left right)return;int mid GetMid(a, left, right);Swap(a[mid], a[left]);int key left;int begin left, end right;while (begin end){while (a[end] a[key] begin end){end–;}while (a[begin] a[key] begin end){begin;}Swap(a[begin], a[end]);}Swap(a[key], a[begin]);QuickSort1(a, left, begin - 1);QuickSort1(a, begin 1, right); } 为什么要让end先走 左边做key右边先走可以保证相遇位置比key小 相遇场景分析 begin遇endend先走停下来end停下条件是遇到比key小的值,end停下来的位置一定比key小,begin没有找到大的遇到end停下了end遇begin:end先走找小没有找到比key更小的直接跟begin相遇了。begin停留的位置是上一轮交换的位置(即上一轮交换把比key小的值换到begin的位置了 同样道理让右边做key左边先走可以保证相遇位置比key要大   2. 挖坑法 步骤思路 (假设排升序给数组a)将最左边的值定义key存储起来最左边的下标用bigen记录最右边的下标用end记录定义pivot记录为最左边的下标即将最左边视为坑位 然后end向左寻找比key小的值放到pivot所指向的位置即坑位中并将这个地方(end所找到的)视作新的坑(更新pivot的值)。 begin向右寻找比key大的值放到坑位中并将这个地方视作新的坑(更新pivot的值) 重复以上步骤直到endbegin 然后将key填进pivot中再通过递归即可完成排序 由于与左右指针法类似就不写单趟直接上完整代码 void QuickSort2(int* a, int left, int right) {if (left right)return;int key a[left];int begin left, end right;int pivot left;while (begin end){while (a[end] key begin end){end–;}a[pivot]a[end];pivot end;while (a[begin] key begin end){begin;}a[pivot] a[begin];pivot begin;}a[pivot] key;QuickSort2(a, left, pivot - 1);QuickSort2(a, pivot 1, right); }
18. 前后指针法 步骤思路 (假设排升序)定义key为数组最左边的下标并定义prevkey与afterkey1 after在找到比key指向的值小的值时prev并将after指向的值与现在的prev(即prev后的值)交换 以此往复直到after数组的值 然后将prev所指向的值与key所指向的值交换 代码如下 我们要注意当prev后的值after就会发生与自身交换 完成一次后效果依然是a[key]左区间的值比其小右区间的值比其大 int key left;int prev left, after left 1;while (afterright){while (a[after] a[key]prev!after){Swap(a[prev], a[after]);}after;}Swap(a[prev], a[key]); 递归是和上面两种方法同样的道理 完整代码如下 void QuickSort3(int* a,int left,int right) {if (left right)return;int key left;int prev left, after left 1;while (afterright){while (a[after] a[key]prev!after){Swap(a[prev], a[after]);}after;}Swap(a[prev], a[key]);QuickSort3(a, left, prev - 1);QuickSort3(a, prev 1, right); } 二. 快速排序的时间和空间复杂度
19. 时间复杂度 ①最好情况 每次的划分都使得划分后的子序列长度大致相等一般在数据已经部分有序或者随机分布的情况下发生。此时时间复杂度为O(Nlog₂N) ②最坏情况 在待排序序列有序的情况下每一次划分的两个区间都有一个为0此时快速排序的时间复杂度退化为O(N²) ③平均情况 实际应用中快速排序的平均情况大概会接近于最好情况因为待排序序列通常不是有序的我们还可以通过三数取中来优化减少最坏情况的可能性所以快速排序的时间复杂度为O(Nlog₂N)
20. 空间复杂度 由于需要递归调用相当于求递归树的深度 ①最坏情况 当数组接近有序时递归深度很深空间复杂度为O(N) ②最好情况 当数组无序时递归树基本相当与完全二叉树空间复杂度为O(log₂N) ③平均情况 实际应用中平均情况大概会接近最好情况同样可以用三数取中优化 所以快速排序空间复杂的为O(log₂N) 三. 快速排序的优化方法
21. 三数取中优化 为了让每次左右区间长度接近我们可以使用三数取中即最左边最右边与中间的值取不大也不小的一个值并返回 int GetMid(int* a, int left, int right) {int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right])return mid;else if (a[left] a[right])//上面if条件不成立可得a[right]a[mid]return right;else//又可得 a[left] a[right]return left;}else//a[left]a[mid]{if (a[mid] a[right])return mid;else if (a[left] a[right])//上面if条件不成立可得a[right]a[mid]return left;else//又可得 a[left] a[right]return right;}}将返回值接收并将其指向位置与最左边的值交换代码如下 if (left right)return;int mid GetMid(a, left, right);Swap(a[mid], a[left]);int key left;
22. 小区间优化 当快速排序要排的数据很长时越递归到后面区间越小递归的层数越多我们可以考虑当要递归区间小于10的时候用别的排序来代替这样就可以省去80%到90%的递归 代码如下 void QuickSort1(int* a, int left,int right) {if ( (right-left1)10)//小区间优化{InsertSort(aleft, right - left 1);//aleft 有可能是后半段区间//减少递归层数}else{if (left right)return;int mid GetMid(a, left, right);Swap(a[mid], a[left]);int key left;int begin left, end right;while (begin end){while (a[end] a[key] begin end){end–;}while (a[begin] a[key] begin end){begin;}Swap(a[begin], a[end]);}Swap(a[key], a[begin]);QuickSort1(a, left, begin - 1);QuickSort1(a, begin 1, right);} } 四. 使用栈来实现非递归快排 栈的实现可以看一下我以前的博客 栈的实现详解-CSDN博客 步骤思路 初始化栈后将数组的最右边与最左边分别放入栈(即将一个区间放入栈中) 进入循环(当栈为空时循环结束)用begin和begin1接收栈顶端的值再删除栈的值再用end和end1接收栈顶端的值再删除栈的值使用左右指针法(挖坑法前后指针法皆可)(用begin与end来寻找值begin1与end1不变)进行一趟排序 如果right1begin1 就往栈里存 right1(当前排序区间的最右边) 和 begin1 反之不存 如果left1begin-1 就往栈里存  begin-1 和 left1(当前排序区间的最左边)  反之不存 最后不要忘记销毁栈 代码如下 void StackQuickSort(int* a, int left, int right) {ST s;StackInit(s);StackPush(s, right);StackPush(s, left);while (!StackEmpty(s)){int begin StackTop(s);int left1 begin;StackPop(s);int end StackTop(s);int right1 end;StackPop(s);int key begin;//int mid GetMid(a, begin, end);//Swap(a[mid], a[begin]);while (begin end){while (a[end] a[key] begin end){end–;}while (a[begin] a[key] begin end){begin;}Swap(a[begin], a[end]);}Swap(a[key], a[begin]);if(right1begin1){StackPush(s,right1);StackPush(s, begin 1);}if(left1begin-1){StackPush(s, begin - 1);StackPush(s, left1);}}StackDestroy(s); } 归并排序 一. 归并排序的递归实现 步骤思路 malloc一个临时数组进入子函数(创建子函数递归会更方便)进行递归子函数利用分治思想一直递归直到leftright 开始执行下面操作 k赋初值为当前区间最左边begin1 end1来记录左数组最左边和最右边定义begin2 end2 来记录右数组的最左边和最右边将两个数组从头比较较小的赋值给临时数组直到有一方赋完值再将没赋完值的数组给临时数组赋值。最后给要排序数组left到right赋值为临时数组left到right 代码如下 //递归 void _MergeSort(int* a,int* tmp, int left, int right) {if(leftright){return;}int mid (left right) / 2;//如果[left,mid][mid1,right]有序就可以归并了_MergeSort(a,tmp, left, mid);_MergeSort(a,tmp, mid 1, right);int begin1 left;int end1 mid;int begin2 mid 1;int end2 right;int kleft;while (begin1 end1begin2end2){if(a[begin1]a[begin2]){tmp[k] a[begin1];}else{tmp[k] a[begin2];}}while (begin1 end1){tmp[k] a[begin1];}while (begin2 end2){ tmp[k] a[begin2];}for (int i left; i right; i){a[i] tmp[i];}}void MergeSort(int* a, int n) {int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}//_MergeSort(a, tmp, 0, n - 1);_MergeSort2(a,tmp, n);free(tmp); tmp NULL; } 二. 时间复杂度与空间复杂度
23. 时间复杂度 归并排序的时间复杂度是稳定的不受输入数组的初始顺序影响 将数组分成两个子数组的时间复杂度为O(1)递归对子数组进行排序假设每个子数组长度为n 则两个子数组排序的总时间复杂度为O(NlogN)将两个有序数组合并为一个有序数组时间复杂度为O(N)所以归并排序时间复杂度为O(NlogN)
24. 空间复杂度 调用栈所需要的额外空间为O(logN)因为我们需要一个额外数组来存储数据所以又额外消耗O(N)的空间我们将较小的O(logN)忽略可以得到归并排序的空间复杂度为O(N) 三. 非递归实现归并排序 步骤思路 开辟动态空间后定义一个数gap1来控制区间(gap相当于每组数据个数)(每一次gap*2使每次区间扩大)gap数组长度 设计一个for循环igap*2 每次分两组[i][igap-1]和[igap][i2gap-1]  (i每次正好跳过这些数据) 将两个区间的值比较放入新开辟的数组再拷贝到原数组 代码如下 //非递归 void _MergeSort2(int a,int* tmp,int n) {int gap 1;while(gapn){for (int i 0; i n; i 2 * gap){int begin1 i;int end1 i gap - 1;;int begin2 i gap;int end2 i 2 * gap - 1;int k i;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[k] a[begin1];}else{tmp[k] a[begin2];}}while (begin1 end1){tmp[k] a[begin1];}while (begin2 end2){tmp[k] a[begin2];}//memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));for (int j i; j k; j){a[j] tmp[j];}}gap * 2;} }但是我们发现这样如果会发生越界的现象 一共三种可能 1. [begin1,end1][begin2,end2]  end2越界 2. [begin1,end1][begin2,end2]  begin2end2越界 3. [begin1,end1][begin2,end2]  end1begin2end2越界 第2,3种我们可以直接不递归了因为后面区间的不存在前面区间的在上一次已经递归好了 第一种呢我们需要把区间(即end)给修正一下 修正代码如下 //非递归 void _MergeSort2(int* a,int* tmp,int n) {int gap 1;while(gapn){for (int i 0; i n; i 2 * gap){int begin1 i;int end1 i gap - 1;;int begin2 i gap;int end2 i 2 * gap - 1;int k i;if (begin2 n)//第二种情况,第二组不存在不需要归并break;if (end2 n)//第一种情况需要修正一下end2 n - 1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[k] a[begin1];}else{tmp[k] a[begin2];}}while (begin1 end1){tmp[k] a[begin1];}while (begin2 end2){tmp[k] a[begin2];}//memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));for (int j i; j k; j){a[j] tmp[j];}}gap * 2;} }排序算法的稳定性 假定在待排序的记录序列中存在多个具有相同关键字的记录若经过排序这些记录的相对次序保持不变 即原序列中 r[i]r[j],且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]前则称这种排序算法是稳定的否则是不稳定的 冒泡选择稳定选择排序不稳定***只会考虑自身假如找到最小值1下标为3将其与下标为0(假设此处为6)处交换若下标为1处也是6就改变了直接插入排序稳定希尔排序不稳定(分组)预排序时相同的值可能分到不同的组堆排序不稳定建堆时可能就乱了归并排序稳定当两个数相等让第一个下来就是稳定的可以控制快速排序不稳定end先找到 j 和begin交换了在找到 i 和bigin交换显然改变了 这篇文章就到这里了感谢大家阅读 (๑′ᴗ‵๑) Lᵒᵛᵉᵧₒᵤ❤