昆明网站排名优化费用,dw网页设计期末作业源代码,标智客logo在线设计生成器免费,wordpress 图片上传失败#xff08;#xff09;标题#xff1a;[数据结构] 归并排序快速排序 及非递归实现
水墨不写bug #xff08;图片来源于网络#xff09; 目录
(一)快速排序
类比递归谋划非递归
快速排序的非递归实现#xff1a;
#xff08;二#xff09;归并排序
归…标题[数据结构] 归并排序快速排序 及非递归实现
水墨不写bug 图片来源于网络 目录
(一)快速排序
类比递归谋划非递归
快速排序的非递归实现
二归并排序
归并排序的递归实现
归并排序的非递归
细节处理
归并排序的非递归实现 正文开始
(一)快速排序 快速排序一般通过递归来实现但是递归也有递归的劣势当递归程度太深会导致栈溢出的问题我们在前面的分享中已经讲解了快速排序的递归实现这里不再赘述为了便于讲解直接给出快速排序的递归实现 int GetRandomKey(vectorint nums, int l, int r)
{return nums[rand() % (r - l 1) l];
}
void QuickSort(vectorint nums,int l,int r)
{//递归出口if (l r)return;int key GetRandomKey(nums,l,r);int left l - 1, right r 1, cur l;while (cur right){if (nums[cur] key)swap(nums[cur], nums[left]);else if (nums[cur] key)cur;elseswap(nums[--right],nums[cur]);}QuickSort(nums, l, left);QuickSort(nums, right, r);
}这里给出的快速排序的递归实现是比较完备的优化过的快排它解决了 1、key选取不合适导致的分区不平衡的问题。 2、key在数据中重复大量出现的问题。 递归的过程 其实通过观察快排的过程我们会发现之所以在传入参数的时候必须传入左右区间是因为我们在快排的内部过程中并不确定需要对哪一个区间的数据 进行排序。 随着递归的进行函数栈帧逐层开辟每一层函数栈帧中都存有需要排序的区间的边界值。 每一个函数栈帧都有一个 左区间端点值 l 右区间端点值 r 递归是在栈区进行的我们既然需要避免计算机自己的栈区溢出那么我们为什么不自己模拟一个栈呢 递归原理 通过模拟一个栈来协助存储左右区间端点值以此来达到让快排正常进行的目的。 因此重要的是需要对自己实现的栈精确的控制。 类比递归谋划非递归 什么时候递归停止 当所有递归都返回的时候递归停止——当模拟实现的栈为空的时候停止迭代 递归出口的条件设置 当递归区间不存在的时候递归通过return返回到上一层——当递归区间不存在的时候直接进入下一次迭代这里就用到了continue 如何准确的控制接收的左右区间的端点值 通过栈来模拟需要注意栈的后进先出的特点push的顺序和pop的顺序是相反的比如先push左端点再push右端点在top的时候先取得的是右端点值pop后top再取得的是左端点值。 快速排序的非递归实现
void QuickSort_NoR(vectorint nums,int l1,int r1)
{stackint st;st.push(l1);st.push(r1);while (!st.empty()){int r st.top();st.pop();int l st.top();st.pop();if (l r)continue;int left l - 1, right r 1, cur l;int key GetRandomKey(nums, l, r);while (cur right){if (nums[cur] key)swap(nums[cur], nums[left]);else if (nums[cur] key)cur;elseswap(nums[--right], nums[cur]);}st.push(right);st.push(r);st.push(l);st.push(left);}
} 二归并排序 归并是一种算法当归并应用在排序中实际上的操作就是将两个有序数组合并为一个有序数组的过程。 归并排序一般通过非递归实现其核心思想是分治但是递归的缺点明显本文上半部分也说明了递归的缺点因此非递归实现归并有很大意义。 时间复杂度O(N*logN) 空间复杂度O(N) 稳定性稳定 归并的缺点需要O(N)的空间复杂度 我们在实现归并排序的时候需要注意的是 1、需要一个N个空间的数组辅助进行排序由于递归次数很多在递归过程中创建数组代价太大所以我们在全局来创建一个数组tem作为辅助不仅在每一层递归中都可使用也节省了资源。 2、归并的主要过程通过三目运算符处的逻辑实现。 3、三目运算符之后需要再将没有遍历到末尾的数据继续添加到tem末尾即可此时归并结束。 4、最终不要忘了将tem内的数据拷贝回原数组。 归并排序的递归实现 vectorint tem(0);
void MergeSort(vectorint nums,int l,int r)
{if (l r)return;int mid (r - l) / 2 l;int cur1 l, cur2 mid 1;MergeSort(nums, l, mid);MergeSort(nums, mid 1, r);int i 0;while (cur1 mid cur2 r){tem[i] nums[cur1] nums[cur2] ?nums[cur1] : nums[cur2];}while (cur1 mid)tem[i] nums[cur1];while (cur2 r)tem[i] nums[cur2];for (int j l; j r;j){nums[j] tem[j - l];}
}
int main()
{vectorint nums { 99,0,7,5,44,3,78,653,90,81 };tem.resize(nums.size());Print(nums);MergeSort(nums,0,nums.size()-1);Print(nums);return 0;
} 归并排序的非递归 想要实现归并的非递归在整体上需要换一种思路。 在局部上归并的逻辑仍然是与递归是一致的 我们在思考的时候要将问题逐渐拆成一个一个的小问题 1、归并过程 将[begin1,end1],[begin2,end2]归并为一个有序的数组算法本质和步骤和非递归的实现方法完全一致 2、非递归省去了进入递归的过程而是直接将数组分为多份每一份有gap个 gap开始取1表示一个数字就是一个区间这个步骤是数组本身就满足的 gap每次*2表示区间扩大的过程这样一来gap逐渐扩大就在思路上完成了归并 通过分析你也知道了最重要的是对区间的左右端点的控制也就是需要控制好区间的偏移和越界问题。 细节处理 1区间的偏移 通过一个循环循环变量为k两个区间的开始位置是由k来决定的用k来控制区间的偏移由于每次是归并两个数组所以每次归并完成后k2*gap: 演示以gap2为例 偏移后k2*gap 2区间的越界 我们上图举的例子是一个特殊情况数组元素个数刚好够归并需要的元素如果元素有9个而不是8个这就需要考虑区间的越界问题了。 当数组的长度更加一般时会出现区间的越界问题对于每一个区间端点 begin1由k决定k n,所以不可能越界 end1begin1gap-1有可能越界如果越界数组个数只有一个则不再归并。 begin2begin1gap可能越界如果越界数组个数只有一个则不再归并。 end2begin12*gap-1可能越界如果越界数组个数有两个修正end2的位置后再归并。 归并排序的非递归实现
void MergeSort_NoR(vectorint nums, int l, int r)
{int n nums.size();int gap 1;while (gap n){for (int k 0; k n; k 2*gap){// 对两组进行归并 [beign1,end1] [begin2,end2] // 组内宽度gap int begin1 k, end1 begin1 gap - 1;int begin2 end1 1, end2 begin2 gap - 1;if (end1 n || begin2 n)break;if (end2 n)end2 n-1;int i k;while (begin1 end1 begin2 end2)tem[i] nums[begin1] nums[begin2] ?nums[begin1] : nums[begin2];while (begin1 end1) tem[i] nums[begin1];while (begin2 end2) tem[i] nums[begin2];for (int j k; j end2; j)nums[j] tem[j];}gap * 2;}
}完~
未经作者同意禁止转载
