2.非递归写法（类比层序遍历用队列实现，这里用栈）
学习原因：递归的本质是不断开辟空间，当递归层数过多时可能会出现栈溢出的问题。因而引入非递归写法
实现原理：递归写法本质上是向下不断开辟空间，当达到终止条件时返回并归还空间。不采用递归的写法，即可以在原数组上直接对下标进行划分
1.入尾标，入头标
2.标记begin，end后，进行头删，并算出keyi
3.此时，原数组被分割成【begin，keyi-1】keyi【keyi+1,end】。
分别对存在的区间进行同样的操作（压栈，出栈）即可。
图示：
PS：数字表示，可视作递归的层数。而实际上没有递归。
void quicksortnonr(int*a,int left,int right) { ST st; StackInit(&st); StackPush(&st, right);//表示end的先入栈 StackPush(&st, left); while (!StackEmpty(&st)) { int begin = StackTop(&st); StackPop(&st); int end = StackTop(&st); StackPop(&st); //得出keyi int keyi = Partsort3(a, begin, end);//三数取中 //【begin，keyi-1】keyi【keyi+1，end】 if (keyi + 1 < end) { StackPush(&st, end);//表示end的先入栈 StackPush(&st, keyi+1); } if (keyi -1 >begin) { StackPush(&st, keyi - 1);//表示end的先入栈 StackPush(&st, begin); } } StackDestroy(&st); }
8.归并排序（递归和非递归写法）
1.递归写法
归并原理：两个有序数组进行比较，并尾插到新空间。
PS：结合递归后，即可细分到只剩两个数归并形成有序数组，两两合成新的有序序列，并拷贝到一块新空间（避免覆盖原数组），新空间的位置关系要与原数组对应
形象图示：
注意点：为提升效率，采用取中间数进行划分
图示：
void MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end) return; int mid = (begin + end) / 2; MergeSort(a,begin,mid,tmp); MergeSort(a,mid+1,end,tmp); //拷贝回与原数组a相对应的位置 memcpy(a + begin,tmp + begin，sizeof(int) * (end - begin + 1)); }
递归实现的逻辑：后序遍历
PS：后序遍历相关可查看博主相关博客
2.非递归写法（注意越界情况的分类讨论）
分析：与快排的非递归算法同理。当递归次数过多时，有可能会导致栈溢出。不妨在原数组的基础上，直接对下标对应区间范围内的数组进行归并，并拷贝回原数组。
形象图示：
注意点：有时候gap的选取会越界！
分析：本质上是不断选取【begin1，end1】【begin2，end2】
注意点：以下分析是在归并进行前，对下标对应空间进行讨论！
1.当begin1和end2和并后形成新begin1，end1时，若end1临界(begin2越界）/end1越界，则停止归并
2.当end1越界时，则对end1进行修正
形象图示：
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail\n"); return; } int gap = 1; while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { // [begin1,end1][begin2, end2] int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1;//((i+gap)+(gap-1)) //printf("[%d,%d][%d,%d] ", begin1, end1,begin2,end2); //分类讨论情况 if (end1 >= n || begin2 >= n) { break; } if (end2 >= n) { end2 = n - 1;//修正end2区间 } printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2); int j = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[j++] = a[begin1++]; } else { tmp[j++] = a[begin2++]; } } while (begin1 <= end1) { tmp[j++] = a[begin1++]; } while (begin2 <= end2) { tmp[j++] = a[begin2++]; } // 归并一部门拷贝一部分 memcpy(a+i, tmp+i, sizeof(int) *(end2-i+1)); } printf("\n"); gap *= 2; } free(tmp); }
三.8种排序方式复杂度/稳定性分析
1.稳定性的概念
假定再待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变，则称这种算法是稳定的。
2.分析
*计数排序较为特别，时间复杂度O(n)/O(range),空间复杂度为O(n)
1.简单选择排序不稳定的原因
特例：替换的数在两相同数同一边时
2.复杂度分析综述
1.希尔排序是直接插入排序基础上加了预处理。较为复杂，暂记结论。
2.直接插入排序，是取每一个数和前面所有数进行比对。无论如何都要先取，所以最好情况即有序情况即是n，最坏情况相当于一个数组的遍历，n^2。
3.快速排序当keyi每次都能取中间值时，接近二叉树，nlogn。keyi每次都取最左/右值时，即相当于一个数组的遍历，n^2。
4.归并排序，接近二叉树，nlogn。由于需要tmp新空间容纳归并后的新空间，空间复杂度为n
5.堆排序，分为堆调整（向上向下）和用删除思想堆排序两部分，根据数学计算知道后者复杂度为nlogn，即堆排整体为nlogn。
————————————————
版权声明：本文为CSDN博主「你的小笔记本YY」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
