快速排序与归并排序的非递归算法_为实现快速排序的非递归算法,可根据基准元素

快速排序非递归

快速排序是一种基于分治的排序算法，其基本思想是选定一个基准元素，然后将待排序数组中小于等于基准元素的元素放到其左侧，大于基准元素的元素放到其右侧，然后对左右两个子数组递归地进行同样的操作，直到整个数组有序。

快速排序的递归算法非常容易理解，但是由于其递归深度可能很大，可能导致栈溢出等问题。因此，我们可以考虑使用非递归算法来实现快速排序。非递归的快速排序算法通常使用栈来实现，将待排序区间的左右端点压入栈中，每次弹出一个区间并对其进行分割，直到栈为空为止。

#include <stack>
#include <algorithm>
using namespace std;
 
void quickSortNonRecursive(int arr[], int left, int right) {
    stack<pair<int, int>> stk;
    stk.push({left, right});
    while (!stk.empty()) {
        int l = stk.top().first, r = stk.top().second;
        stk.pop();
        if (l >= r) 
            continue;
        int pivot = arr[l + rand() % (r - l + 1)];
        int i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (arr[i] < pivot);
            do j--; while (arr[j] > pivot);
            if (i < j) 
                swap(arr[i], arr[j]);
        }
        stk.push({l, j}), stk.push({j + 1, r});
    }
}

在上面的代码中，我们使用了一个pair<int, int>类型的栈来保存待排序的区间，每次取出栈顶元素，并对其进行分割。其中，我们使用rand()函数随机选择一个基准元素，以增加算法的随机性，防止出现最坏情况，提高排序的效率。同时，我们使用了双指针i和j来进行分割，i指向左侧子数组的末尾，j指向右侧子数组的开头，当i和j相遇时，分割完成。

归并排序非递归

归并排序是另一种基于分治思想的排序算法，其基本思想是将待排序数组分成两个子数组，对每个子数组递归地进行排序，最后将两个有序子数组合并成一个有序数组。归并排序的递归算法非常容易实现，但同样存在递归深度过大的问题。因此，我们可以使用非递归算法来实现归并排序。

非递归归并排序算法的核心思想是利用循环将数组不断地分成长度为2的子数组，然后将相邻的两个子数组合并成一个有序的大数组，不断循环，直到整个数组有序。具体实现中，我们使用了一个类似于归并排序中的merge函数来实现数组的合并，同时使用了一个长度为数组长度的临时数组来存储中间结果。

#include <stack>
using namespace std;
 
void mergeSortUnRec(int* arr, int n)
{
	int* help = new int[n];
	memset(help, 0, sizeof(int) * n);
	stack<pair<int, int> > stk1, stk2;
	stk1.push({ 0,n - 1 });
	while (!stk1.empty())
	{
		auto p = stk1.top();
		stk1.pop();
		if (p.first >= p.second)
			continue;
		stk2.push(p);
		int m = p.first + (p.second - p.first) / 2;
		stk1.push({ m + 1,p.second });
		stk1.push({ p.first,m });
	}
	//merge
	while (!stk2.empty())
	{
		int l = stk2.top().first, r = stk2.top().second;
		stk2.pop();
		int m = l + (r - l) / 2;
		int cur1 = l, cur2 = m + 1, cur3 = l;
		while (cur1 <= m && cur2 <= r)
		{
			if (arr[cur1] < arr[cur2])
				help[cur3++] = arr[cur1++];
			else
				help[cur3++] = arr[cur2++];
		}
		while (cur1 <= m)
			help[cur3++] = arr[cur1++];
		while (cur2 <= r)
			help[cur3++] = arr[cur2++];
		memcpy(arr + l, help + l, sizeof(int) * (r - l + 1));
	}
	delete[] help;
}

在上述代码中，我们定义了两个pair类型的栈，其中pair的第一个元素表示子数组的左端点，第二个元素表示子数组的右端点。首先，我们利用stk1作为辅助将整个数组划分成若干个子数组，并将这些子数组入栈stk2。接下来，我们不断地从栈stk2中取出两个子数组，进行归并操作，重复这个过程，直到栈为空。

也可以不用栈用循环，也可以达到同样的目的

void merge(int arr[], int l, int m, int r) {
    int i = l, j = m + 1, k = 0;
    int* tmp = new int[r - l + 1];
    while (i <= m && j <= r) {
        if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
        else tmp[k++] = arr[j++];
    }
    while (i <= m) 
        tmp[k++] = arr[i++];
    while (j <= r) 
        tmp[k++] = arr[j++];
    for (i = l, k = 0; i <= r; i++, k++) 
        arr[i] = tmp[k];
    delete[] tmp;
}
 
void mergeSortNonRecursive(int arr[], int n) {
    for (int sz = 1; sz < n; sz *= 2) {
        for (int i = 0; i < n - sz; i += sz * 2) {
            merge(arr, i, i + sz - 1, min(i + sz * 2 - 1, n - 1));
        }
    }
}