用c++实现的八大排序算法

最近重新复习了一下排序算法，深入理解了各个排序算法的基本思想，根据算法基本思想重新写了这八种类型的排序算法，特此总结一下，以便日后忘记时可以重新查看。也给有需要的朋友作参考。

#include 

#include 
#include 
using namespace std;
/*********************************插入排序算法******************************/
/***********************直接插入排序*********************/
/**
 *基本思想：顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置
 *子集合的数据元素个数从只有一个数据元素开始，逐次增大，当子集合大小最终和集合大小相同时
 *排序完成
 *直接插入排序是稳定的
 * **/
void insertionsort(vector &vtarr)
{
 //将数组的第一个元素看做有序序列，从第二个元素开始直到数组的最后一个元素
 //依次插入
 for (unsigned int i=1; i -1 && temp < vtarr[j])
  {
vtarr[j + 1] = vtarr[j];
--j;
  }
  //将比较的元素放到适合的位置
  vtarr[j + 1] = temp;
 }
}

/****************************希尔排序法******************************/
/**
 *基本思想：把待排序的数据元素分成若干个小组，对同一个小组内的数据元素
 *用直接插入法排序；小组的个数逐次减少；当完成了所有数据元素都在一个组
 *内的排序后，排序过程结束。希尔排序又称作缩小增量排序
 *值得注意的是，增量序列的最后一个元素一定是1
 */
void shellsort(vector &vtarr)
{
 // 先根据排序数组的大小确定增量序列
 // 增量序列为[n/2, n/4, n/8,...,1]n为排序数组的元素个数
 vector vtadd;
 // 如果没有元素或者只有一个元素，不需要排序，返回
 if (vtarr.size() < 2)
 {
  return;
 }
 unsigned int num = 2;
 int nspan;// 增量值
 while(num <= vtarr.size())
 {
  nspan = vtarr.size() / num;
  vtadd.push_back(nspan);
  num *= 2;
 }
 // 这个分组的思想是按增量span来划分，[j,j+span,j+2span...]其中 j>=0 && j -1 && temp < vtarr[m])
 {
  vtarr[m + nspan] = vtarr[m];
  m -= nspan;
 }
 vtarr[m + nspan] = temp;
}
  }
 }
}

/*********************************选择排序算法******************************/
/***********************直接选择排序算法*********************/
/*基本思想：首先将待排序的数据元素集合的第1个视为最小元素，并记录其下标为small，然后从第2个元素开始找出比下标
 *为small的元素小的元素，并把其下标值存为small，继续往后查找到集合最后一个元素，每次查找到下标比small小的元素
 *就将其下标替换为small。这样就找出了整个集合中最小的元素的下标small，然后将第1个元素与下标为small的元素互换位置。
 *接着将集合的第2个元素视为最小元素，记下下标为small，然后从第3个元素开始按以上方法查找，即找出集合中次小的元素
 *然后将次小元素与第2个元素互换位置。重复以上步骤直到集合中只剩一个元素为止。
 */
void selectsort(vector &vtarr)
{
 for(unsigned int i=0; i vtarr[j])
{
 small = j;
}
  }
  if (small != i)
  {
int temp = vtarr[i];
vtarr[i] = vtarr[small];
vtarr[small] = temp;
  }
 }
}

/*********************************堆排序法******************************/
/* 基本思想：首先把n个元素的数组a初始化为最大堆，然后循环执行如下过程直到数组为空为止：
 * 1、把堆顶a[0]元素（为最大元素）和当前最大堆的最后一个元素交换
 * 2、最大堆元素个数减1
 * 3、由于第1步后根节点不再满足最大堆的定义，因此调整根节点使之满足最大堆的定义
 */
// 堆排序首先需要定义一个函数，将一颗所有叶节点都满足最大堆的定义，只有根节点没有满足最大堆定义的
// 情况下，调整为最大堆。
// 其中vtarr为堆数组，n为堆的节点个数，nrootindex为要调整为最大堆的根节点下标
// 已知根节点的下标，则左子树的下标为2*nrootindex+1,右子树的下标为2*nrootindex+2
void createheap(vector &vtarr, int n, int nrootindex)
{
 int i = nrootindex;
 int j = 2 * i + 1;//左子树的下标
 int tempvalue = vtarr[nrootindex];//保存根节点的值
 bool bfinish = false;//是否调整完成的标志
 while (j < n && !bfinish)
 {
  // 找出左子树和右子树的最大值
  if (j+1 < n && vtarr[j] < vtarr[j+1])
  {
++j;//j+1后就变成了右子树的下标了
  }

  // 如果根节点大于左右子节点的最大值，说明符合最大堆的定义，调整完成
  if (tempvalue > vtarr[j])
  {
bfinish = true;
  }
  else
  {
// 否则该子节点上移到根节点
vtarr[i] = vtarr[j];
i = j;//原来的子节点的位置成为新的根
j = 2 * i + 1;//新根的左子树的下标
  }
 }
 // 把原来的根元素放合适的位置
 vtarr[i] = tempvalue;
}

// 将需要排序的无序数组初始化成为一个最大堆，需要从最后一个非页节点到根节点a[0],依次调整
// 使其符合最大堆的定义；最后一个非叶节点为(n-2)/2取整，其中n为堆的元素个数
void initheap(vector &vtarr)
{
 for (int i=(vtarr.size()-2)/2; i>=0; --i)
 {
  createheap(vtarr, vtarr.size(), i);
 }
}

// 堆排序主函数
// 首先把有n个元素的数组vtarr初始化为最大堆，然后循环执行如下过程直到数组为空为止
// 1、把堆顶元素vtarr[0](为最大元素)和当前最大堆的最后一个元素交换；
// 2、最大堆元素个数减1
// 3、由于第1步后根结点不再满足最大堆定义，因此调整根结点使之满足最大堆的定义
void heapsort(vector &vtarr)
{
	initheap(vtarr);// 将需要排序的数组初始化成为最大堆
 for (int i = vtarr.size()-1; i>0; --i)
 {
  int temp = vtarr[0];
  vtarr[0] = vtarr[i];
  vtarr[i] = temp;
  createheap(vtarr, i, 0);
 }
}

/*********************************交换排序******************************/
/*******************冒泡排序法**********************/
/*基本思想：设数组vtarr中存放了n个数据元素，循环进行n-1趟如下的排序过程：
 * 第一趟时，依次比较相邻两个数据元素vtarr[j]和vtarr[j+1](j=0,1,2...,n-2),如果vtarr[j]>vtarr[j+1]
 * 则交换两个数据元素，否则不交换，这样数值最大的数据元素将被放置在vtarr[n-1]中；
 * 第二趟时，数据元素个数减1，即数据元素个数为n-1,操作方法和第一趟类似，这样整个
 * n个数据元素集合中数值次大的数据元素将被放置在vtarr[n-2]中；当第n-1趟结束时，整个n
 * 个数据元素集合中次小的数据元素将被放置在vtarr[1]中，vtarr[0]中放置了最小的数据元素
 */ 
void bubblesort(vector &vtarr)
{
 bool border = false;
 for (int i = vtarr.size() - 1; i > 0 && !border; --i)
 {
  border = true;
  for (int j=0; j vtarr[j+1])
{
 int temp = vtarr[j];
 vtarr[j] = vtarr[j+1];
 vtarr[j+1] = temp;
 border = false;//有交换说明还没有序
}
  }
 }
}

/*********************************快速排序法******************************/
/*基本思想：快速排序是一种二叉树结构的交换排序方法。设数组a中存放了n个数据元素，low为数组的低端下标，
 * hight为数组的高端下标，从数组a中任取一个元素（通常取a[low]）作为标准，调整数组a中各个元素的位置，使
 * 排在标准元素前面的元素均小于标准元素，排在标准元素后面的元素均大于或等于标准元素的关键字。这样一次过
 * 程结束后，一方面将标准元素放在未来排好序的数组中该标准元素应在的位置，另一方面将数组中的元素以标准元
 * 素为中心分成了两个子数组，位于标准元素左边的元素均小于标准元素，位于标准元素右边的元素均大于标准元素
 * 然后，对这两个子数组中的元素分别再进行方法类同的递归快速排序。递归算法的结束条件是hight<=low,即上界
 * 下标小于或等于下界下标
 */
void quicksort(vector &vtarr, int low, int hight)
{
 int i = low; // 左边扫描起始位置
 int j = hight;  // 右边扫描起始位置
 int temp = vtarr[i];// 取下标最低位置的元素作为标准元素，并保存到临时变量
 while (i < j)
 {
  // 因为以下标最低位置元素为标准元素，因此开始扫描必须从数组右侧进行扫描
  while (i < j && temp < vtarr[j])
		{
			--j;
		}
		if (i < j)
		{
			// 当从右向左找到第一个小于temp元素的元素时，交换两个元素的位置
			vtarr[i] = vtarr[j];
			++i;
		}
		// 然后从左向右扫描查找
		while (i < j && temp > vtarr[i])
		{
			++i;
		}
		if (i < j)
		{
			// 当从左向右找到第一个大于temp元素的元素时，交换两个元素的位置
			vtarr[j] = vtarr[i];
			--j;
		}
 }
	// 把标准元素放在最终适合的位置,此时i==j
	vtarr[i] = temp;
	// 以位置i为分割点，将数组分割成左右两个数组，再对左右两个数组进行递归排序
	if (low < i)
	{
		quicksort(vtarr, low, i-1);
	}
	if (i < hight)
	{
		quicksort(vtarr, i+1,hight);
	}
}

/*********************************归并排序******************************/
/* 归并排序主要是二路归并排序。
 * 二路归并排序算法的基本思想：设数组vtarr中存放了n个数据元素，初始时把它们看成n个长度为1的有序
 * 子数组，然后从第一个有序子数组开始，把相邻的有序子数组两两合并，得到n/2（此处向上取整）个长度
 * 为2的新的有序子数组（当n为奇数时，最后一个新的有序子数组的长度为1）。对这些新的有序子数组再进行
 * 两两归并。如此重复，直到得到一个长度为n的有序数组为止。
 * 算法中，需要初始化一个新的数组，以存放归并后的数据
 */ 
// 归并函数
// vtorder 待归并的部分有序的数组
// vtmerge 存放归并后的数组
// nlen 分组的长度
void merge(vector &vtorder, vector &vtmerge, int nlen)
{
 int l1 = 0;//第一个归并组的下标从0开始
 int l2;// 第二个归并组的起始下标
 int h1;// 第一个归并组的最后下标
 int h2;// 第二个归并组的最后下标
	int m = 0;//vtmerge数组的下标
 while (l1 + nlen  < (int)vtorder.size())
 {
  h1 = l1 + nlen -1;//第一组的上限
  l2 = l1 + nlen;//第二组的开始
  h2 = min(l2 + nlen -1, (int)vtorder.size() - 1);
		// 归并过程
		int i=l1;
		int j=l2;
		for (; i<=h1 && j <=h2; ++m)
		{
			if (vtorder[i] < vtorder[j])
			{
				vtmerge[m] = vtorder[i];
				++i;
			}
			else
			{
				vtmerge[m] = vtorder[j];
				++j;
			}
		}
		// 归并完后，有可能有其中一组没有全部放到vtmerge
		// 将第一组剩下的元素放到vtmerge
		while (i <= h1)
		{
			vtmerge[m] = vtorder[i];
			++i;
			++m;
		}
		// 将第二组剩下的元素放到vtmerge
		while (j <= h2)
		{
			vtmerge[m] = vtorder[j];
			++j;
			++m;
		}
  l1 = h2 +1;//重新设置第一组的开始位置
 }
	// 如果根据分组的长度分出奇个组，则最后一个组没有与其他组归并，还放在数组的最后
	while (l1 < (int)vtorder.size())
	{
		vtmerge[m++] = vtorder[l1++];
	}
}

// 归并排序函数
void mergesort(vector &vtarr)
{
	int nlen = 1;//归并组的长度
	vector vtmerge;//存放归并后的数组
	vtmerge.resize(vtarr.size());
	while (nlen < (int)vtarr.size())
	{
		merge(vtarr, vtmerge, nlen);
		vtarr = vtmerge;// 将归并后的数组复制到原数组
		nlen *= 2;//二路归并，每次归并长度加倍
	}
}

/*********************************基数排序（桶排序）******************************/
/* 基数排序是针对关键字为整数类型时的排序方法，是一种很高效的排序方法
 * 基数排序算法的基本思想：设待排序的数据元素是m位d进制整数（不足m位的关键字在高位补0），设置d个桶
 * 令其编号分别为0,1,...d-1.首先按关键字最低的数组依次把各数据元素放到相应的桶中，然后按照桶号从小
 * 到大和进入桶中数据元素的先后顺序收集分配在各桶中的数据元素，这样就形成了数据元素集合的一个新的排
 * 列，称这样的一次排序过程为一次基数排序；再对一次基数排序得到的数据元素序列按关键字次低位的数值依
 * 次把各数据放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后顺序收集分配在各桶中的数据
 * 元素；这样的过程重复进行，当完成了第m次基数排序后，就得到了排好序的数据元素序列。
 */ 
//对十进制正整数进行排序
void radixsort(vector &vtarr)
{
	// 找出数组中的最大值
	int nmax = 0;
	for (int i=0; i<(int)vtarr.size(); ++i)
	{
		if (vtarr[i] > nmax)
		{
			nmax = vtarr[i];
		}
	}
	// 计算最大值有几位数
	int m = 0;//位数
	while (nmax != 0)
	{
		++m;
  nmax /= 10;
	}
	//初始化10个桶
	queue buck[10];
	int q = 1;
	// 进行m次排序
	for (int i=0; i &vtarr)
{
 for (unsigned int i=0; i vtarr;
 vtarr.push_back(3);
 vtarr.push_back(9);
 //vtarr.push_back(-4);
 vtarr.push_back(100);
 vtarr.push_back(3);
// vtarr.push_back(-40);
 vtarr.push_back(0);
 vtarr.push_back(7);
 vtarr.push_back(12);
 vtarr.push_back(92);
 vtarr.push_back(182);
 vtarr.push_back(123);
 
 vector vtarr1 = vtarr;
 vector vtarr2 = vtarr;
 vector vtarr3 = vtarr;
 vector vtarr4 = vtarr;
 vector vtarr5 = vtarr;
 vector vtarr6 = vtarr;
 vector vtarr7 = vtarr;
 cout << "*******没有排序*****" << endl;
 display(vtarr);

 cout << "*******直接插入排序法*****" << endl;
 insertionsort(vtarr1);
 display(vtarr1);

 cout << "*******希尔排序法*****" << endl;
 shellsort(vtarr2);
 display(vtarr2);

 cout << "*******直接选择排序法*****" << endl;
 selectsort(vtarr3);
 display(vtarr3);

 cout << "*******堆排序法*****" << endl;
 heapsort(vtarr4);
 display(vtarr4);

 cout << "*******冒泡排序法*****" << endl;
 bubblesort(vtarr);
 display(vtarr);

 cout << "*******快速排序法*****" << endl;
 quicksort(vtarr5, 0, vtarr.size() - 1);
 display(vtarr5);

 cout << "*******归并排序法*****" << endl;
 mergesort(vtarr6);
 display(vtarr6);

 cout << "*******基数排序法*****" << endl;
 radixsort(vtarr7);
 display(vtarr7);
}

各种算法的时间复杂度和稳定性：