C++排序算法

#include
using namespace std;
#include
//打印模板
template
void Print(T* arr, int n)
{
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
	cout << endl;
}
//交换模板
template
void Swap(T& a, T& b)
{
	T temp = a;
	a = b;
	b = temp;
}
//冒泡排序
template
void BubbleSort(T* arr, int n)
{
//flag为标志
	bool flag = true;
	for (int i = 0; i < n - 1&&flag; i++)
	{
		flag = false;
		//当以下代码中，没出现交换时，说明后面的数组已经有序，故flag为false，跳出循环
		for (int j = 0; j < n - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(arr[j], arr[j + 1]);
				flag = true;
			}
		}
	}
}
//选择排序
template
void SelectSort(T* arr, int n)
{
	int min = 0;
	for (int i = 0; i < n - 1; i++)
	{
		min = i;
		for (int j = i + 1; j < n; j++)
		{
			if (arr[min] >arr[j])
				min = j;
		}
		if (min != i)
			Swap(arr[min], arr[i]);
	}
}
//插入排序
template
void InsertSort(T* arr, int n)
{
	T temp;
	int j = 0;
	for (int i = 1; i < n; i++)
	{
		if (arr[i] < arr[i - 1])
		{
			temp = arr[i];
			//数组往后移动，腾出位置插入temp
			for (j = i - 1; j >= 0 && arr[j] > temp; j--)
				arr[j + 1] = arr[j];
			arr[j + 1] = temp;
		}
	}
}
//快速排序
template
void QSort(T* arr, int low, int high)
{
	if (low >= high)
		return;
	int i = low;
	int j = high + 1;
	//选择第一个元素作为枢纽元，效率较低，可更改为其他枢纽元以提高运行速度
	T key = arr[low];
	while (1)
	{
		while (arr[++i] < key)
		{
			if (i == high)
				break;
		}
		while (arr[--j] > key)
		{
			if (j == low)
				break;
		}
		if (i >= j)
			break;
		Swap(arr[i], arr[j]);
	}
	Swap(arr[low], arr[j]);
	QSort(arr, low, j - 1);
	QSort(arr, j + 1, high);
}
//希尔排序
template
void ShellSort(T* arr, int n)
{
	T temp;
	int increment = n;
	int j;
	do
	{
	//每次循环都修改步长，使步长逐渐变小，直到步长小于1
		increment = increment / 3 + 1;
		for (int i = increment; i < n; i++)
		{
			if (arr[i] < arr[i - increment])
			{
				temp = arr[i];
				for (j = i - increment; j >= 0 && arr[j] > temp; j -= increment)
					arr[j + increment] = arr[j];
				arr[j + increment] = temp;
			}
		}
	} while (increment < 1);
}
//堆调整，将节点下沉，调整成一个最大堆
template
void HeapAdjust(T* arr, int node, int size)
{
	if (node >= size)
		return;
	int max = node;
	int left = node * 2 + 1;
	int right = node * 2 + 2;
	if (left < size && arr[max] < arr[left])
		max = left;
	if (right < size && arr[max] < arr[right])
		max = right;
	if (node != max)
	{
		Swap(arr[max], arr[node]);
		HeapAdjust(arr, max, size);
	}
}
//堆排序
template
void HeapSort(T* arr, int n)
{
	//将数组调整为一个最大堆
	for (int i = (n - 1) / 2; i >= 0; i--)
	{
		HeapAdjust(arr, i, n);
	}
	for (int i = n - 1; i >= 0; i--)
	{
		//将最大节点调到数组后面
		Swap(arr[0], arr[i]);
		//再调整使堆保持为最大堆
		HeapAdjust(arr, 0, i);
	}
}
//归并
template
void Merge(T* arr, int start, int mid, int end)
{
	T* temp = new T[end - start + 1];
	int left = start;
	int right = mid + 1;
	int index = 0;
	while (left <= mid && right <= end)
	{
		if (arr[left] < arr[right])
			temp[index++] = arr[left++];
		else
			temp[index++] = arr[right++];
	}
	while (left <= mid)
		temp[index++] = arr[left++];
	while (right <= end)
		temp[index++] = arr[right++];
	for (int i = 0; i < index; i++)
		arr[i + start] = temp[i];
	delete[]temp;
}
//归并排序
template
void MergeSort(T* arr, int start, int end)
{
	if (start >= end)
		return;
	int mid = (start + end) / 2;
	MergeSort(arr, start, mid);
	MergeSort(arr, mid + 1, end);
	Merge(arr, start, mid, end);
}
//桶排序
void BucketSort(int* arr, int n)
{
	int bucket[1000]{ 0 };
	for (int i = 0; i < n; i++)
		bucket[arr[i]]++;
	int j = 0;
	for (int i = 0; i < 1000; i++)
	{
		while (bucket[i])
		{
			arr[j] = i;
			j++;
			bucket[i]--;
		}
	}
}
//获得最大位
int maxbit(int* arr, int n)
{
	int d = 1;
	int p = 10;
	for (int i = 0; i < n; i++)
	{
		while (arr[i] >= p)
		{
			d++;
			p *= 10;
		}
	}
	return d;
}
//基数排序
void RadixSort(int* arr, int n)
{
	int d = maxbit(arr, n);
	int count[10];
	int* temp = new int[n];
	int j, k;
	int radix = 1;
	for (int i = 1; i <= d; i++)
	{
		for (j = 0; j < 10; j++)
			count[j] = 0;
		for (j = 0; j < n; j++)
		{
			k = (arr[j] / radix) % 10;
			count[k]++;
		}
		for (j = 1; j < 10; j++)
			count[j] += count[j - 1];
		for (j = n - 1; j >= 0; j--)
		{
			k = (arr[j] / radix) % 10;
			temp[count[k] - 1] = arr[j];
			count[k]--;
		}
		for (j = 0; j < n; j++)
			arr[j] = temp[j];
		radix *= 10;
	}
	delete[]temp;
}
int main()
{
	int arr[20];
	for (int i = 0; i < 20; i++)
		arr[i] = 1 + rand() % 1000;
	Print(arr, 20);
	//BubbleSort(arr, 20);
	//SelectSort(arr, 20);
	//InsertSort(arr, 20);
	//ShellSort(arr, 20);
	//QSort(arr, 0, 19);
	//HeapSort(arr, 20);
	//MergeSort(arr, 0, 19);
	//BucketSort(arr, 20);
	RadixSort(arr, 20);
	Print(arr, 20);
	return 0;
}