本文目录
- 实现递归和非递归转换的基本思想是什么
- 用C++编程 ，快速排序非递归算法
- Python实现的快速排序算法详解
- 求C语言快排非递归算法解析非递归
- 编写 快速排序的非递归算法
- C语言中快速排序法的原理及应用
- C语言课程设计：shell排序、堆排序、快速排序、归并(递归和非递归)排序5种算法效率分析！求能运行的源码！
实现递归和非递归转换的基本思想是什么
递归与非递归转换的基础知识是能够正确理解三种树的遍历方法：前序，中序和后序，第一篇就是关于这三种遍历方法的递归和非递归算法。一、为什么要学习递归与非递归的转换的实现方法? 1)并不是每一门语言都支持递归的。 2)有助于理解递归的本质。 3)有助于理解栈，树等数据结构。二、三种遍历树的递归和非递归算法 递归与非递归的转换基于以下的原理：所有的递归程序都可以用树结构表示出来。需要说明的是，这个”原理”并没有经过严格的数学证明，只是我的一个猜想，不过在至少在我遇到的例子中是适用的。学习过树结构的人都知道，有三种方法可以遍历树：前序，中序，后序。理解这三种遍历方式的递归和非递归的表达方式是能够正确实现转换的关键之处，所以我们先来谈谈这个。需要说明的是，这里以特殊的二叉树来说明，不过大多数情况下二叉树已经够用，而且理解了二叉树的遍历，其它的树遍历方式就不难了。 1)前序遍历 a)递归方式： void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法 */ { if (T) { visit(T); /* 访问当前结点 */ preorder_recursive(T-》lchild); /* 访问左子树 */ preorder_recursive(T-》rchild); /* 访问右子树 */ } }b)非递归方式 void preorder_nonrecursive(Bitree T) /* 先序遍历二叉树的非递归算法 */ { initstack(S); push(S,T); /* 根指针进栈 */ while(!stackempty(S)) { while(gettop(S,p)&&p) { /* 向左走到尽头 */ visit(p); /* 每向前走一步都访问当前结点 */ push(S,p-》lchild); } pop(S,p); if(!stackempty(S)) { /* 向右走一步 */ pop(S,p); push(S,p-》rchild); } } }2)中序遍历 a)递归方式 void inorder_recursive(Bitree T) /* 中序遍历二叉树的递归算法 */ { if (T) { inorder_recursive(T-》lchild); /* 访问左子树 */ visit(T); /* 访问当前结点 */ inorder_recursive(T-》rchild); /* 访问右子树 */ } }b)非递归方式 void inorder_nonrecursive(Bitree T) { initstack(S); /* 初始化栈 */ push(S,T); /* 根指针入栈 */ while (!stackempty(S)) { while (gettop(S, p) && p) /* 向左走到尽头 */ push(S,p-》lchild); pop(S,p); /* 空指针退栈 */ if (!stackempty(S)) { pop(S,p); visit(p); /* 访问当前结点 */ push(S,p-》rchild); /* 向右走一步 */ } } }3)后序遍历 a)递归方式 void postorder_recursive(Bitree T) /* 中序遍历二叉树的递归算法 */ { if (T) { postorder_recursive(T-》lchild); /* 访问左子树 */ postorder_recursive(T-》rchild); /* 访问右子树 */ visit(T); /* 访问当前结点 */ } }b)非递归方式 typedef struct { BTNode* ptr; enum {0,1,2} mark; } PMType; /* 有mark域的结点指针类型 */ void postorder_nonrecursive(BiTree T) /* 后续遍历二叉树的非递归算法 */ { PMType a; initstack(S); /* S的元素为PMType类型 */ push (S,{T,0}); /* 根结点入栈 */ while(!stackempty(S)) { pop(S,a); switch(a,mark) { case 0: push(S,{a.ptr，1}); /* 修改mark域 */ if(a.ptr-》lchild) push(S,{a,ptr-》lchild,0}); /* 访问左子树 */ break; case 1: push(S,{a,pt,2}); /* 修改mark域 */ if(a.ptr-》rchild) push(S,{a.ptr-》rchild,0}); /* 访问右子树 */ break; case 2: visit(a.ptr); /* 访问结点 */ } } }三、实现递归与非递归的换转原理和例子一）原理分析通常，一个函数在调用另一个函数之前，要作如下的事情：a)将实在参数，返回地址等信息传递给被调用函数保存; b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口。 从被调用函数返回调用函数之前，也要做三件事情：a)保存被调函数的计算结果;b)释放被调函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数。所有的这些，不论是变量还是地址，本质上来说都是”数据”，都是保存在系统所分配的栈中的。 ok，到这里已经解决了第一个问题：递归调用时数据都是保存在栈中的，有多少个数据需要保存就要设置多少个栈，而且最重要的一点是：控制所有这些栈的栈顶指针都是相同的，否则无法实现同步。 下面来解决第二个问题：在非递归中，程序如何知道到底要转移到哪个部分继续执行?回到上面说的树的三种遍历方式，抽象出来只有三种操作：访问当前结点，访问左子树，访问右子树。这三种操作的顺序不同，遍历方式也不同。如果我们再抽象一点，对这三种操作再进行一个概括，可以得到：a)访问当前结点：对目前的数据进行一些处理;b)访问左子树：变换当前的数据以进行下一次处理;c)访问右子树：再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式)。 下面以先序遍历来说明： void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法 */ { if (T) { visit(T); /* 访问当前结点 */ preorder_recursive(T-》lchild); /* 访问左子树 */ preorder_recursive(T-》rchild); /* 访问右子树 */ } }visit(T)这个操作就是对当前数据进行的处理， preorder_recursive(T-》lchild)就是把当前 数据变换为它的左子树，访问右子树的操作可以同样理解了。 现在回到我们提出的第二个问题：如何确定转移到哪里继续执行?关键在于一下三个地方：a)确定对当前数据的访问顺序，简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的，即确定什么是这个递归调用树的”左子树”和”右子树”c)确定这个递归调用树何时返回，即确定什么结点是这个递归调用树的”叶子结点”。 二）两个例子 好了上面的理论知识已经足够了，下面让我们看看几个例子，结合例子加深我们对问题的认识。即使上面的理论你没有完全明白，不要气馁，对事物的认识总是曲折的，多看多想你一定可以明白(事实上我也是花了两个星期的时间才弄得比较明白得)。 1)例1： f(n) = n + 1; (n 《2)= f(n 》= 2); 这个例子相对简单一些，递归程序如下： int f_recursive(int n) { int u1, u2, f; if (n 《 2) f = n + 1; else { u1 = f_recursive((int)(n/2)); u2 = f_recursive((int)(n/4)); f = u1 * u2; } return f; }下面按照我们上面说的，确定好递归调用树的结构，这一步是最重要的。首先，什么是叶子结点，我们看到当n 《 2时f = n + 1，这就是返回的语句，有人问为什么不是f = u1 * u2，这也是一个返回的语句呀?答案是：这条语句是在u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))之后 执行的，是这两条语句的父结点。 其次，什么是当前结点，由上面的分析，f = u1 * u2即是父结点 。然后，顺理成章的u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))就分别是左子树和右子树了。最后，我们可以看到，这个递归函数可以表示成后序遍历的二叉调用树。好了，树的情况分析到这里，下面来分析一下栈的情况，看看我们要把什么数据保存在栈中： 非递归程序中我们已经看到了要加入一个标志域，因此在栈中要保存这个标志域;另外，u1，u2和每次调用递归函数时的n/2和n/4参数都要保存，这样就要分别有三个栈分别保存：标志域，返回量和参数，不过我们可以做一个优化，因为在向上一层返回的时候，参数已经没有用了，而返回量也只有在向上返回时才用到，因此可以把这两个栈合为一个栈。如果对于上面的分析你没有明白，建议你根据这个递归函数写出它的递归栈的变化情况以加深理解，再次重申一点：前期对树结构和栈的分析是最重要的，如果你的程序出错，那么请返回到这一步来再次分析，最好把递归调用树和栈的变化情况都画出来，并且结合一些简单的参数来人工分析你的算法到底出错在哪里。 ok，下面给出我花了两天功夫想出来的非递归程序(再次提醒你不要气馁，大家都是这么过来的)。 代码：int f_nonrecursive(int n) { int stack，cp; /* 初始化栈和栈顶指针 */ cp = 0; stack = n; flag = 0; while (cp 》= 0) { switch(flag) { case 0: /* 访问的是根结点 */ if (stack 》= 2) { /* 左子树入栈 */ flag = 1; /* 修改标志域 */ cp++; stack / 2); flag = 0; } else { /* 否则为叶子结点 */ stack += 1; flag = 2; } break; case 1: /* 访问的是左子树 */ if (stack 》= 2) { /* 右子树入栈 */ flag = 2; /* 修改标志域 */ cp += 2; stack / 4); flag = 1; } else { /* 否则为叶子结点 */ stack += 1; flag = 2; } break;case 2: /* */ if (flag == 2) { /* 当前是右子树吗? */ /* * 如果是右子树， 那么对某一棵子树的后序遍历已经 * 结束，接下来就是对这棵子树的根结点的访问 */ stack; flag = 2; cp = cp - 2; } else /* 否则退回到后序遍历的上一个结点 */ cp--; break; } } return stack; }算法分析：a)flag只有三个可能值：0表示第一次访问该结点，1表示访问的是左子树，2表示已经结束了对某一棵子树的访问，可能当前结点是这棵子树的右子树，也可能是叶子结点。b)每遍历到某个结点的时候，如果这个结点满足叶子结点的条件，那么把它的flag域设为2;否则根据访问的是根结点，左子树或是右子树来设置flag域，以便决定下一次访问该节点时的程序转向。 2)例2: 快速排序算法递归算法如下： void swap(int array， int low， int high) { int temp; temp = array; array; array = temp; } int partition(int array， int low， int high) { int p; p = array;while (low 《 high) { while (low 《 high && array 》= p) high--; swap(array，low，high); while (low 《 high && array 《= p) low++; swap(array，low，high); } return low; } void qsort_recursive(int array， int low， int high) { int p; if(low 《 high) { p = partition(array， low， high); qsort_recursive(array， low， p - 1); qsort_recursive(array， p + 1， high); } }需要说明一下快速排序的算法： partition函数根据数组中的某一个数把数组划分为两个部分，左边的部分均不大于这个数，右边的数均不小于这个数，然后再对左右两边的数组再进行划分。这里我们专注于递归与非递归的转换，partition函数在非递归函数中同样的可以调用(其实partition函数就是对当前结点的访问)。 再次进行递归调用树和栈的分析： 递归调用树：a)对当前结点的访问是调用partition函数;b)左子树：qsort_recursive(array， low， p - 1);c)右子树：qsort_recursive(array， p +1， high); d)叶子结点：当low 《 high时;e)可以看出这是一个先序调用的二叉树。栈：要保存的数据是两个表示范围的坐标。 代码：void qsort_nonrecursive(int array， int low， int high) { int m， cp， p; cp = 0; m = high; /* 初始化栈和栈顶指针 */ while (m) { while (m) { /* 向左走到尽头 */ p = partition(array， m); /* 对当前结点的访问 */ cp++; m; n = p - 1; } /* 向右走一步 */ m + 2; n; cp++; } }
用C++编程 ，快速排序非递归算法
#include 《iostream》using namespace std;int partition(int *a, int l, int h){int x = a;int i = l;int j = h+1;int temp; while (i《j){while (a《x&&i《h);while(a》x); if (i《j){temp = a;a;a = temp;}} a;a = x;return j;}void qsort(int *a, int l, int h){if (l》=h)return;int *s = new int;int p = 0;s = l;s = h;int low,high,q;while (p》0){high = s;low = s;if (low》=high)break; q = partition(a, low, high); if (q-low 》 high-q){s = low;s = q-1;if (high 》 q){s = q+1;s = high;}}else{s = q+1;s = high;if (q 》 low){s = low;s = q-1;}}}delete s;}int main(){int a = {9,8,7,6,5,4,3,2,1};//int a = {1,2,3,4,5,6,7,8,9};qsort(a,0,8); for (int i=0; i《9; i++)cout《《a《《endl;return 0;}
Python实现的快速排序算法详解
Python实现的快速排序算法详解本文实例讲述了Python实现的快速排序算法。分享给大家供大家参考，具体如下：快速排序基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。如序列。重复上述过程，直到基准数左边的数字都比其小，右边的数字都比其大。然后分别对基准数左边和右边的序列递归进行上述方法。实现代码如下： def parttion(v, left, right): key = v low = left high = right while low 《 high: while (low 《 high) and (v 》= key): high -= 1 v while (low 《 high) and (v 《= key): low += 1 v v = key return lowdef quicksort(v, left, right): if left 《 right: p = parttion(v, left, right) quicksort(v, left, p-1) quicksort(v, p+1, right) return vs = print("before sort:",s)s1 = quicksort(s, left = 0, right = len(s) - 1)print("after sort:",s1)运行结果： before sort: after sort:
求C语言快排非递归算法解析非递归
//快排非递归算法void merge(int a需要合并的两段 int i = 0;int j = 0;int k = 0;int count = 0;if(low 》= high) return;int m = center - low + 1;int n = high - center; int *L = (int *)malloc(sizeof(int)*SCALE);int *R = (int *)malloc(sizeof(int)*SCALE);if(!L || !R){printf("归并排序merge（）内存分配故障！");exit(0);}for( count=0; count《=m; count++){L;}for( int count=0; count《=n; count++){R;}for(i=0,j=0,k=low; i《m&&j《n; ++k){if( L ){a;}else{a;}}while(i 《 m){a;}while(j 《 n){a;}free(L);free(R);}
编写 快速排序的非递归算法
终于编写出来了，我写了两种，你看看：下面是代码：/*非递归算法1 递归算法的开销很大，所以在下编了一个非递归的，算法描述如下： A non-recursive version of quick sort using stack: There are 2 stacks, namely one which stores the start of a subarray and the other which stores the end of the subarray. STEP 1: while the subarray contains more than one element ,i.e. from Do { SUBSTEP 1. pivot=Partion(subarray); SUBSTEP 2. keep track of the right half of the current subarray i.e. push (pivot+1) into stackFrom, push (to) into stackTo SUBSTEP 3. go on to deal with the left half of the current subarray i.e. to=pivot-1 } STEP 2: if(neither of the stacks is empty) Get a new subarray to deal with from the stacks. i.e. start=pop(stackFrom); to=pop(stackTo); STEP 3: both stacks are empty, and array has been sorted. The program ends. */*/ void UnrecQuicksort(int q,int low,int high) {stack s1;《br/》 stacks2;《br/》 s1.push(low);《br/》 s2.push(high);《br/》 int tl,th,p;《br/》 while(!s1.empty() && !s2.empty())《br/》 {tl=s1.top();th=s2.top();《br/》 s1.pop();s2.pop();《br/》 if(tl》=th) continue;《br/》 p=partition(q,tl,th);《br/》 s1.push(tl);s1.push(p+1);《br/》 s2.push(p-1);s2.push(th);《br/》 } } /*非递归算法2 要把递归算法改写成非递归算法，可引进一个栈，这个栈的大小取决于递归调用的深度，最 多不会超过n，如果每次都选较大的部分进栈，处理较短的部分，递归深度最多不超过log2n ，也就是说快速排序需要的附加存储开销为O（log2n）。 */ void UnrecQuicksort2(int q,int low,int high) {int *a;《br/》 int top=0,i,j,p;《br/》 a=new int=i;《br/》 i=p-1;《br/》 } else {//先分割后部,前部进栈 a=j; a=p-1; j=p+1; } } } } /*打印输出*/ void display(int p,int len) {for(int i=0;i cout《 } /*测试*/ int _tmain(int argc, _TCHAR* argv) {int a={49,65,97,12,23,41,56,14}; quicksort(a,0,7); //UnrecQuicksort(a,0,7); //UnrecQuicksort2(a,0,7); display(a,8); return 0; }
C语言中快速排序法的原理及应用
“快速排序法”使用的是递归原理，下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组{53，12，98，63，18，72，80，46， 32，21}，先找到第一个数--53，把它作为中间值，也就是说，要把53放在一个位置，使得它左边的值比它小，右边的值比它大。{21，12，32， 46，18，53，80，72，63，98}，这样一个数组的排序就变成了两个小数组的排序--53左边的数组和53右边的数组，而这两个数组继续用同样的方式继续下去，一直到顺序完全正确。
一般来说，冒泡法是程序员最先接触的排序方法，它的优点是原理简单，编程实现容易，但它的缺点就是--程序的大忌--速度太慢。
附上快速排序代码：
#include《stdio.h》void quicksort(int a,int left,int right){ int i,j,temp; i=left; j=right; temp=a; if(left》right) return; while(i!=j) { while(a》=temp&&j》i) j--; if(j》i) a; while(a《=temp&&j》i) i++; if(j》i) a; } a=temp; quicksort(a,left,i-1); quicksort(a,i+1,right);}void main(){ int a={53,12,98,63,18,72,80,46,32,21}; int i; quicksort(a,0,9); /*排好序的结果*/ for(i=0;i《10;i++) printf("%4d\n",a);}
C语言课程设计：shell排序、堆排序、快速排序、归并(递归和非递归)排序5种算法效率分析！求能运行的源码！
#include 《stdio.h》#include 《time.h》#include 《stdlib.h》#include 《Windows.h》void shellSort(int *a,int len){ int step; int i,j; int temp; for(step=len/2; step》0;step/=2) { for(i=step;i《len;i++) { temp = a; for(j=i-step;(j》=0 && temp 《 a);j-=step) { a; } a = temp; } }}void swap(int *a,int *b){int temp = *a;*a = *b;*b = temp;}void heapify(int *a,int n,int k){int l,r,lg = -1;l = 2*k;r = l+1;if (l 《= n && a){lg = l;}else{lg = k;}if (r 《= n && a){lg = r;}if (lg != k){swap(&a);heapify(a,n,lg);}}void build_heap(int a,int n){for (int i=n/2+1; i》0; i--){heapify(a,n,i);}}void heap_sort(int a,int n){build_heap(a,n);for (int i=n; i》0; i--){swap(&a);heapify(a,i-1,1);}}int partitions(int a,long p,long q){long i,j=p-1;for (i=p; i《q; i++){if (a){j++;swap(&a);}}j++;swap(&a);return j;}void quicksort(int a,long p,long q){long i;if (p《q){i = partitions(a,p,q);quicksort(a,p,i-1);quicksort(a,i+1,q);}}void merge(int *a,int start, int mid, int end){int n1 = mid - start + 1;int n2 = end - mid;int *left = (int *)malloc(sizeof(int)*n1), *right=(int *)malloc(sizeof(int)*n2);int i, j, k;for (i = 0; i 《 n1; i++) /* left holds a */left;for (j = 0; j 《 n2; j++) /* right holds a */right;i = j = 0;k = start;while (i 《 n1 && j 《 n2)if (left)a;elsea;while (i 《 n1) /* left is not exhausted */a;while (j 《 n2) /* right is not exhausted */a;free(left);free(right);}void MergeSort(int *a,int start, int end){int mid;if (start 《 end) {mid = (start + end) / 2;MergeSort(a,start, mid);MergeSort(a,mid+1, end);merge(a,start, mid, end);}}double gettime(LARGE_INTEGER t,LARGE_INTEGER t1,LARGE_INTEGER t2){double time;if (t.LowPart==0 && t.HighPart==0) time = -1;else {time = (float)(t2.LowPart - t1.LowPart);if (time 《 0) time += 2^32;time /= (t.LowPart+t.HighPart * 2^32);}return time;}int main(){const int NUM = 1000;srand(time(NULL));int data;int i;for (i=0; i《NUM; ++i){data = rand()/(RAND_MAX/20000+1);}LARGE_INTEGER t,t1,t2;QueryPerformanceFrequency(&t);QueryPerformanceFrequency(&t1);shellSort(data,NUM);QueryPerformanceFrequency(&t2);printf("shell time:%0.4f\n",gettime(t,t1,t2));QueryPerformanceFrequency(&t1);heap_sort(data,NUM);QueryPerformanceFrequency(&t2);printf("shell time:%0.4f\n",gettime(t,t1,t2));QueryPerformanceFrequency(&t1);quicksort(data,1,NUM);QueryPerformanceFrequency(&t2);printf("shell time:%0.4f\n",gettime(t,t1,t2));QueryPerformanceFrequency(&t1);MergeSort(data,0,NUM);QueryPerformanceFrequency(&t2);printf("shell time:%0.4f\n",gettime(t,t1,t2));return 0;}
