介绍
在上一篇博客中,我们使用快速排序的时候是使用递归的方式进行的,如上图所示,
但是如果我们把递归变成非递归的形式,该怎么进行呢
一般有以下方法
(1)循环 (2)借助栈
可以结合这个图进行非递归进行
这个思路图,这个图只是简单的介绍了0 ~4的栈的入栈和出栈情况
typedef int TackDataType; typedef struct SLtack { TackDataType* TData; int Top;//标识栈顶位置 int Capacity; }SLtack; //初始化 void TackInit(SLtack* pst) { assert(pst); pst->TData = NULL; pst->Top = 0;//栈顶元素的下一个 pst->Capacity = 0; } //释放 void TackDestroy(SLtack* pst) { assert(pst); free(pst->TData); pst->TData = NULL; pst->Top = 0; pst->Capacity = 0; } //插入数据 void TackPushData(SLtack* pst, TackDataType elemest) { assert(pst); //判断容量 if (pst->Capacity == pst->Top) { TackcapacityAdd(pst); printf("扩容成功\n"); } assert(pst->Capacity != pst->Top); pst->TData[pst->Top] = elemest; pst->Top++; } //删除数据 void TackPopData(SLtack* pst) { assert(pst); if(pst->Top) pst->Top--; } //空间扩容 void TackcapacityAdd(SLtack* pst) { assert(pst); //扩容 pst->Capacity = (pst->Capacity == 0 ? 4 : pst->Capacity * 2); TackDataType* tmp = realloc(pst->TData, sizeof(TackDataType) * pst->Capacity); if (tmp == NULL) { perror("realloc"); return; } pst->TData = tmp; } //找出栈顶 TackDataType TackTop(SLtack* pst) { assert(pst); return *(pst->TData + (pst->Top - 1)); } //判断栈是否为空 bool Empty(SLtack* pst) { assert(pst); return pst->Top == 0; } //栈的长度 int TackSize(SLtack* pst) { assert(pst); return pst->Top; } int TriNum(int* a, int begin, int end) { int mid = (begin - end) / 2 + end; if (begin > end) { if (end > mid) { return end; } else if (begin < mid) { return begin; } return mid; } else { if (begin > mid) { return begin; } else if (end < mid) { return end; } else return mid; } } void excheng(int* a, int* b) { int c = *a; *a = *b; *b = c; } int main() { srand(time(NULL)); int N = 100; int* arr = (int*)malloc(sizeof(int) * N); int i = 0; for (i = 0; i < N; i++) { arr[i] = rand(); } //创建一个栈 SLtack* tack = (SLtack*)malloc(sizeof(SLtack)); //初始化 TackInit(tack); int begin = 0; int end = N - 1; //插入 TackPushData(tack, begin); TackPushData(tack, end); while (!Empty(tack)) { //找出栈顶 TackDataType end1 = TackTop(tack); //删除 TackPopData(tack); //找出栈顶 TackDataType begin1 = TackTop(tack); //删除 TackPopData(tack); //快速排序 int key = TriNum(arr, begin1, end1); excheng(&arr[key], &arr[(begin1)]); key = begin1; int prev = begin1; int cur = begin1 + 1; while (cur <= end1) { //cur 比较 if (arr[cur] < arr[key] && ++prev != cur)//增加++prev != cur可以有效解决相同位置进行交换 { excheng(&arr[cur], &arr[prev]); } cur++; } excheng(&arr[key], &arr[prev]); if (begin1 < prev - 1) { TackPushData(tack, begin1); TackPushData(tack, prev - 1); } if (prev + 1 < end1) { TackPushData(tack, prev + 1); TackPushData(tack, end1); } } free(arr); TackDestroy(tack); return 0; }
归并排序
思路：
核心：分解和合并
将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。
将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。
#include<stdio.h> #include<stdlib.h> #include<time.h> #include<string.h> void _Mergesort(int* arr, int begin, int end, int *tmp) { if (begin >= end) return; //分割 int mid = (end + begin) / 2; _Mergesort(arr, begin, mid, tmp); _Mergesort(arr, mid + 1, end, tmp); //合并 int cur1 = begin; int cur2 = mid + 1; int i = 0; while (cur1 <= mid && cur2 <= end) { if (arr[cur1] >= arr[cur2]) { tmp[i++] = arr[cur2++]; } else { tmp[i++] = arr[cur1++]; } } if (cur1 > mid) { while (cur2 <= end) { tmp[i++] = arr[cur2++]; } } if (cur2 > end) { while (cur1 <= mid) { tmp[i++] = arr[cur1++]; } } memcpy(arr + begin, tmp, sizeof(int) * i); } void Mergesort(int* arr, int begin, int end) { //创建一个数组 int* tmp = (int*)malloc(sizeof(int) * (end - begin + 1)); if (tmp == NULL) { perror("malloc"); return; } _Mergesort(arr, begin, end, tmp); free(tmp); } int main() { srand(time(NULL)); int N = 10000; int* arr = (int*)malloc(sizeof(int) * N); int i = 0; for (i = 0; i < N; i++) { arr[i] = rand(); } //归并排序 Mergesort(arr, 0, N - 1); free(arr); return 0; }
需要借助一个数组tmp
归并排序的非递归
从归并排序的递归思路来，主要就是合并的思想，如果我们要把非递归的思路模拟递归的思路，就要明白归并的合并怎么开始
可以看出
思路：我们合并的开始是一个元素开始，第二次合并是两个元素，第三次就是4个，直到合并的长度变成了整个数组的长度，就结束
我们在两两合并的时候就是有可能会碰见落单的小数组，我们可以让其和合并过的前一个进行合并组成一个新合并的数组，
#include<stdio.h> #include<stdlib.h> #include<time.h> #include<string.h> void merge(int* arr, int begin1, int end1, int begin2, int end2,int *tmp) { //合并 int i = 0; int x = begin1; while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] >= arr[begin2]) { tmp[i++] = arr[begin2++]; } else { tmp[i++] = arr[begin1++]; } } if (begin1 > end1) { while (begin2 <= end2) { tmp[i++] = arr[begin2++]; } } if (begin2 > end2) { while (begin1 <= end1) { tmp[i++] = arr[begin1++]; } } memcpy(arr + x, tmp, sizeof(int) * i); } void _Mergesort(int* arr, int begin, int end, int *tmp) { int t = 1;//每次元素的个数 while (t <= (end + 1)/ 2)//遍历的次数 { int i = 0;//代表开始的下标 //每次遍历一遍 while ((i + 2 * t -1)<= end) { merge(arr, i, i + t - 1, i + t, i+2 * t - 1, tmp); i = i + 2 * t; } //判断是否还有部分没有合并 if (i <= end) { merge(arr, i - 2 * t, i - 1, i, end, tmp); } t *= 2; } } void Mergesort(int* arr, int begin, int end) { //创建一个数组 int* tmp = (int*)malloc(sizeof(int) * (end - begin + 1)); if (tmp == NULL) { perror("malloc"); return; } _Mergesort(arr, begin, end, tmp); free(tmp); } int main() { srand(time(NULL)); int N = 33; int* arr = (int*)malloc(sizeof(int) * N); int i = 0; for (i = 0; i < N; i++) { arr[i] = rand(); } int diyth[] = { 6,5,8,4,1,2,8,9,5 }; //归并排序 Mergesort(arr, 0, N - 1); for (i = 0; i < N; i++) { printf("%d\n", arr[i]); } free(arr); return 0; }
