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

快速排序：是一种交换排序，当完全有序时退化为冒泡排序，时间复杂度为O（n^2)。正常情况下为O（nlogn）.

非递归：其实就是手动利用栈来存储每次划分后两个序列的起始点和终止点。栈非空时获取栈顶两个值：起始点和终止点，然后再根据两个点划分获得中轴，将两个序列中没划分完的起始点和终止点入栈。重复这个过程,直到栈为空时完成排序。
 

void quicksort(int *arr, int low, int high)
{
	stack<int> stk;
	if(low < high)
	{
		int pos = partation(arr, low, high);
		if(pos-1 > low)
		{
			stk.push(low);
			stk.push(pos-1);
		}
		if(pos+1 < high)
		{
			stk.push(pos+1);
			stk.push(high);
		}
		
		while(!stk.empty())
		{
			int h = stk.top();
			stk.pop();
			int l = stk.top();
			stk.pop();
			
			pos = partation(arr, l, h);
			if(pos-1 > l)
			{
				stk.push(l);
				stk.push(pos-1);
			}
			if(pos+1 < h)
			{
				stk.push(pos+1);
				stl.push(h);
			}
		}
	}
}

归并排序：将两个或两个以上的有序表组合一个新的有序表称为“归并”。先使每个子序列有序，再归并使子序列段有序，最后得到完全有序的序列。

通常是采用递归实现，可是如果待排序序列过大，递归可能会导致栈溢出。。所以需要了解一下对于归并排序的非递归实现，    
算法思想：我们先假设数组的每一个元素是有序的，然后第一次以有序序列长度k为1的进行两两序列比较，接着下一次以有序序列长度k为2进行两两序列比较，一直这样直到有序序列长度大于数组长度时，排序完成。这过程相当于递归实现时，先分治后合并中的“后合并”。

 

实现如下：

#include <iostream>
#include <stdlib.h>
using namespace std;

//将两个有序序列排序为一个有序序列
void sort(int *arr, int *tmp, int start, int mid, int end)
{
	int i = start;
	int j = mid + 1;
	int k = 0;
	int h = 0;
	for (k = i; i <= mid && j <= end; k++)
	{
		if (arr[i] < arr[j])
		{
			tmp[k] = arr[i++];
		}
		else
		{
			tmp[k] = arr[j++];
		}
	}

	if (i <= mid)
	{
		for( h = 0; h <= mid - i; h++)
		{
			tmp[k+h] = arr[h + i];
		}
	}
	else
	{
		for (h = 0; h <= end - j; h++)
		{
			tmp[k+h] = arr[h + j];
		}
	}
}

//一趟归并排序
void Merge(int *arr, int *tmp, int k, int length)
{
	int i = 0;
	while (i <= length - 2 * k)
	{
		sort(arr, tmp, i, i + k - 1, i + 2 * k - 1);
		i += 2 * k;
	}

	if (i < length - k)//当不够两个有序序列归并时，但如果还剩超过k个元素,也进行归并排序；
	{
		sort(arr, tmp, i, i + k - 1, length - 1);
	}
	else//否则将剩余元素复制到中间数组里
	{
		for (int j = i; j < length; j++)
		{
			tmp[j] = arr[j];
		}
	}

	for (int l = 0; l < length; l++)//一趟归并完成后，将中间数组的排序结构复制到原数组，继续下一趟归并，直到完全有序
	{
		arr[l] = tmp[l];
	}
}


void MergeSort(int *arr, int length)
{
	if (NULL!=arr && length>0)
	{
		int *tmp_arr = (int *)malloc(sizeof(int )*length);
		int k = 1;
		while (k < length)
		{
			Merge(arr, tmp_arr, k, length);
			k *= 2;
		}
	}

}
void print(int *arr, int length) {
	int i;
	for (i = 0;i<length;i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}
int main()
{
	const int N = 10;
	int arr[N] = { 1,3,5,6,8,2,4,7,9,10 };

	MergeSort(arr, N);
	print(arr, N);
}