本篇内容主要讲解“c语言递归和非递归排序怎么实现”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“c语言递归和非递归排序怎么实现”吧!
递归代码流程
归并就是把两个或多个序列合并，这里只介绍二路归并，就是不断的把序列分为2组，直到每个组有一个元素为止，然后再比较合并，直到合为1个序列，完成。
非递归代码流程
与递归不断分解数组相反，非递归直接从长度为1的子序列开始合并，直到全并为1个整个序列，复用了merge函数
两者比较
代码用非递归的方式效率更高一些：
空间复杂度：从O(log2n)变为1个临时数组O(n)
时间复杂度：少了递归的时间
时间复杂度
O(nlogn)
代码（递归）
#include <stdio.h>#include <stdbool.h>#define MAXSIZE 9typedef struct { int r[MAXSIZE+1]; // first index used as tmp, not real data int len;}SqList;void swap(SqList *L, int i, int j) { int tmp = L->r[i]; L->r[i] = L->r[j]; L->r[j] = tmp;}void merge(int sr[], int tr[], int s, int m, int t) { // 本函数的任务就是比对sr中两个分组(s..m, m+1..t)的元素大小并归并到tr int j,k,l; j = m + 1; // 第2分组的起始位置 k = s; // k用于tr数组中的游标与sr中的起始位置对应起来 while (s<=m && j<=t) { if (sr[s] < sr[j]) { tr[k++] = sr[s++]; } else { tr[k++] = sr[j++]; } } // 只要是合并，就肯定至少是2个序列合并，肯定会在比对后剩下1个未消耗完元素的序列分组 while (s<=m) { tr[k++] = sr[s++]; } while (j<=t) { tr[k++] = sr[j++]; }}void msort(int sr[], int tr[], int s, int t) { int m; int tmpr[MAXSIZE+1]; // 每层递归的临时数组，存放本次被调用时s到t归并后的下标值(位置与首次传入的L->r相同) if (s == t) { tr[s] = sr[s]; // 归并的思想，1个元素的分组为有序 } else { // 不是1个元素的分组，继续分组 m = (s+t)/2; msort(sr, tmpr, s, m); msort(sr, tmpr, m+1, t); // 合并tmpr到tr完成本层的排序任务 merge(tmpr, tr, s, m, t); }}void merge_sort(SqList *L) { msort(L->r, L->r, 1, L->len); // 因为在msort中第1个参数sr数组只是读取，所以这里这样传递没有问题}int main(void) { SqList list = { {999,50,10,90,30,70,40,80,60,20}, MAXSIZE }; merge_sort(&list); printf("after merge_sort:\n"); for (int i=0; i<=MAXSIZE; i++) { printf("index: %d, value: %d\n",i,list.r[i]); } return 0;}output
➜ c gcc sort_merge.c&& ./a.out
after merge_sort:
index: 0, value: 999
index: 1, value: 10
index: 2, value: 20
index: 3, value: 30
index: 4, value: 40
index: 5, value: 50
index: 6, value: 60
index: 7, value: 70
index: 8, value: 80
index: 9, value: 90
代码（非递归）
#include <stdio.h>#include <stdbool.h>#include <stdlib.h>#define MAXSIZE 9typedef struct { int r[MAXSIZE+1]; // first index used as tmp, not real data int len;}SqList;void merge(int sr[], int tr[], int s, int m, int t) { // 本函数的任务就是比对sr中两个分组(s..m, m+1..t)的元素大小并归并到tr int j,k,l; j = m + 1; // 第2分组的起始位置 k = s; // k用于tr数组中的游标与sr中的起始位置对应起来 while (s<=m && j<=t) { if (sr[s] < sr[j]) { tr[k++] = sr[s++]; } else { tr[k++] = sr[j++]; } } // 只要是合并，就肯定至少是2个序列合并，肯定会在比对后剩下1个未消耗完元素的序列分组 while (s<=m) { tr[k++] = sr[s++]; } while (j<=t) { tr[k++] = sr[j++]; }}void merge_pass(int sr[], int tr[], int k, int len) { int i=1; // 合并时的游标 while (i < len-2*k+1) { // 也就是每次循环后，当前所剩余的是否还够2个完整子序列 merge(sr, tr, i, i+k-1, i+2*k-1); //合并本轮扫描到的2个子序列 i+=2*k; // 赋值后的i为下一轮2个子序列的起始位置 } // 下面是扫尾工作，**可能会**出现2种情况，a. 剩余1～2个子序列之间的情况, b. 剩余<=1个子序列的情况 if (i < len-k+1) { merge(sr, tr, i, i+k-1, len); } else { // 这里加else也可以 如果上面i正好把序列消耗完，则循环不会执行 while (i<len) { tr[i] = sr[i]; i++; } }}void merge_sort(SqList *L) { int *tr = (int *)malloc(L->len*sizeof(int)); int k=1; while (k<L->len) { merge_pass(L->r, tr, k, L->len); // 序列1变2 k++; merge_pass(tr, L->r, k, L->len); // 序列2变4 k++; }}int main(void) { SqList list = { {999,50,10,90,30,70,40,80,60,20}, MAXSIZE }; merge_sort(&list); printf("after merge_sort2:\n"); for (int i=0; i<=MAXSIZE; i++) { printf("index: %d, value: %d\n",i,list.r[i]); } return 0;}output
➜ c gcc sort_merge_norecursive.c&& ./a.out
after merge_sort2:
index: 0, value: 999
index: 1, value: 10
index: 2, value: 20
index: 3, value: 30
index: 4, value: 40
index: 5, value: 50
index: 6, value: 60
index: 7, value: 70
index: 8, value: 80
index: 9, value: 90
到此，相信大家对“c语言递归和非递归排序怎么实现”有了更深的了解，不妨来实际操作一番吧！这里是编程网网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
