sort.h

含有7种排序算法

#ifndef SORTCLASS___
#define SORTCLASS___


#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <time.h>
#include <vector>

using namespace std;
#include "timer.h"

const int INSERTION_SORT_BOUND  = 16;
typedef int (*CMPFUN)(int, int);
int cmpfun(int a, int b);

static void swap(int *a, int *b);

const char COMBO = 'c';
const char QUICK = 'q';
const char MIN = 'm';
const char BUBBLE = 'b';
const char INSERTION = 'i';
const char SHELL = 's';
const char SELECTION = 'e';


const int MAXIMUM = 20000; //maximum places to test in DetermineFastest()


class Sort
{
protected:
	
	char fastest; 
	char *returnval;
	
	int bubbletime;
	int insertiontime;
	int shelltime;
	int selectiontime;
	int mintime;
	int combotime;
	int quicktime;

	bool bubbleflag;
	bool insertionflag;
	bool shellflag;
	bool selectionflag;
	bool minflag;
	bool comboflag;
	bool quickflag;

	void HelperHeapSort(int This[], CMPFUN fun_ptr, unsigned int first, unsigned int the_len)
	{
		unsigned int half;
		unsigned int parent;
		
		if (the_len <= 1)
			return;
		
		half = the_len >> 1;
		for (parent = half; parent >= 1; --parent)
		{
			int temp;
			int level = 0;
			unsigned int child;
			
			child = parent;
			while (child <= half)
			{
				++level;
				child += child;
				if ((child < the_len) &&
					((*fun_ptr)(This[first + child], This[first + child - 1]) > 0))
					++child;
			}
			temp = This[first + parent - 1];
			for (;;)
			{
				if (parent == child)
					break;
				if ((*fun_ptr)(temp, This[first + child - 1]) <= 0)
					break;
				child >>= 1;
				--level;
			}
			for (;level > 0; --level)
			{
				This[first + (child >> level) - 1] =
					This[first + (child >> (level - 1)) - 1];
			}
			This[first + child - 1] = temp;
		}
		
		--the_len;
		do
		{
			int temp;
			int level = 0;
			unsigned int child;
			
			temp = This[first + the_len];
			This[first + the_len] = This[first];
			This[first] = temp;
			
			child = parent = 1;
			half = the_len >> 1;
			
			while (child <= half)
			{
				++level;
				child += child;
				if ((child < the_len) &&
					((*fun_ptr)(This[first + child], This[first + child - 1]) > 0))
					++child;
			}
			
			for (;;)
			{
				if (parent == child)
					break;
				if ((*fun_ptr)(temp, This[first + child - 1]) <= 0)
					break;
				child >>= 1;
				--level;
			}
			
			for (;level > 0; --level)
			{
				This[first + (child >> level) - 1] =
					This[first + (child >> (level - 1)) - 1];
			}
			This[first + child - 1] = temp;
		} while (--the_len >= 1);
	}
	
	
	void Qsort(int This[], CMPFUN fun_ptr, unsigned int first, unsigned int last)
	{
		unsigned int stack_pointer = 0;
		int first_stack[32];
		int last_stack[32];
		
		for (;;)
		{
			if (last - first <= INSERTION_SORT_BOUND)
			{
				unsigned int indx;
				int prev_val = This[first];
				int cur_val;
				
				for (indx = first + 1; indx <= last; ++indx)
				{
					cur_val = This[indx];
					if ((*fun_ptr)(prev_val, cur_val) > 0)
					{
						unsigned int indx2;
						This[indx] = prev_val;
						
						for (indx2 = indx - 1; indx2 > first; --indx2)
						{
							int temp_val = This[indx2 - 1];
							if ((*fun_ptr)(temp_val, cur_val) > 0)
							{
								This[indx2] = temp_val;
							}
							else
								break;
						}
						This[indx2] = cur_val;
					}
					else
					{
						prev_val = cur_val;
					}
				}
			}
			else
			{
				int pivot;
				{
					int temp;
					unsigned int med = (first + last) >> 1;
					temp = This[first];
					if ((*fun_ptr)(temp, This[last]) > 0)
					{
						This[first] = This[last]; This[last] = temp;
					}
					temp = This[med];
					if ((*fun_ptr)(This[first], temp) > 0)
					{
						This[med] = This[first]; This[first] = temp;
					}
					temp = This[last];
					if ((*fun_ptr)(This[med], temp) > 0)
					{
						This[last] = This[med]; This[med] = temp;
					}
					pivot = This[med];
				}
				{
					unsigned int up;
					{
						unsigned int down;
						down = first;
						up = last;
						for (;;)
						{
							do
							{
								++down;
							} while ((*fun_ptr)(pivot, This[down]) > 0);
							
							do
							{
								--up;
							} while ((*fun_ptr)(This[up], pivot) > 0);
							
							if (up > down)
							{
								int temp;
								temp = This[down]; This[down]= This[up]; This[up] = temp;
							}
							else
								break;
						}
					}
					{
						unsigned int len1; 
						unsigned int len2; 
						len1 = up - first + 1;
						len2 = last - up;
						if (len1 >= len2)
						{
							if ((len1 >> 5) > len2)
							{
								HelperHeapSort(This, fun_ptr, first, len1);
							}
							else
							{
								first_stack[stack_pointer] = first; 
								last_stack[stack_pointer++] = up;
							} 
							first = up + 1;
						}
						else
						{
							if ((len2 >> 5) > len1)
							{
								HelperHeapSort(This, fun_ptr, up + 1, len2);
							}
							else
							{
								first_stack[stack_pointer] = up + 1; 
								last_stack[stack_pointer++] = last;
							}
							last = up;
						}
					}
					continue;
				}
				
			}
			if (stack_pointer > 0)
			{
				first = first_stack[--stack_pointer];
				last = last_stack[stack_pointer];
			}
			else
				break;
			}
	}
  
public:   

	Sort()
	{
		fastest = QUICK; 		
		bubbletime = 0;
		insertiontime = 0;
		shelltime = 0;
		selectiontime = 0;
		mintime = 0;
		combotime = 0;
		quicktime = 0;
		returnval = new char[200];
		bubbleflag = false;
		insertionflag = false;
		shellflag = false;
		selectionflag = false;
		minflag = false;
		comboflag = false;
		quickflag = false;
	}
	~Sort()
	{
		delete returnval;
	}
	
	void QuickSort(int v[], unsigned n)
    {
		unsigned i, j, ln, rn;
		while (n > 1)
        {
			swap(&v[0], &v[n/2]);
			for (i = 0, j = n; ; )
            {
				do
				--j;
				while (v[j] > v[0]);
				do
				++i;
				while (i < j && v[i] < v[0]);
				if (i >= j)
					break;
				swap(&v[i], &v[j]);
			}
			
			swap(&v[j], &v[0]);
			ln = j;
			rn = n - ++j;
			if (ln < rn)
			{
				QuickSort(v, ln);
				v += j;
				n = rn;
			}
			else
			{
				QuickSort(v + j, rn);
				n = ln;
			}
		}
	}
	
	void MinSort(int* array, int n)
    {
		int i, j, temp_index;
		int min;
		for (i=0; i < n-1; ++i)
		{
			temp_index = i;
			min = array[i];
			for (j = i+1; j < n; ++j)
			{
				if (array[j] < min)
				{
					temp_index = j;
					min = array[j];
				}
			}
			array[temp_index] = array[i];
			array[i] = min;
		}
	}
	
	void BubbleSort(int* array, int n)
    {
		int i, j;
		int temp;
		for (i = 0; i < n-1; ++i)
		{
			for (j = i+1; j > 0; --j)
			{
				if (array[j] < array[j-1])
				{
					temp = array[j];
					array[j] = array[j-1];
					array[j-1] = temp;
				}	
			}	
		}
	}
	
	void InsertionSort(int* array, int n)
	{
		int i, j;
		int temp;
		for (i=1; i < n; ++i)
		{
			temp = array[i];
			j = i-1;
			while ((j >= 0) && (temp < array[j]))
			{
				array[j+1] = array[j];
				j--;
			}
			array[j+1] = temp;
		}
	}
	
	void ShellSort(int* array, int n)
    {
		int i, j, k, s, gap_cnt;
		int temp;
		int gaps[5];
		gaps[0] = 9; gaps[1] = 5; gaps[2] = 3; gaps[3] = 2; gaps[4] = 1;
		for (gap_cnt = 0; gap_cnt < 5; gap_cnt++)
		{
			k = gaps[gap_cnt];
			s = -k;
			for (i = k; i < n; ++i)
			{
				temp = array[i];
				j = i-k;
				if (s == 0)
				{
					s = -k;
					s++;
					array[s] = temp;
				}
				while (temp < array[j] && j >= 0 && j <= n) 
				{
					array[j+k] = array[j];
					j = j-k;
				}
				array[j+k] = temp;
			}
		}