sort.h

经典排序算法

/* @filename Sort.h	v1.0 12/24/2002
//============================================================================
* * 
* * Copyright 2002 Handsome Technologies, Inc. All rights reserved
* *
* * @version 1.0 
* *
* * @author  Victor Cui<[e-mail]>
* *
//============================================================================
* *
* *Description:Sort lib
* *
//============================================================================*/

#ifndef _SORT_H_
#define _SORT_H_

template<class T>
class CSort{
private:
	static void Swap(T &value1, T &value2)
	{
		T temp = value1;
		value1= value2;
		value2 = temp;
	};

	static unsigned Max(T array[], unsigned begin, unsigned end)
	{
		if((end - begin) < 1)
			return begin;

		unsigned iResult;
		T node;
		for(int i = begin; i < end; i++)//"[)"
		{
			if(i == begin)
			{
				node = array[i];
				iResult = i;
			}
			else
			{
				if(array[i] > node)
				{
					iResult = i;
					node = array[i];
				}
			}
		}
		return iResult;
	};

	static unsigned Min(T array[], unsigned begin, unsigned end)
	{
		if((end - begin) < 1)
			return begin;

		unsigned iResult;
		T node;
		for(int i = begin; i < end; i++)//"[)"
		{
			if(i == begin)
			{
				node = array[i];
				iResult = i;
			}
			else
			{
				if(array[i] < node)
				{
					iResult = i;
					node = array[i];
				}
			}
		}
		return iResult;
	};

	static void MergePass(T x[], T y[], int s, int n, bool toUper)
	{// 归并大小为s的相邻段
		int i = 0;
		while (i <= n - 2 * s) {
			// 归并两个大小为s的相邻段
			Merge(x, y, i, i+s-1, i+2*s-1, toUper);
			i = i + 2 * s;
		}
		if (i + s < n) Merge(x, y, i, i+s-1, n-1, toUper);
		else for (int j = i; j <= n-1; j++)
			// 把最后一段复制到y
			y[j] = x[j];
	};

	static void Merge(T c[], T d[], int l, int m, int r, bool toUper)
	{// 把c[l:m]] 和c[m:r] 归并到d [ l : r ] .
		int i = l, // 第一段的游标
			j = m+1, // 第二段的游标
			k = l; // 结果的游标
		//只要在段中存在i和j，则不断进行归并
		while ((i <= m) && (j <= r))
		{
			if (toUper ? c[i] <= c[j] : c[i] > c[j]) 
				d[k++] = c[i++];
			else 
				d[k++] = c[j++];
		}
			// 考虑余下的部分
		if (i > m) 
			for (int q = j; q <= r; q++)
				d[k++] = c[q];
		else 
			for (int q = i; q <= m; q++)
				d[k++] = c[q];
	};

	static void quickSort(T a[], int l, int r, bool toUper)
	{// 排序a [ l : r ]， a[r+1] 有大值
		if (l >= r) return;
		int i = l, // 从左至右的游标
			j = r + 1; // 从右到左的游标
		T pivot = a[l];
		// 把左侧>= pivot的元素与右侧<= pivot 的元素进行交换
		while (true) {
			do {// 在左侧寻找>= pivot 的元素
				i = i + 1;
			} while (toUper ? a[i] < pivot : a[i] > pivot);
			do {// 在右侧寻找<= pivot 的元素
				j = j - 1;
			} while (toUper ? a[j] > pivot : a[j] < pivot);
			if (i >= j) break; // 未发现交换对象
			Swap(a[i], a[j]);
		}
		// 设置p i v o t
		a[l] = a[j];
		a[j] = pivot;
		quickSort(a, l, j-1, toUper); // 对左段排序
		quickSort(a, j+1, r, toUper); // 对右段排序
	};

public:
	//quick sort
	static void QSort(T array[], unsigned size, bool toUper)
	{
		if(size <= 1)
			return;//over
		quickSort(array, 0, size - 1, toUper);

	};

	static void MergeSort(T array[], unsigned size, bool toUper)
	{
		T *b = new T [size];
		int s = 1; // 段的大小
		while (s < size) {
			MergePass(array, b, s, size, toUper); // 从a归并到b
			s += s;
			MergePass(b, array, s, size, toUper); // 从b 归并到a
			s += s;
		}
	};
	
	static void InsertSort(T array[], unsigned size, bool toUper)
	{
		if(size <= 1)
			return;
		T t;
		int j;
		for (int i = 1; i < size; i++) 
		{
			t = array[i];
			for (j = i-1; j >= 0 && (toUper ? t < array[j] : t > array[j]); j--)
				array[j+1] = array[j];

			array[j+1] = t;
		}
	};

	static void SelectSort(T array[], unsigned size, bool toUper)
	{
		if(size <= 1)
			return;
		for(int i = 0; i < size; i++)
		{
			if((toUper ? Max(array, 0, size - i) : Min(array, 0, size - i)) != (size -i - 1))
				Swap(array[index], array[size - i - 1]);
		}
	};

	static void BubbleSort(T array[], unsigned size, bool toUpper)/* if is true, result such as 1 ,2 3 )*/
	{
		if(size <= 1)
			return;	//over
		bool bSorted = false;
		for(unsigned i = 0; i < size; i++)
		{
			if(bSorted)
				break;
			bSorted = true;
			for(unsigned j = 1; j < size - i; j++)
			{
				if(toUpper ? array[j] < array[j - 1] : array[j] > array[j - 1])
				{
					Swap(array[j], array[j - 1]);
					if(bSorted)
						bSorted = false;
				}
			}
		}
	};
};

#endif