一、非递归实现快速排序
void QuickSortNonR(int* a, int begin, int end) { ST s; STInit(&s); STPush(&s, end); STPush(&s, begin); while (!STEmpty(&s)) { int left = STTOP(&s);//先拿出来 STPop(&s); int right= STTOP(&s);//后拿出来 STPop(&s); //单躺排序，一次调整，得到中间keyi值，划分填入 int keyi = PartSort2(a, left, right); //[left,keyi-1]keyi[keyi+1,right] if (left < keyi - 1) { STPush(&s, keyi - 1); STPush(&s, left); } if (keyi + 1 < right) { STPush(&s, right); STPush(&s, keyi+1); } } STDestroy(&s); }
过程解析:非递归实现快速排序也是需要通过快速排序思想来走的，基本思想是以某数值为基准值，不断将待排序集合分割成两组子序列，采用前序遍历的方法根 左子树 右子树，对于递归的过程中我们知道左子树会演变为新的根，也会分为新根 新左子树 新右子树，然后我们将采用栈来模拟递归的过程，由于栈的特点是后进先出合前序遍历的特性。这里后进代表着左子树，新出代表着该左子树为根演变新左子树和新右子树的过程。然后这里需要范围去定义根(整体范围)、左子树（左边范围）、右子树（右边范围）。这里左子树会不断分为新的左子树和右子树，也意味着产生新的范围，一般来说先取左边(在上)再取右边(在下)，对应着右边先压栈，左边再压栈。 
单躺排序结束会返回中间位置下标keyi帮整体划分为两部分，不断重复该过程。当条件不满足时，说明暂时不需要继续分为左子树和右子树，可能出现其他两种结果。第一种相等，说明只有一个数据；第二种大于。说明不存在数据，不需要压栈，等到栈为空结束排序。
二、非递归实现归并排序
由于快速排序采用是前序遍历满足栈相关数据结构的特性，然后归并排序属于后序排序因此不是通过使用栈区模拟非递归实现归并排序。如果采用栈去模拟实现非递归归并排序，由于归并排序不像快速排序不是出栈既排序，而是等到栈为空，开始归并排序，然而没有归并操作这种做法。
基本思路:整个序列分为以gap为子序列，结束条件为gap < n（gap = n - 1 表示归并最后一次），将两个有序子序列，比较大小尾插到新数组中，(子序列中只有一个数据时，默认是有序的)。对于两个有序子序归并在一起，形成一个新的有序子序列，当形成完新的子序列，复制到原数组中，不断重复该操作。
解决办法:对此应当设置变量gap为归并每组数据个数，首先gap设为1，以二的幂次方增长。
int begin1=i,end1=i+gap-1; int begin2=i+gap,end2=i+2*gap-1; [begin1,end1][begin2,end2]归并
注意点:这里gap是二的幂次方增长，对于两个子序列匹配时，规定数量是固定的，可能会出现越界访问，所以需要注意end1，begin2和end2的值。
对于end2只需要将修改为临界值就行，而对于end1和begin2则不参与进程。完成一趟for循环，需要拷贝到原数组中，这样子的话不参与进程的序列，将被随机值替代.
if (end1 >= n || begin2 >= n) break; if (end2 >= n) end2 = n - 1;
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(n * sizeof(int)); if (tmp == NULL) { perror("malloc fail!!!"); return; } int gap = 1; while (gap < n) { printf("gap:%2d->", gap); for (int i = 0; i < n; i += 2 * gap)//调正部分是跳过两组子序列，去到新的两组子序列中 { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; //printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2); if (end1 >= n || begin2 >= n) { break; } if (end2 >= n) { end2 = n - 1; } printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2); //上面是传值 int j = begin1; //下面是插入，这里j下标很有讲究 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); }
以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二初阶数据结构笔记，希望对你在学习初阶数据结构中有所帮助！
