One day when I was boiling water in a kettle
Accidentally, the water is full
So when it boils
The water kept coming out
I think of the stack overflow caused by recursion
So sister a Zi learned the non recursive algorithm online
Next, sister a Zi will teach you !
Sister Zi will lead you to learn quickly , Merge sort non recursive implementation oh !!!
catalogue ：
1, Quick sort non recursive
2, Merge sort non recursive
Before learning non recursion, we have to learn the defects of recursion , To better understand the advantages of non recursion .
Recursive defect ： Stack frame space is too deep , Insufficient stack space , Can cause overflow .
c Language memory allocation ：
for example ：
recursion 1000 second ：
recursion 10000 second ：
graphic ：
recursion （ function call ） Is to press the stack , When the stack is too deep , It will cause stack overflow .
Recursive to non recursive method ：① Direct conversion cycle ② Simulate recursive process with data structure stack
1, Quick sort non recursive
Let's use non recursion to realize the quick sorting and digging method
1.1 code implementation
Stack operation , You can see what ah Zi sent before “ can't 2022 Is there anyone who doesn't understand the stack ” This blog post !
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include"stack.h" // Excavation method -
Ascending order int PartSort(int* a, int left, int right) { int begin = left; int end =
right; int key = a[begin]; int pivot = begin; while (begin < end) { while
(begin < end && a[end] >= key) { --end; } a[pivot] = a[end]; pivot = end; while
(begin < end && a[begin] <= key) { ++begin; } a[pivot] = a[begin]; pivot =
begin; } pivot = begin;// When begin And end meet , Casually begin and end Value for pivot a[pivot] = key;
return pivot; } // Quick sort non recursive void QuickSortNonR(int* a, int n) { ST st;
StackInit(&st);// Initialization stack StackPush(&st, n - 1);// Subscript of the last element in the array StackPush(&st,
0);// Subscript of the first element in the array while (!StackEmpty(&st))// When the stack is not empty, we enter the loop { int left =
StackTop(&st);// Take out the top element of the stack and give it to left StackPop(&st);// Out of stack - Delete stack top element int right =
StackTop(&st); StackPop(&st); int keyIndex = PartSort(a, left,
right);// Interval sorting using pit digging method //[left, keyIndex - 1] keyIndex [keyIndex + 1, right] -
Sub interval if (keyIndex + 1 < right)// Due to the last in first out feature of stack , So enter the right section first { StackPush(&st, right);
StackPush(&st, keyIndex + 1); } if (left < keyIndex - 1) { StackPush(&st,
keyIndex - 1); StackPush(&st, left); } } StackDestory(&st);// Destroy stack } int main() {
int arr[10] = {3, 4, 2, 5, 1}; int sz = sizeof(arr) / sizeof(arr[0]);
QuickSortNonR(arr, sz); for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); }
return 0; }
1.2 Train of thought explanation
Let's learn ideas according to the above code
2, Merge sort non recursive
2.1 code implementation
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include"stack.h"
// Non recursive merge sort void MergeSortNonR(int* a, int n) { int* tmp =
(int*)malloc(sizeof(int)* n); if (tmp == NULL) { perror("malloc:"); return; }
int gap = 1;//gap Is the number of data in each group , Double each time while (gap < n) { for (int i = 0; i < n; i += 2
* gap) { // Can be regarded as [i, i + gap - 1] [i + gap, i + 2 * gap - 1] int begin1 = i,
end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1;
// In the process of merging, the right half interval may not exist ! if (begin2 >= n) break; // In the process of merging, the right half of the interval crossed the boundary , On correction if (end2 >= n) {
end2 = n - 1; } int index = i; while (begin1 <= end1 && begin2 <= end2) { if
(a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] =
a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while
(begin2 <= end2) { tmp[index++] = a[begin2++]; } // copy in for (int j = i; j <=
end2; ++j) { a[j] = tmp[j]; } } gap *= 2; } free(tmp); } int main() { int arr[]
= {10, 6, 7, 1, 3, 9, 4, 2 }; int sz = sizeof(arr) / sizeof(arr[0]);
MergeSortNonR(arr, sz); for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); }
return 0; }
2.2 Train of thought explanation
Technology
Daily Recommendation