排序算法C++实现整理

#include 
using namespace std;

template
void selectionSort(T arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		int minIndex = i;
		for (int j = i+1; j < n; j++)
		{
			if (arr[j] < arr[minIndex])
			{
				minIndex = j;
			}
		}
		swap(arr[minIndex], arr[i]);
	}
}

时间复杂度 O(n2) ，如果数据本身就是接近有序的，则插入排序比较快
原理：遍历当前数组，从第一个元素起每个元素都插入到合适的位置。
遍历到第一个元素只看到一个元素，不用管；
遍历到第二个元素需要和第一个元素比较，看下是否需要和第一个元素互换位置；
遍历到第三个元素时，先和第二个元素比较，看是否互换，如果互换再和第一个元素比较，看是否互换；
后面依此类推。。。

//插入排序
template 
void insertSort(T arr[], int n)
{
	//从第二个元素开始，因为第一个元素不需要插入
	for (int i = 1; i < n; i++)
	{
		//在区间[0,i)寻找第i个元素合适的插入位置
		for (int j = i; j > 0; j--)
		{
			if (arr[j] < arr[j-1])
			{
				swap(arr[j], arr[j - 1]);
			}
			else
			{
				break;
			}
		}
	}
}

插入排序优化：
第i个元素往前遍历的时候，先创建一个临时变量e并赋值第i个元素的值，
依次和第i-1，i-2，…，0个元素对比时，如果该元素大于e，则该元素的值赋值给后一个元素，
并继续往前对比，否则结束第i个元素的遍历；

template 
void insetSort2(T arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		T e = arr[i];
		for (int j = i; j > 0; j--)
		{
			if (arr[j - 1] > e)
			{
				arr[j] = arr[j - 1];
			}
			else
			{
				arr[j] = e;
				break;
			}
		}	
	}
}

时间复杂度 O(n2)
遍历第i,i+1，i+2，…，n-1个元素，如果前一个元素更大，则相邻的两个元素互换位置

template 
void bubbleSort(T arr[], int n)
{
	for (int i = 0; i < n-1; i++)
	{
		//冒泡对比的区间[i+1,n)
		for (int j = i+1; j < n; j++)
		{
			if (arr[i] > arr[j])
			{
				swap(arr[i], arr[j]);
			}
		}
	}
}

（1）首先，从数组的首元素开始每隔“步长(间隔)”个元素就挑选一个元素出来作为子数组元素。

（2）然后每个子数组各自进行比较，比较好后，每个子数组都有顺序，进入下一轮，步长(间隔)减少， 再根据步长(间隔)分组进行比较。

（3）重复以上操作，最后就有顺序了。

//希尔排序
template 
void shellSort(T arr[], int n)
{
	int h = 1;
	while (h< n/3)
	{
		h = 3 * h + 1;//计算初始步长
	}

	while (h>=1)
	{
		for (int i = h; i < n; i++)
		{
			T e = arr[i];
			// 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
			for (int j = i; j >= h; j-=h)
			{
				if (arr[j-h] > e)
				{
					arr[j] = arr[j - h];
				}
				else
				{
					arr[j] = e;
					break;
				}
			}
		}
		h = h / 3;
	}
}

时间复杂度（nlogn），个人不喜欢用递归的方式写代码，工作中也几乎没见过递归代码

template 
void merge(T arr[], int left, int mid, int right)
{
	//新建一个临时数组存储arr数组[left，right]区间的值
	T* temp = new T[right - left + 1];
	for (int i = left; i <= right; i++)
	{
		temp[i - left] = arr[i];
	}
	//将temp数组分两个区间,[0, tempMid]和[tempMid+1, right-left]
	int tempMid = (right - left) / 2;
	int leftIndex = 0;
	int rightIndex = tempMid + 1;
	//对arr数组[left，right]区间的值进行排序
	for (int i = left; i <= right; i++)
	{
		if (leftIndex > tempMid)
		{
			//左半区间已全部排序，直接把右半区间的元素加入到arr数组
			arr[i] = temp[rightIndex]++;
		}
		else if (rightIndex > right - left)
		{
			//右半区间已全部排序，直接把左半区间的元素加入到arr数组
			arr[i] = temp[leftIndex++];
		}
		else if (temp[leftIndex] < temp[rightIndex])
		{
			//左半区间的元素更小
			arr[i] = temp[leftIndex++];
		}
		else
		{
			//右半区间的元素更小
			arr[i] = temp[rightIndex++];
		}
	}
	delete[] temp;
}

template 
void mergeSort2(T arr[], int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int mid = (left + right) / 2;
	mergeSort2(arr, left, mid);
	mergeSort2(arr, mid + 1, right);
	merge(arr, left, mid, right);
}

template 
void mergeSort(T arr[], int n)
{
	mergeSort2(arr, 0, n - 1);
}

template 
int partition(T arr[], int left, int right)
{
	//标杆值是flagValue，确认flagValue在数组中的位置
	T flagValue = arr[left];
	int lastSmallIndex = left;// 最后一个小于flagValue的元素的索引
	//[left+1, k]的值均小于flagValue，[k+1， right]的值均大于等于flagValue
	for (int i = left+1; i <= right; i++)
	{
		if (arr[i] < flagValue)
		{
			lastSmallIndex++;
			swap(arr[i], arr[lastSmallIndex]);
		}
	}
	swap(arr[left], arr[lastSmallIndex]);
	return lastSmallIndex;
}

template 
void quickSort2(T arr[], int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int p = partition(arr, left, right);
	quickSort2(arr, left, p-1);
	quickSort2(arr, p + 1, right);
}

template 
void quickSort(T arr[], int n)
{
	quickSort2(arr, 0, n - 1);
}