일반적인 정렬 알고리즘(빠른 정렬, 삽입 정렬, 힐 정렬, 무더기 정렬, 거품 정렬, 선택 정렬, 병합 정렬)

#pragma once
#include<cassert>
#include<iostream>

template<class T>
class Sort
{
public:
	Sort(T* a,size_t size);
public:
	//    
	void InsertSort();
	void ShellSort();
	//    
	void SelectSort();
	void HeapSort();
	//    
	void BubbleSort();
	void QuickSort();
	//    
	void MergeSort();
	//    
	void LSDSort();
	void MSDSort();
	//    
	void CountSort();
protected:
	//  
	void _CreateHeap()
	{
		int root = (_size - 2) / 2;
		for (int i = root; i >= 0; --i){
			AdjustDown(i,_size);
		}
	}
	//    
	void AdjustDown(int root, size_t size)
	{
		int child = root * 2 + 1;
		while (child<size){
			if (child + 1 < size&&_array[child] > _array[child + 1]){
				child++;
			}
			if (_array[root] > _array[child]){
				std::swap(_array[root], _array[child]);
				root = child;
				child = root * 2 + 1;
			}
			else{
				break;
			}
		}
	}
	//      
	size_t _PartQuickSort(size_t l,size_t r)
	{
		size_t key = l;
		if (l == r)
			return key;
		T tmp = _array[l];
		size_t i = l;
		size_t j = r;
		while (i < j){
			while (i < j && _array[j] >= tmp){
				j--;
			}
			if (i <j){
				std::swap(_array[i],_array[j]);
				key = j;
			}
			while (i < j && _array[i] <= tmp){
				i++;
			}
			if (i < j){
				std::swap(_array[i],_array[j]);
				key = i;
			}
		}
		return key;
	}
	void _QuickSort(size_t left, size_t right)
	{
		if (left < right){
			size_t mid = _PartQuickSort(left, right);
			_QuickSort(left,mid-1);
			_QuickSort(mid+1,right);
		}
	}
	//        
	void _Merge(size_t first,size_t last,size_t mid)
	{             //2^1-1    2^2-1       2^3-1
		T one = first;
		T two = mid+1;
		if (first == last)
			two = mid;
		
		T* NewArray = new T[last - first + 1];
		size_t k = 0;
		while(one<=mid && two<=last){
			if (_array[one] < _array[two]){
				NewArray[k] = _array[one];
				one++;
			}
			else{
				NewArray[k] = _array[two];
				two++;
			}
			k++;
		}
			while (two<=last){
			NewArray[k] = _array[two];
				++k;
				++two;
			}
			while (one<=mid){
				NewArray[k] = _array[one];
				++k;
				++one;
			}
		for (size_t i = first,j = 0; i <= last; ++i,++j){
		std::swap(NewArray[j],_array[i]);
		}
	}
	void _MergeSort(size_t first,size_t last,size_t mid)
	{
		if (first < last){
			_MergeSort(first, mid, first + ((mid - first) >> 1));
			_MergeSort(mid + 1, last, (   mid + 1 + ((last - mid - 1)>> 1)));
		}
		_Merge(first, last, mid);
	}
	size_t _Digit()//        
	{
		if (_size==0)
			return 0;
		int max = _array[0];
		for (size_t i = 0; i < _size;++i)
		{
			if (_array[i]>max)
				max = _array[i];
		}
		size_t i = 1;
		if (max%10!=0){
			i++;
			max /= 10;
		}
		return i;
	}
protected:
	T* _array;
	size_t _size;
};
template<class T>
Sort<T>::Sort(T* a, size_t size)
:_array(a)
, _size(size)
{}
template<class T>
void Sort<T>::InsertSort()
{
	assert(_array);
	if (_size == 1)
		return;
	for (size_t i = 0; i <= _size - 2; ++i){
		int end = i;
		T tmp = _array[i + 1];
		while (end>=0){
			if (_array[end]>tmp){
				_array[end + 1] = _array[end];
				end--;
			}
			else
				break;
		}
		_array[end + 1] = tmp;
	}
}
template<class T>
void Sort<T>::ShellSort()
{
	size_t gap = _size/3+1;//gap   ，   
	while (gap > 0){
		for (size_t i = 0; i < _size - gap; ++i){
			int j = i;
			while (j>=0){
				if (_array[j]>_array[j + gap]){
					std::swap(_array[j],_array[j + gap ]);
					j -= gap;
				}
				else
					break;
			}
		}
		gap--;
	}
}
template<class T>
void Sort<T>::SelectSort()
{
	for (size_t i = 0; i < _size - 1; ++i){
		size_t j = i + 1;
		while (j <= _size-1){
			if (_array[i]>_array[j]){
				std::swap(_array[i], _array[j]);
			}
			j++;
		}
	}
}
template<class T>
void Sort<T>::HeapSort()
{
	_CreateHeap();
	size_t size = _size;
	for (size_t i = _size - 1; i > 0; --i){
		std::swap(_array[0], _array[i]);
		AdjustDown(0,--size);
	}
}
template<class T>
void Sort<T>::BubbleSort()
{
	for (size_t i = _size-1; i > 0; --i){
		for (size_t j = 0; j < i; ++j){
			if (_array[j] > _array[j + 1]){
				std::swap(_array[j],_array[j+1]);
			}
		}
	}
}
template<class T>
void Sort<T>::QuickSort()
{
	size_t left = 0;
	size_t right = _size - 1;
	_QuickSort(left,right);
}
template<class T>
void Sort<T>::MergeSort()
{
	size_t first = 0;
	size_t last = _size-1;
	//size_t mid = (first+last) / 2;
	size_t mid = first + ((last - first) >> 1);
	_MergeSort(first,last,mid);
}
template<class T>
void Sort<T>::LSDSort()//    （    ）
{
	int Digit = _Digit();
	int digit = 1;
	int bit = 1;
	int* tmp = new int[_size];
	while (digit<=Digit){
		int Counts[10] = { 0 };
		int Start[10] = { 0 };
		for (size_t i = 0; i < _size; ++i){
			Counts[(_array[i]/bit )% 10]++;
		}
		
		for (size_t i = 1; i < 10; ++i){
			Start[i] = Start[i - 1] + Counts[i - 1];
		}
		for (size_t i = 0; i < _size; ++i){
			size_t index = (_array[i] / bit ) % 10;
			tmp[Start[index]++] = _array[i];
		}
	std::swap(tmp, _array);
	digit++;
	bit *= 10;
	}
	delete[] tmp;
}
template<class T>
void Sort<T>::CountSort()//    
{
	int max = _array[0];
	int min = _array[0];
	for (size_t i = 0; i < _size; ++i){
		if (_array[i]>max)
			max = _array[i];
		if (_array[i] < min)
			min = _array[i];
	}
	int* count = new int[max-min+1];
	memset(count, 0, sizeof(int)*(max-min+1));
	for (size_t i = 0; i <_size; ++i){
		count[_array[i] - min]++;
	}
	for (size_t i = 0,j=0; i < max - min + 1; ++i){
		while (count[i])
		{
			_array[j++] = i+min;
			/*std::cout << i;*/
			count[i]--;
		}
	}
	std::cout << std::endl;
}

#include<iostream>
#include"Sort.h"
#include<string>
#include<string.h>

void InsertSortTest()
{
	char str[] = "qassdsf";
	//std::cout << str << std::endl;
	//int a = 0;
	//int& b = a;
	//char* p = str;
	//char*&q = str;
	Sort<char> s1(str,strlen(str));
	s1.InsertSort();
	std::cout << str << std::endl;
}

void ShellSortTest()
{
	int a[] = {9,1,5,8,3,7,4,6,2};
	Sort<int> s1(a, sizeof(a)/sizeof(a[0]));
	/*s1.InsertSort();
	for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i){
		std::cout << a[i] << "  ";
	}
	std::cout << std::endl;*/
	s1.ShellSort();
	for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i){
		std::cout << a[i] << "  ";
	}
	std::cout << std::endl;
}
void SelectSortTest()
{
	int a[] = { 9, 1, 5, 8, 3, 7, 4, 6, 2 };
	Sort<int> s1(a, sizeof(a) / sizeof(a[0]));
	s1.SelectSort();
	for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i){
		std::cout << a[i] << "  ";
	}
	std::cout << std::endl;
}
void HeapSortTest()
{
	int a[] = { 9, 1, 5, 8, 3, 7, 4, 6, 2 };
	Sort<int> s1(a, sizeof(a) / sizeof(a[0]));
	s1.HeapSort();
	for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i){
		std::cout << a[i] << "  ";
	}
	std::cout << std::endl;
}
void BubbleSortTest()
{
	int a[] = { 9, 1, 5, 8, 3, 7, 4, 6, 2 };
	Sort<int> s1(a, sizeof(a) / sizeof(a[0]));
	s1.BubbleSort();
	for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i){
		std::cout << a[i] << "  ";
	}
	std::cout << std::endl;
}
void QuickSortTest()
{
	int a[] = { 3, 1, 5, 8, 9, 7, 4, 6, 2 };
	Sort<int> s1(a, sizeof(a) / sizeof(a[0]));
	s1.QuickSort();
	for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i){
		std::cout << a[i] << "  ";
	}
	std::cout << std::endl;
}
void MergeSortTest()
{
	int a[] = { 1, 3, 5, 8, 9, 2, 4, 6, 7 };
	Sort<int> s1(a, sizeof(a) / sizeof(a[0]));
	s1.MergeSort();
	for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i){
		std::cout << a[i] << "  ";
	}
	std::cout << std::endl;
}
void LSDSortTest()
{
	int a[] = { 73, 22, 93, 43, 5598, 14, 28, 65, 39, 81 };
	Sort<int> s1(a, sizeof(a) / sizeof(a[0]));
	s1.LSDSort();
	for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i){
		std::cout << a[i] << "  ";
	}
	std::cout << std::endl;
}
void CountsSortTest()
{
	int a[] = { 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 };
	Sort<int> s1(a, sizeof(a) / sizeof(a[0]));
	s1.CountSort();
	for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i){
		std::cout << a[i] << "  ";
	}
	std::cout << std::endl;
}
int main()
{
	//InsertSortTest();
	//ShellSortTest();
	//SelectSortTest();
	//HeapSortTest();
	//BubbleSortTest();
	//QuickSortTest();
	//MergeSortTest();
	//LSDSortTest();
	CountsSortTest();

	system("pause");
	return 0;
}