最近对排序算法的复习

// 归并排序.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"


void Swap(int &x,int &y) {
	int temp = x;
	x = y;
	y = temp;
}

//将两个表归并为一个,array[low...mid]+array[mid+1...high]->array[low...high]
void merger(int array[],int low,int mid,int high) {		
	int i = low,j = mid+1,p = 0;
	int *R1 = new int[high-low+1];
	if(R1 == NULL)
		cout<<"error"<<endl;
	while(i<=mid && j<=high) {
		if(array[i]<array[j]) {
			R1[p] = array[i];
			i++;
		}else {
			R1[p] = array[j];
			j++;
			}
		p++;
	}
	while(i<=mid) {
		R1[p] = array[i];
		i++;
		p++;
	}
	while(j<=high) {
		R1[p] = array[j];
		j++;
		p++;
	}
	for(i=low,p=0;i<=high;i++,p++) {
		array[i]=R1[p];
	}
}


/*分治法的三个步骤
*设归并排序的当前区间是R[low..high]，分治法的三个步骤是：
*分解：将当前区间一分为二，即求分裂点
*求解：递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序
*组合：将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]
*递归的终结条件：子区间长度为1（一个记录自然有序）
*/
void merger_px(int array[],int low,int high) {
	int mid;
	if(low<high) {
		mid = (low+high)/2;
		merger_px(array,low,mid);
		merger_px(array,mid+1,high);
		merger(array,low,mid,high);
	}
}

int main(int argc, char* argv[])
{
	int array[] = {23,54,12,34,97,60,58,7,73,82};
	for(int i=0;i<10;i++) {
		cout<<array[i]<<" ";
	}
	cout<<endl;

	merger_px(array,0,9);

	for(i=0;i<10;i++) {
		cout<<array[i]<<" ";
	}
	cout<<endl;
	return 0;
}