sort.h

数组排序算法-----这个程序的头文件中包含四种排序方法：泡沫排序法

/*
	Author:	David Martinjak
	Date:	December, 2001
	Email:	[e-mail]

	This is a class header file that you can implement
	in a driver program (such as the included sortmain.cpp)
	to sort arrays of multiple types.  

	This software is open source code, and is provided
	as-is with no warranties whatsoever.  Please feel
	free to make modifications and use for your own
	intents and purposes.

  */

#include <stdlib.h>
#include <iostream.h>


template <class T>
class sort {
public:
	sort(int);								// constructor
	void bubble(T array[]);					// bubble sort
	void insertion(T array[]);				// insertion sort
	void quick(T array[], int, int);		// quick sort
	void selection(T array[]);				// selectioni sort

private:
	int size;
};



template <class T>
sort<T>::sort(int s) {
	if (s < 0) {			// make sure the size is valid
		cerr << "** An invalid array size was entered." << endl;
		exit(-1);
		return;
	}

	size = s;				// if the size is valid, assign it 
}


template <class T>
void sort<T>::bubble(T array[]) {
	
	T temp;
	int last = size - 1;
	bool sorted = true;

	do {
		sorted = true;
		for (int i = 0; i < last; i++) {

			/* 
				swap elements if the higher index element is 
				greater than the smaller index element
			 */

			if (array[i] > array[i + 1]) {	
				temp = array[i];
				array[i] = array[i + 1];
				array[i + 1] = temp;
				sorted = false;
			}

		}

		last--;
	} while (!sorted);

}


template <class T>
void sort<T>::insertion(T array[]) {

	T cVal;		// current value being examined
	
	for (int i = 1; i < size; i++) {

		cVal = array[i];
		for (int n = i - 1; n >= 0 && cVal < array[n]; n--) {
			array[n + 1] = array[n];
		}

		array[n + 1] = cVal;

	}	// end for loop

}


template <class T>
void sort<T>::quick(T array[], int llimit, int rlimit) {

	T temp;
	int left = llimit;
	int right = rlimit;
	int pivot = (left + right) / 2;	// find the median
	T median = array[pivot];


	do {

		while ((array[left] < median) && (left < rlimit)) {
			left++;
		}

		while ((median < array[right]) && (right > llimit)) {
			right--;
		}

		if (left <= right) {

			// swap elements
			temp = array[left];
			array[left] = array[right];
			array[right] = temp;
			left++;
			right--;
		}

	} while (left <= right);


	if (llimit < right) {
		sort<T>::quick(array, llimit, right);
	}


	if (left < rlimit) {
		sort<T>::quick(array, left, rlimit);
	}

}


template <class T>
void sort<T>::selection(T array[]) {

	T temp;
	int min;

	for (int i = 0; i < size - 1; i++) {
		min = i;

		for (int n = i + 1; n < size; n++) {
			if (array[n] < array[min]) {
				min = n;
			}

			temp = array[min];
			array[min] = array[i];
			array[i] = temp;
		}
	}

}