「数据结构」八大排序(超详解 附动图 源码)(14)

6.5快速排序非递归实现

快速排序非递归实现，需要借助栈，栈中存放的是需要排序的左右区间。
而且非递归可以彻底解决栈溢出的问题。
其实他的思想与递归是类似的：
具体思想：
将数组左右下标入栈， 若栈不为空，两次取出栈顶元素，分别为闭区间的左右界限 将区间中的元素按照前后指针法排序(其余两种也可)得到基准值的位置 再以基准值为界限，若基准值左右区间中有元素，则将区间入栈 重复上述步骤直到栈为空
代码如下：
// 快速排序 非递归实现void QuickSortNonR(int* a, int left, int right){ //创建栈 Stack st; StackInit(&st); //原始数组区间入栈 StackPush(&st, right); StackPush(&st, left); //将栈中区间排序 while (!StackEmpty(&st)) { //注意：如果right先入栈，栈顶为left left = StackTop(&st); StackPop(&st); right = StackTop(&st); StackPop(&st); //得到基准值 int mid = PartSort3(a, left, right); // 以基准值为分割点，形成左右两部分 if (right > mid 1) { StackPush(&st, right); StackPush(&st, mid 1); } if (left < mid - 1) { StackPush(&st, mid - 1); StackPush(&st, left); } } StackDestroy(&st);}
快速排序的特性总结：
快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序 时间复杂度：O(N*logN) 空间复杂度：O(logN) 稳定性：不稳定

7.归并排序

7.1递归实现

基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。