快排+归并非递归实现

快排非递归

int quicksortOnce(int* nums, int l, int r)
{
	if (l >= r) return 0;
	int x = nums[l + r + 1 >> 1];
	int i = l - 1, j = r + 1;
	while (i < j)
	{
		do i++; while (nums[i] < x);
		do j--; while (nums[j] > x);
		if (i < j) swap(&nums[i], &nums[j]);
	}
	return i;
}
void quicksortNonR(int* nums, int n)
{
	const int N = 10010;
	int q[N] = { 0 };
	int hh = 0, tt = -1;
	q[++tt] = 0, q[++tt] = n - 1;
	//使用的是队列，队头的是l
	while (hh <= tt)
	{
		int l = q[hh++], r = q[hh++];
		int mid = quicksortOnce(nums, l, r);
		
		if (l < mid - 1) q[++tt] = l, q[++tt] = mid - 1;
		if (mid < r) q[++tt] = mid, q[++tt] = r;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

注意每次进行排序的时候都需要返回他们中间的那个位置（不能使用l+r>>1的方式直接确定中的位置)

归并排序非递归

void mergesortNonR(int* nums, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	int gab = 1;
	while (gab < n)
	{
		for (int i = 0; i < n; i += gab * 2)
		{
			int l1 = i, r1 = i + gab - 1, l2 = r1 + 1, r2 = l2 + gab - 1;
			if (r1 >= n || l2 >= n) break;
			if (r2 >= n) r2 = n - 1;
			int k = 0;
			while (l1 <= r1 && l2 <= r2)
			{
				if (nums[l1] < nums[l2]) tmp[k++] = nums[l1++];
				else tmp[k++] = nums[l2++];
			}
			while (l1 <= r1) tmp[k++] = nums[l1++];
			while (l2 <= r2) tmp[k++] = nums[l2++];
			memcpy(nums + i, tmp, sizeof(int) * (r2 - i + 1));
		}
		gab *= 2;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

使用两个区间进行归并更方便，但是使用一个区间分成两块儿在进行归并也不是不可以