1、array.cpp文件

在array.cpp文件先定义好初始化函数与打印函数

#include<iostream>
using namespace std;

/*
 * 函数功能：初始化数组
 * 返回值：返回插入元素个数
 */
template <class T>
int initAraay(T a[],int _size = 100)
{
	T elem;
	int i = 0;
	cin>>elem;
	while(elem != -1 && i < _size)
	{
		a[i++] = elem;
		cin >> elem;
	}
	return i;
}

template <class T>
void print(T a[],int _size = 10)
{
	int i=0;
	while(i < _size)
	{
		cout<<a[i++]<<" ";
	}
	cout<<endl;
}

2、折半插入排序

折半插入排序：BInsertSort.cpp

/*
 * 函数功能：折半插入排序(升序）
 * 输入参数：数组a，数组元素个数size
 * 返回值：无
 */

#include "array.cpp"
template <class T>
void BInsertSort(T a[],int size)
{
	T elem;//哨兵元素
	for (int i = 1; i < size; i++)//将a[i]插入有序表a[0,i-1]数组中，通过二分查找获取插入位置
	{	
		elem = a[i];
		int low = 0;
		int high = i-1;

		while (low <= high)
		{  //该循环获取插入位置 high+1
			int middle = (low + high)/2;

			if (elem < a[middle])
			{
				high = middle - 1;
			}
			else
			{
				low = middle + 1;
			}
		}
		
		for ( int j = i-1; j >= high+1; j--) 
		{	//插入位置后的元素后移一个单元
			a[j+1] = a[j];
		}

		a[high+1] = elem;
		print(a,i+1);
	}
}

3、归并排序

归并排序：mergeSort.cpp

#include "array.cpp"

/*
 * 函数功能：二链表升序合并
 * 输入参数：数组a，数组b，a元素个数size1，b元素个数size2
 * 返回值：排序后元素个数
 */
template <class T>
int mergeSort(T a[],int size1,T b[],int size2)
{
	int _size = size1 + size2;
	int pos1 = 0;
	int pos2 = 0;

	for(int i=0;;i++)
	{	//1,2,4,7     3,5,6
		if( a[pos1] > b[pos2])
		{
			//a中元素后移，a[pos1]处插入b[pos2]
			for(int temp_size = size1; temp_size != pos1;temp_size--)
			{
				a[temp_size] = a[temp_size-1];
			}
			a[pos1] = b[pos2];//插入b[pos2]
			pos1++;
			pos2++;  //比较b下一元素
			size1++; //a元素个数加一
		}
		else if( a[pos1] == b[pos2])
		{//相等，重复元素不插入
			pos2++;
		}
		else
		{//比较a下一个元素
			pos1++;
		}

		//a遍历完，b剩余元素加到a后面，排序完成
		if(pos1 == size1)
		{
			for(;pos2 < size2; pos2++)
			{
				a[size1++] = b[pos2];
			}
			break;
		}
		//b遍历完，排序完成
		else if(pos2 == size2)
		{
			break;
		}
	}
	return _size;
}

 4、简单选择排序

#include "array.cpp"

/*
 * 函数功能：简单选择排序(升序)
 * 输入参数：数组a，数组元素个数size
 * 输出参数：无
 * 时间复杂度：O(n^2) 
 * 空间复杂度：O(1)
 * 稳定性：稳定
 */
template <class T>
void SimpleSelectSort(T a[],int size)
{
	int minIndex;
	for (int i=0; i<size; i++)
	{	
		minIndex = i;
		for ( int j=i; j<size-1; j++)
		{//找到第i小的元素的下标
			if(a[minIndex] > a[j+1]) minIndex = j+1;
		}
		//将第i小的元素插入待a[i]，原来的a[i]交换到a[minIndex]
		T elem = a[minIndex];
		a[minIndex] = a[i];
		a[i] = elem;
	}
}

 5、堆排序

#include "array.cpp"

/*
 * 函数功能：用于堆排序调整堆 使未出堆元素结构仍为大根堆
 * 输入参数：数组a，当前元素下标、待调整堆的最后一个元素下标
 * 输出参数：无
 */
template <class T>
void adjustHeap(T a[],int current,const int lastIndex)
{	//采用大根堆
	T temp = a[current];
	int child = 2*current + 1;//当前结点左孩子下标
	while (child <= lastIndex)
	{
		if (child+1 <= lastIndex && a[child] < a[child+1]) child++;//选择两个子结点中较大的那个
		if (a[child] <= temp) break; //以当前结点为根的树符合大根堆，调整完成 
		else
		{       //当前结点与当前孩子交换，下一循环为以当前孩子为根
			a[current] = a[child];
			current = child;//当前孩子作为当前结点
			a[child] = temp;
			child = 2 * current + 1;//当前结点左孩子下标
		}
	}
}


/*
 * 函数功能：堆排序(升序)
 * 输入参数：数组a，数组元素个数size
 * 输出参数：无
 * 时间复杂度：O(n*log n)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 */
template <class T>
void HeadSort(T a[],const int size)
{
	for (int i = (size-2)/2; i>=0; i-- ) // (size-2)/2 第一个非叶子结点下标
	{	//初始化堆
		adjustHeap(a,i,size-1);
	}
	for (int i = size-1; i >= 1; i--)
	{	//堆根逐个出堆，堆剩余元素进行调整，两步交替操作即可完成排序
		T temp = a[0];
		a[0] = a[i];//最大值出堆
		a[i] = temp;//堆尾元素作堆根
		adjustHeap(a,0,i-1);//调整堆
	}
}

int main()
{
    int a[100];
    int a_size;
    a_size = autoInitArray(a);//初始化待排序数组
    print(a,a_size);
        
    /*******************************************/
    cout<<endl<<"堆排序:"<<endl;
    cout<<"堆排序:";
    HeadSort(a,a_size);
    print(a,a_size);
                                                                                                                                         
    return 0;
}