快速排序和归并排序的非递归实现

创作时间:

作者:

@小白创作中心

快速排序和归并排序的非递归实现

引用

CSDN

https://blog.csdn.net/hdxbufcbjuhg/article/details/144775846

快速排序和归并排序是两种非常重要的排序算法，它们通常以递归方式实现。然而，在某些场景下，递归实现可能会导致栈溢出等问题。因此，掌握它们的非递归实现方式是非常有必要的。本文将详细介绍如何使用栈和队列来实现快速排序的非递归版本，以及如何实现归并排序的非递归版本。

一、非递归版快速排序

1. 使用栈实现非递归版快速排序

在学习非递归版快速排序前，建议先了解递归版的快速排序。递归的本质是在内存的栈区开辟新的函数栈帧，而栈区的压栈方式与数据结构中的压栈类似，因此可以通过栈这个数据结构来模拟递归调用的行为。

具体实现时，需要一个栈来存储数组的左右下标。每次将指定数组序列的左右下标存入栈中，为了保证取出时是左右的顺序，需要将右下标先入栈，再入栈左下标。

void NonRQuickSort1(int* arr, int left, int right)
{
    ST st;
    STInit(&st);
    STPush(&st, right);
    STPush(&st, left);
    while (!STEmpty(&st))
    {
        int left = STTop(&st);
        STPop(&st);
        int right = STTop(&st);
        STPop(&st);
        if (left >= right) continue;
        int keyi = _QuickSort(arr, left, right);
        // [left, keyi - 1] [keyi + 1, right]
        if (right > keyi + 1)
        {
            STPush(&st, right);
            STPush(&st, keyi + 1);
        }
        if(left < keyi - 1)
        {
            STPush(&st, keyi - 1);
            STPush(&st, left);
        }
    }
    STDestroy(&st);
}

2. 使用队列实现非递归版快速排序

队列版快速排序的实现思路与栈版类似，主要区别在于使用队列来存储下标。由于快速排序的左右区间一旦划分就互不影响，可以使用层序遍历的思想，将划分出来的左右区间依次进行处理。

void QuickSortNonR2(int* arr, int left, int right)
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, left);
    QueuePush(&q, right);
    while (!QueueEmpty(&q))
    {
        int left = QueueFront(&q);
        QueuePop(&q);
        int right = QueueFront(&q);
        QueuePop(&q);
        int keyi = _QuickSort(arr, left, right);
        // [left, keyi - 1] [keyi + 1, right]
        if (left < keyi - 1)
        {
            QueuePush(&q, left);
            QueuePush(&q, keyi - 1);
        }
        if (right > keyi + 1)
        {
            QueuePush(&q, keyi + 1);
            QueuePush(&q, right);
        }
    }
    QueueDestroy(&q);
}

二、非递归版归并排序

归并排序的非递归实现不能使用栈或队列，因为后序遍历需要左右子树的信息，而栈只能模拟先处理根的情况。非递归版归并排序的本质是对数组进行分组，然后两两一组进行排序，最后进行合并。

具体实现时，首先将数组的一个元素划分为一组，然后两两一组进行合并。合并完成后，将gap乘以2来调整每组元素的个数，用新的gap来划分数组，直到gap大于或等于数组长度。

void MergeSortNonR(int* arr, int n)
{
    int* tmp = (int*)malloc(n * sizeof(n));
    if (tmp == NULL)
    {
        perror("malloc");
        return;
    }
    int gap = 1;
    while (gap < n)
    {
        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;
            if (end1 >= n || begin2 >= n)
            {
                break;
            }
            else if (end2 >= n)
            {
                end2 = n - 1;
            }
            int j = begin1;
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (arr[begin1] < arr[begin2])
                    tmp[j++] = arr[begin1++];
                else
                    tmp[j++] = arr[begin2++];
            }
            while (begin1 <= end1)
            {
                tmp[j++] = arr[begin1++];
            }
            while (begin2 <= end2)
            {
                tmp[j++] = arr[begin2++];
            }
            for (int j = i; j <= end2; j++)
            {
                arr[j] = tmp[j];
            }
        }
        gap *= 2;
    }
}