sort.cpp

将数组分为小块进行插入排序

#include <iostream>
#include <stdlib.h>
#include <climits>
#include <ctime>
#include <fstream>

using namespace std;

#define N_MAX 200000

void Insertion_sort(int* p, int len);
void Merge(int* p, int r, int s, int t);

int main()
{
	int n, k, i;
	int group, group_size, lastgroup_size;
	double runtime;
	char* filename = "output.txt";
			
	int A[N_MAX];
	
	ofstream output(filename);
	
	srand(time(0));
	cout << "Please input n & k :";
	cin >> n;
	cin >> k;
	
	runtime = double(clock()) / CLOCKS_PER_SEC;
	group = n / k;
	group_size = k;
	
	// Generating n random numbers within 0 ~ RAN_MAX - 1
	output << "n=" << n << " k=" << k << endl << endl;
	output << n <<" unsorted numbers" << endl;		
	for (i=0; i<n; i++)
	{
		A[i] = rand() % n + 1;
		output << A[i] << " ";	
	}
	output << endl << endl;
	
	// Insertion sort each sublist 
	for (i=0; i < group; i++)
		Insertion_sort(&A[group_size * i], group_size);

	// Merge-sort the sublists in pairs
	while (group > 1)
	{
		i = 0;
		while ((group - i) >= 2)
		{
			if (2 == (group - i))
				Merge(A, group_size * i, group_size * (i + 1) - 1, n - 1);
			else
				Merge(A, group_size * i, group_size * (i + 1) - 1, group_size * (i + 2) - 1);
			i = i + 2;
		}
		group = (group % 2) ? (group / 2 + 1) : (group / 2);
		group_size = group_size * 2;
	}
	
	// Output results and display runtime
	output << "final sorted sequence" << endl;
	for (i=0; i<n; i++)
		output << A[i] << " ";
		
	runtime = double(clock()) / CLOCKS_PER_SEC - runtime;
	cout <<"Results written to "<< filename << endl << "Runtime: " << runtime*1000 << "ms" << endl;

}

void Insertion_sort(int* p, int len)
{
	int i, j, v;
	
	for (i=1; i<len; i++)
	{
		v = p[i];
		j = i - 1;
		while ((v < p[j]) && (j >= 0))
		{
			p[j+1] = p[j];
			j--;
		}
		p[j+1] = v;
	}
}

void Merge(int* p, int r, int s, int t)
{
	int n1 = s - r + 1;
	int n2 = t - s;
	
	int L[N_MAX], R[N_MAX];
	int i, j;
	
	for (i=0; i<n1; i++)
		L[i] = p[r+i];
	
	for (i=0; i<n2; i++)
		R[i] = p[s+1+i];
	
	L[n1] = INT_MAX;
	R[n2] = INT_MAX;
	
	i = 0;
	j = 0;
	for (int k=r; k<=t; k++)
	{
		if (L[i]<=R[j])
		{
			p[k] = L[i];
			i++;
		}
		else
		{
			p[k] = R[j];
			j++;
		}
	}
}