一、冒泡排序

template<class T>
inline void CMySort_Array<T>::Bubble_sort(T arr[],int len)
{
	int i, j, tempval;
	for (i = len-1; i > 0; i--)
		for (j = 0; j < i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				tempval = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tempval;
			}
		}
}

二、选择排序

template<class T>
inline void CMySort_Array<T>::Selection_sort(T arr[], int len)
{
	int i, j, serial, tempval;
	for (j = 0; j < len - 1; j++)
	{
		serial = j;
		for (i = j + 1; i < len; i++)
		{
			if (arr[serial] > arr[i])serial = i;
		}
		tempval = arr[serial];
		arr[serial] = arr[j];
		arr[j] = tempval;
	}
}

三、插入排序

template<class T>
inline void CMySort_Array<T>::Insertion_Sort(T arr[], int len)
{
	int j, tempval;
	for (int i = 1; i < len; i++)
	{
		tempval = arr[i];
		j = i - 1;
		while (j >= 0 && tempval < arr[j])
		{
			arr[j + 1] = arr[j];
			j -= 1;
		}
		arr[j + 1] = tempval;
	}
}

四、希尔排序

template<class T>
inline void CMySort_Array<T>::Shell_Sort(T arr[], int len)
{
	int j, tempval;
	int jump = len >> 1;
	while (jump != 0)
	{
		for (int i = jump; i < len; i++)
		{
			tempval = arr[i];
			j = i - jump;
			while (j >= 0 && tempval < arr[j])
			{
				arr[j + jump] = arr[j];
				j -= jump;
			}
			arr[j + jump] = tempval;
		}
		jump >>= 1;
	}
}

五、快速排序

1、这里调用_Quick_Sort(arr, 0, len-1);的目的是定义对象后方便使用这个算法

template<class T>
inline void CMySort_Array<T>::Quick_Sort(T arr[], int len)
{
	_Quick_Sort(arr, 0, len-1);
}

2、上面调用的函数（_Quick_Sort(arr, 0, len-1);）的代码，真正的快排代码

template<class T>
inline void CMySort_Array<T>::_Quick_Sort(T arr[], int low, int hight)
{
	int L = arr[low];//标杆值
	int head = low + 1;//期望指的数比标杆小
	int tail = hight;//期望指的数比标杆大

	if (low >= hight)return;//表示只有一个元素，该元素无需定位

	int tempval;
	while (head<=tail)
	{
		while (head <= tail && arr[head] <= L)head++;
		while (head <= tail && arr[tail] >= L)tail--;
		if (head < tail)
		{
			tempval = arr[head];
			arr[head] = arr[tail];
			arr[tail] = tempval;
			head++;
			tail--;
		}
	}
	arr[low] = arr[tail];
	arr[tail] = L;
	_Quick_Sort(arr, low, tail - 1);
	_Quick_Sort(arr, tail + 1, hight);
}

六、归并排序

1、这里调用_Merge_Sort_Recursion(arr, 0, len - 1);的目的是定义对象后方便使用这个算法

template<class T>
inline void CMySort_Array<T>::Merge_Sort(T arr[], int len)
{
	_Merge_Sort_Recursion(arr, 0, len - 1);
}

2、归操作代码

template<class T>
inline void CMySort_Array<T>::_Merge_Sort_Recursion(T arr[], int left, int right)
{
	//归操作
	if (left >= right)return;//只有一个元素
	int mid = left + ((right - left) >> 1);
	_Merge_Sort_Recursion(arr, left, mid);//左区间
	_Merge_Sort_Recursion(arr, mid+1, right);//右区间

	//并操作
	_Merge_Sort_Merge(arr, left, mid, right);
}

3、并操作代码

template<class T>
inline void CMySort_Array<T>::_Merge_Sort_Merge(T arr[], int left, int mid, int right)
{
	//准备一个合并用的辅助数组
	int length = right - left + 1;
	int* pDate = new int[length];

	//合并
	int low = left;//表示左区间最小值
	int hight = mid + 1;//表示右区间最小值
	int index = 0;
	while (hight <= right && low <= mid)//表示左右区间存在
	{
		while (hight <= right && arr[low] > arr[hight])//表示右区间最小值要小
		{
			pDate[index] = arr[hight];
			index++;
			hight++;
		}
		while (low <= mid && arr[low] <= arr[hight])//表示左区间最小值要小
		{
			pDate[index] = arr[low];
			index++;
			low++;
		}
	}

	//到这一步，证明有一个区间是合并进辅助数组了
	if (hight <= right)//右区间还没有合并完
		memmove(&pDate[index], &arr[hight], sizeof(T) * (right - hight + 1));
	if (low <= mid)//左区间还没有合并完
		memmove(&pDate[index], &arr[low], sizeof(T) * (mid - low + 1));

	//辅助空间合并完成之后拷贝回原始数组
	memmove(&arr[left], pDate, sizeof(T) * length);
	delete[] pDate;
}