DS快速排序和归并排序的非递归实现(16)

文章目录

前言
一、快排的非递归实现
二、归排的非递归实现
总结

前言

打破递归桎梏，迎接迭代解放！

一、快排的非递归实现

我们要替代递归，就要用到迭代或者循环，也就是说，其核心思想是不变的，只是换一种方式来实现而已
我们操控的是两个边界，利用栈来实现，这时候也就要考验你前面的知识是否学透了

void QuickSortNonR(int* arr, int n)
{
    // 初始化
    Stack st;
    StackInit(&st);

    // 先把最开始的两边界入栈
    StackPush(&st, n - 1);
    StackPush(&st, 0);

    // 进入循环，结束条件为空栈
    while (!isStackEmpty(&st)){
        int left = StackTop(&st);
        StackPop(&st);

        int right = StackTop(&st);
        StackPop(&st);

        int key = Partition(arr, left, right);

        // 先排左边，因此先让右边界进栈
        if (key + 1 < right){
            StackPush(&st, right);
            StackPush(&st, key + 1);
        }

        if (left < key - 1){
            StackPush(&st, key - 1);
            StackPush(&st, left);
        }
    }

    StackDestroy(&st);
}

栈的特性是先进后出，我们可以先将最外层的区间值入栈，即将 begin 与 end 入栈，之后进行选 key 划分的操作，判断左右区间是否合法，合法才能入栈，继续循环，如果所有区间都非法，栈就空了，循环也就结束了

二、归排的非递归实现

归并排序属于后序排序因此不是通过使用栈去模拟非递归实现归并排序，因此在这里我们的基本思路是整个序列分为以gap为子序列，结束条件为gap < n（gap = n - 1 表示归并最后一次）
在这里插入图片描述
这其实有点像归排里面的合并操作，只是由于是迭代版本，我们对于边界的处理要格外注意

下面是三种可能出现的边界问题

在这里插入图片描述
对于一二两种，我们直接跳出循环，对于第三种，那说明还是有数据需要递归的，这时候我们修改下end2即可

void MergeSortNonR(int* arr, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    int gap = 1;

    while (gap < n){
        for (int i = 0 ; i < n ; i += 2 * gap){
            // 拆成[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;

            // 没有右区间，其实就是第一二种情况
            if (begin2 >= n){
                break;
            }

            // 右区间过长
            if (end2 >= n){
                end2 = n - 1;
            }

            // 归并
            int index = begin1; // index是tmp的下标
            while (begin1 <= end1 && begin2 <= end2){
                if (arr[begin1] < arr[begin2]){
                    tmp[index++] = arr[begin1++];
                }

                else {
                    tmp[index++] = arr[begin2++];
                }
            }

            while (begin1 <= end1){
                tmp[index++] = arr[begin1++];
            }

            while (begin2 <= end2){
                tmp[index++] = arr[begin2++];
            }

            // 拷贝
            for (int j = i ; j <= end2 ; j++){
                arr[j] = tmp[j];
            }

        }
        gap *= 2;
    }
    free(tmp);
}