首页 > 代码库 > 高速排序 归并排序的非递归版本号 备忘
高速排序 归并排序的非递归版本号 备忘
首先,归并排序,分治。递归解决小的范围。再合并两个有序的小范围数组,便得到整个有序的数组。
这是非常适合用递归来写的。至于非递归。便是从小到大。各个击破,从而使得整个数组有序。代码例如以下:
void merge(vector<int> &A, int left, int mid, int right) { int i=left,j=mid+1; vector<int> tmp(right-left+1,0); int k=0; while(i<=mid&&j<=right) { if(A[i] < A[j]) tmp[k++]=A[i++]; else tmp[k++]=A[j++]; } while(i<=mid)tmp[k++]=A[i++]; while(j<=right)tmp[k++]=A[j++]; //write to A for(int i=0;i<right-left+1;++i) { A[left+i]=tmp[i]; } } void mergeSort(vector<int> &A) { const int n=A.size(); int step=1; int left=0,right,mid; while(step< n) { left=0; while(left+step<n) { mid=left+step-1; right=mid+step; if(right>=n) right=n-1; merge(A,left,mid,right); left=right+1; } step *= 2; } }
int partition(vector<int> &A, int left, int right) { int pivot=A[right]; int i=left; for(int k=left;k<right;++k) { if (A[k] < pivot) swap(A[i++],A[k]); } swap(A[i],A[right]); return i; } void quickSort(vector<int> &A) { stack<pair<int,int> > s; const int n = A.size(); if(n <2 ) return; int left=0,right=n-1; s.push(make_pair(left, right)); while(!s.empty()) { auto cur=s.top();s.pop(); left=cur.first;right=cur.second; if(left>=right)continue; int mid=partition(A,left,right); s.push(make_pair(left, mid-1)); s.push(make_pair(mid+1, right)); } }
写习惯了这两种排序的递归版本号,此处的非递归版本号确实不是那么自然而然的,可是仅仅要记住递归的版本号一定能够使用栈来模拟递归的过程,那么我们相同能够实现非递归的版本号,此文就是一份备忘吧。
高速排序 归并排序的非递归版本号 备忘
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。