排序算法总结

排序的一些基本概念

排序是数据处理中经常使用的一种操作，其主要目的是便于查找。

1. 在排序（sort）问题中，通常将数据元素称为记录（record）。
2. 将待排序记录扫描一遍称为一趟（pass）。
3. 排序的定义
   给定一个记录序列（$r_1、r_2、…、r_n$）其关键码分别为（$k_1、k_2、…、k_n$），排序是将这些记录排列成顺序为（$r_{s1}、r_{s2}、…、r_{sn}$）的一个序列，使得相应的关键码满足升序或降序。简言之：排序是将一个记录的任意序列重新排列成一个按关键码有序的序列。
4. 算法的稳定性
   假设在待排序的记录序列中有多个具有相同关键码的记录，若经过排序，这些记录的相对此项保持不变，及在原序列中$k_i=k_j$，且$k_i$在$k_j$之前，而排序后的序列中$k_i$仍在$k_j$之前，则称这种算法是稳定的；反之不稳定。

排序的分类

• 根据排序过程中待排序的所有记录是否全部被放置在内存中，可分为内排序和外排序。

  • 内排序：排序过程中，待排序的所有记录全部被放置在内存中。
  • 排序：排序过程中，由于待排序记录个数太多，不能同时放置在内存中，整个排序过程需要在内外存之间多次交换数据才能得到排序结果。

• 根据排序方法是否建立在关键码比较的基础上，可分为基于比较的排序和不基于比较的排序。

排序算法的性能

1. 排序算法的时间开销是衡量其好坏的最重要的标志。
   对于基于比较的内排序，在排序过程中通常需要进行下列两种基本操作
   ①比较，关键码之间的比较；
   ②移动，记录从一个位置移动到另一个位置。
   所以，在待排序的记录个数一定的条件下，算法的执行时间主要消耗在关键码之间的比较和记录的移动上。因此，高效率的排序算法应该具有尽可能少的关键码比较次数和尽可能少的记录移动次数。
2. 评价排序算法的另一个主要标准是执行算法所需要的辅助存储空间。 辅助存储空间是指在待排序的记录个数一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。
3. 算法本身的复杂程度也是一个要考虑的因素。
4. 稳定性不是衡量算法好坏的标准。

排序算法思想及代码

插入排序

主要思想是每次讲一个待排序记录插入到一个已经排好序的序列中，直到全部记录都排好序。

直接插入排序（straight insertion sort）

直接插入排序算法简单、容易实现，当序列中的记录基本有序或待排序记录较少时，是最佳的排序方法。基本思想是依次将待排序序列中的每一个记录插入到一个已排好序的序列中，直到全部记录都排好序。可以想一下打扑克的时候，每抓到一张牌就会插入到你手中已经按顺序理好的牌中。

1. 将整个待排序的记录划分为有序区和无序区，初始时有序区为待排序记录序列中的第一个记录，无序区包括所有的剩余待排序记录
2. 讲无序区第一个记录插入到有序区的合适位置中，从而使无序区减少一个记录，有序区增加一个记录
3. 重复2直到无序区中没有记录为止。

例如待排序序列序列12 15 9 20 6 31 24

初试键值序列	[ 12 ] 15 9 20 6 31 24
第一趟	[ 12 15 ] 9 20 6 31 24
第二趟	[ 9 12 15 ] 20 6 31 24
第三趟	[ 9 12 15 20 ] 6 31 24
第四趟	[ 6 9 12 15 20 ] 31 24
第五趟	[ 6 9 12 15 20 31 ] 24
第六趟	[ 6 9 12 15 20 24 31 ]

代码

a[n]为待排序数组，其中有n个空间，但是注意此时是将数组a[n]的第一个位置，即a[0]作为哨兵，暂存你从无序区选到的数。因此你实际排序的数只有n-1个。

void InsertSort(int r[],int n)
{
	int i,j;
	for(i=2;i<n;i++)				//0号单元作为哨兵
	{
		r[0]=r[i];					//暂存关键码
		for(j=i-1;r[0]<=r[j];j--)	//r[0]<r[j]也可
			r[j+1]=r[j];
		r[j+1]=r[0];
	}
}

算法分析

/	时间复杂度	空间复杂度
最好情况	$O(n)$
最坏情况	$O(n^2)$
平均	$O(n^2)$	$O(1 )$

实例

待排序序列12,46,75,46,1,35,64 共七个数，因此需要设置一个容量为8的数组。

#include<iostream>
using namespace std;
void print1(int r[],int n) //过程输出 
{
	cout<<"r["<<0<<"] = "<<r[0]<<" 哨兵"<<endl; 
	for(int i=1;i<n;i++)
		cout<<"r["<<i<<"] = "<<r[i]<<endl; 
}
void print2(int r[],int n) //常规输出 
{
	for(int i=1;i<n;i++)
		cout<<"r["<<i<<"] = "<<r[i]<<endl; 
}
void InsertSort(int r[],int n)
{
	int i,j;
	for(i=2;i<n;i++)				//0号单元作为哨兵
	{
		r[0]=r[i];					//暂存关键码
		for(j=i-1;r[0]<=r[j];j--)
			r[j+1]=r[j];
		r[j+1]=r[0];
		cout<<"第"<<i-1<<"趟结果"<<endl;
		print1(r,8);
		cout<<endl;
	}
}

int main() 
{
	int r[8]={0,12,46,75,46,1,35,64};
	cout<<"待排序数组："<<endl; 
	print2(r,8);
	cout<<endl;
	InsertSort(r,8);
	cout<<"排序后数组："<<endl; 
	print2(r,8);
    return 0;
}

---

折半插入排序

这个就不多说了，就是把直接插入排序中在有序区进行顺序查找替换为二分查找。

代码

void BInsertSort(int a[],int n)
{
	int i,j,low,high,mid;
	for (i=2;i<n;i++)
	{
		a[0]=a[i];
		low=1;
		high=i-1;
		while(low<=high)
		{
			mid=(low+high)/2;
			if (a[mid]>a[0])
				high=mid-1;
			else
				low=mid+1;
		}
		for(j=i-1;j>=high+1;j--)
			a[j+1]=a[j];
		a[high+1]=a[0]; //a[low]=a[0];
	}
}

---

希尔排序（shell sort）

希尔排序又称缩小增量排序，是对直接插入排序的一种改进。基本思想是将待排序序列分成若干子序列，在子序列内进行插入排序，待整个序列基本有序时，对全体记录进行一次插入排序。

排序过程

假设待排序的记录为n个，先取整数$d＜n$，将所有相距为d的记录构成一组，从而将整个待排序记录序列分割成为d个子序列，对每个子序列分别进行直接插入排序，然后再缩小间隔d。重复上述分割，再对每个子序列分别进行直接插入排序，直到最后取d＝1，即将所有记录放在一组进行一次直接插入排序，最终将所有记录重新排列成按关键码有序的序列。d的取值可以自己决定，一般来说，按照希尔最早提出的方法是$d_1=\lfloor n/2 \rfloor$，$d_{i+1}=\lfloor d_i/2 \rfloor$，最后增量为1。
例如：待排序徐序列59,20,17,36,98,23,14,13,28

shell sort	d	序列
第一趟	$9/2=4$	28　　　　59　　　　98 20　　　　23　　 　14　　　　17　 　　　13　　　　36 结果：28 20 14 13 59 23 17 36 98
第二趟	$4/2=2$	14　17　28　59　98 　19　20　23　36　 结果：14 19 17 20 28 23 59 36 98
第三趟	$2/2=1$	（即直接插入排序） 结果：14 17 19 20 23 28 36 59 98

代码

希尔排序中a[n]为待排序数组，其中有n个空间，注意此时是将数组a[n]的第一个位置，即a[0]作为暂存单元，不是哨兵。因此你实际排序的数只有n-1个。

void ShellSort(int a[],int n)
{
	int d,i,j;
	for(d=n/2;d>=1;d/=2)
	{
		for (i=d+1;i<n;i++)
		{
				a[0]=a[i];
				for (j=i-d;j>0&&a[0]<a[j];j=j-d)
					a[j+d]=a[j];
				a[j+d]=a[0];
		}
	}
}

算法分析

/	时间复杂度	空间复杂度
最好情况	/
最坏情况	$O(n^2)$
平均	/	$O(1 )$

希尔排序的增量取法有各种方案。按照希尔提出的方法是$d_1=\lfloor n/2 \rfloor$，$d_{i+1}=\lfloor d_i/2 \rfloor$，最后增量为1。但由于直到最后一步，在奇数位置的元素才会与偶数位置的元素进行比较，这样使用这个序列的效率将很低。后人又提出各种效率更高的增量取法。**不同增量取值方法会使希尔排序算法的性能有很大差异。**因此对希尔排序的时间复杂度的分析很困难，在特定情况下可以准确地估算排序码的比较次数和元素移动次数，但想要弄清排序码比较次数和元素移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。在 Knuth所著的《计算机程序设计技巧》第3卷中，利用大量的实验统计资料得出，当n很大时，排序码平均比较次数和元素平均移动次数大约在$n^{1.25}$到$1.6n^{1.25}$的范围内。 我觉得就是现在大部分教材中的$O(n^{1.3})$。
我还翻译了一个文章，感兴趣的可以看看，里面汇总了一些文献对于希尔排序的性能推算。希尔排序复杂度详细分析（翻译来源：Hans Werner Lang教授）

实例

待排序序列59,20,17,36,98,23,14,13,28 共9个数，因此需要设置一个容量为10的数组。

#include<iostream>
using namespace std;
void print(int r[],int n) //常规输出 
{
	for(int i=1;i<n;i++)
		cout<<"r["<<i<<"] = "<<r[i]<<endl; 
	cout<<endl; 
}

void ShellSort(int a[],int n)
{
	int d,i,j;
	int count=1; //用于过程输出，可删除 
	for(d=n/2;d>=1;d/=2)
	{
		for (i=d+1;i<n;i++)
		{
				a[0]=a[i];
				for (j=i-d;j>0&&a[0]<a[j];j=j-d)
					a[j+d]=a[j];
				a[j+d]=a[0];
		}
		/*-----过程输出可删除--------*/ 
		cout<<"第"<<count<<"趟"<<endl;
		cout<<"d = "<<d<<endl;
		count++;
		print(a,n);
		/*-----过程输出--------*/ 
	}
}
int main()
{

	int a[10]={0,59,20,17,36,98,23,14,13,28};
	cout<<"待排序数组"<<endl;
	print(a,10);
	ShellSort(a,10);
	cout<<"排序结果"<<endl;
	print(a,10);
	return 0;
}

交换排序

冒泡排序（bubble sort）

冒泡排序又称起泡排序，基本思想是两两比较相邻记录的关键码，如果反序则交换。

排序过程

1. 将整个待排序的记录序列划分成有序区和无序区，初始时有序区为空，无序区包括所有待排序的记录。
2. 对无序区从前向后依次将相邻记录的关键码进行比较，若反序则交换，从而使得
   关键码小的记录向前移，关键码大的记录向后移（像水中的气泡，体积大的先浮上来）
3. 重复执行2直到无序区中没有反序的记录。

例如： 待排序序列453,143,49,6,31,1,28

……以此类推，直到整个序列排序完成。例子里可以看出来每次交换都有一个数到达它的最终位置（之后排序这个数字的位置都不会变了嗷₍₍ (ง ˙ω˙)ว ⁾⁾）。

代码

void BubbleSort(int a[],int n)
{
	for(int i=0;i<n-1;i++)
	{  
		/*设置一个标志，如果依次循环中不再出现交换，
		证明每个记录都到达了它的最终位置上，
		即可跳出循环停止排序过程。*/
		bool flag=false;  
		for (int j=0;j<n-i-1;j++)
		{
			if (a[j]>a[j+1])
			{
				int mid=a[j];
				a[j]=a[j+1];
				a[j+1]=mid;
				flag=true;
			}
		}
		if(flag==false) return;
	}
}

算法分析

/	时间复杂度	空间复杂度
最好情况	$O(n)$
最坏情况	$O(n^2)$
平均	$O(n^2)$	$O(1 )$

实例

待排序序列453,143,49,6,31,1,28

#include<iostream>
using namespace std;
void Print(int a[],int n)
{
	for (int i=0;i<n;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
}
void BubbleSort(int a[],int n)
{
	for(int i=0;i<n-1;i++)
	{
		bool flag=false;
		for (int j=0;j<n-i-1;j++)
		{
			if (a[j]>a[j+1])
			{
				int mid=a[j];
				a[j]=a[j+1];
				a[j+1]=mid;
				flag=true;
			}
		}
		if(flag==false) return;
		/*-------排序过程------*/
		cout<<"第"<<i+1<<"趟排序："; 
		Print(a,n); 
		/*-------排序过程------*/
	}
}
int main()
{
	int b[7]={453,143,49,6,31,1,28};
	cout<<"待排序数组:"<<endl;
	Print(b,7);
	BubbleSort(b,7);
	cout<<"排序结果:"<<endl;
	Print(b,7);
	return 0;
}

---

快速排序（quick sort）

排序过程

快速排序是对起泡排序的一种改进，基本思想是首先选一个轴值（pivot即比较的基准）将待排序记录划分成独立的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。

举个栗子： 待排序序列：23,12,49,6,31,19,28

以第一行数据为例：

例子中可以看出，每次交换轴值都会到达它的最终位置（之后排序这个数字的位置都不会变了嗷₍₍ (ง ˙ω˙)ว ⁾⁾）。

代码

我参考了两本书，列了两个写法。两个写法的区别就在于int partition(int a[],int low,int high)这个函数不太一样。
写法一
不借助pivot做暂存空间。每次比较发现逆序之后直接进行交换。

void change(int &a, int &b)					//自定义的交换函数
{
	int mid=a;
	a=b;
	b=mid;
}
int partition(int a[],int low,int high)
{
	while(low<high)
	{
		while(low<high && a[low]<=a[high])
			high--;
		change(a[low],a[high]);
		while(low<high && a[low]<=a[high])
			low++;
		change(a[low],a[high]);
	}
	return low; 							//return high也行 
}
void QuickSort(int a[],int low,int high)
{
	if(low<high)
	{
		int p=partition(a,low,high);
		QuickSort(a,low,p-1);
		QuickSort(a,p+1,high);
	}
}

写法二
借助pivot做暂存空间。最后再将轴值放入。

int partition(int a[],int low,int high)
{
	int pivot = a[low];
	while(low<high)
	{
		while(low<high && a[high]>=pivot)
			high--;
		a[low]=a[high];
		while(low<high && a[low]<=pivot)
			low++;
		a[high]=a[low];
	}
	a[low]=pivot;
	return low; 						//return high也行 
}
void QuickSort(int a[],int low,int high)
{
	if(low<high)
	{
		int p=partition(a,low,high);	//第一次划分
		QuickSort(a,low,p-1);  			//递归对左侧划分
		QuickSort(a,p+1,high);			//递归对左侧划分
	}
}

算法分析

/	时间复杂度	空间复杂度
最好情况	$O(nlog_2n)$	$O(log_2n)$
最坏情况	$O(n^2)$	$O(n)$
平均	$O(nlog_2n)$	$O(log_2n)$

实例

/*---------------------写法一-----------------------*/
#include<iostream>
using namespace std;
void Print(int a[],int n)
{
	for (int i=0;i<n;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
}
void change(int &a, int &b)
{
	int mid=a;
	a=b;
	b=mid;
}
int partition(int a[],int low,int high)
{
	while(low<high)
	{
		while(low<high && a[low]<=a[high])
			high--;
		//if(low<high)
		{
			change(a[low],a[high]);
		//	low++;
		}
		while(low<high && a[low]<=a[high])
			low++;
		//if(low<high)
		{
			change(a[low],a[high]);
		//	high--;
		}
	}
	Print(a,7);  //过程输出 
	return low; //return high也行 
}
void QuickSort(int a[],int low,int high)
{
	if(low<high)
	{
		int p=partition(a,low,high);
		QuickSort(a,low,p-1);
		QuickSort(a,p+1,high);
	}
}
int main()
{
	int a[7]={23,12,49,6,31,19,28};
	
	cout<<"待排序序列："<<endl;
	Print(a,7);
	cout<<endl<<"划分过程"<<endl; 
	QuickSort(a,0,6);
	cout<<endl<<"排序结果："<<endl;
	Print(a,7);

	return 0;
}

/*---------------------写法二-----------------------*/
#include<iostream>
using namespace std;
void Print(int a[],int n)
{
	for (int i=0;i<n;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
}
int partition(int a[],int low,int high)
{
	int pivot = a[low];
	while(low<high)
	{
		while(low<high && a[high]>=pivot)
			high--;
		a[low]=a[high];
		while(low<high && a[low]<=pivot)
			low++;
		a[high]=a[low];
	}
	a[low]=pivot;
	Print(a,7); //过程输出 
	return low; //return high也行，可以自己试一下，因为这时候low=high为pivot的最终位置
}
void QuickSort(int a[],int low,int high)
{
	if(low<high)
	{
		int p=partition(a,low,high);
		QuickSort(a,low,p-1);
		QuickSort(a,p+1,high);
	}
}
int main()
{
	int a[7]={23,12,49,6,31,19,28};
	
	cout<<"待排序序列："<<endl;
	Print(a,7);
	cout<<endl<<"划分过程"<<endl; 
	QuickSort(a,0,6);
	cout<<endl<<"排序结果："<<endl;
	Print(a,7);

	return 0;
}

选择排序

简单选择排序（simple selection sort）

基本思想是第i趟排序从待排序序列中找到最小值，并和第i个记录交换，作为有序序列的第i个记录。

排序过程

1. 将整个记录序列划分为有序区和无序区，初始时有序区为空，无序区含有待排序的所有记录。
2. 在无序区中选取关键码最小的记录，将它与无序区中的第一个记录交换，使得有序区扩展了一个记录，同时无序区减少了一个记录。
3. 不断重复2，直到无序区只剩下一个记录为止。此时所有的记录已经按关键码从小到大的顺序排列。

例如待排序序列12,5,19,35,3

从例子中可以看出每次排序，有序区的记录最终位置已经确定。

代码

void SelectSort(int a[],int n)
{
	for (int i=0;i<n-1;i++)
	{
		int index=i;
		for(int j=i+1;j<n;j++)
		{
			if (a[j]<a[index]) 
				index=j;
		}
		if (index!=i)
		{
			int mid=a[i];
			a[i]=a[index];
			a[index]=mid;
		}
	}
}

算法分析

/	时间复杂度	空间复杂度
最好情况	$O(n^2)$
最坏情况	$O(n^2)$
平均	$O(n^2)$	$O(1 )$

实例

#include<iostream>
using namespace std;
void print (int a[],int n)
{
	for (int i=0;i<n;i++)
		cout<<a[i]<<"  ";
	cout<<endl;
} 
void SelectSort(int a[],int n)
{
	for (int i=0;i<n-1;i++)
	{
		int index=i;
		for(int j=i+1;j<n;j++)
		{
			if (a[j]<a[index]) 
				index=j;
		}
		if (index!=i)
		{
			int mid=a[i];
			a[i]=a[index];
			a[index]=mid;
		}
		/*-------------排序过程--------------*/
		cout<<"第"<<i+1<<"趟排序: "; 
		print(a,n);
	}
}
int main()
{
	int a[9]={20,12,65,35,62,11,43,65,98};
	cout<<"待排序数组：";
	print(a,9);
	SelectSort(a,9);
	cout<<"排序后数组：";
	print(a,9);
	return 0;
}

---

堆排序（heap sort）

堆排序是简单选择排序的改进，是利用堆的特性进行排序的方法。基本思想是（假设用大根堆）首先将待排序的记录序列构造成一个堆，选出堆中所有记录的最大者即堆顶的记录，然后将堆顶记录移走，并将剩余记录再调整成堆，这样又能找出一个当前最大的记录，以此类推，直到堆中只有一个记录为止。

什么是堆？
堆（heap） 是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆）；或者每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。顺序存储结构表示就是：

$小根堆\begin{cases} k_i \leq k_{2i}\\ k_i \leq k_{2i+1} \end{cases} 1 \leq i \leq \lfloor n/2 \rfloor$

$大根堆\begin{cases} k_i \geq k_{2i}\\ k_i \geq k_{2i+1} \end{cases} 1 \leq i \leq \lfloor n/2 \rfloor$

排序过程

1. 将一个无序序列构造成一个堆，即初始建堆
   数据用顺序存储结构存储，将所有的数据都放在一个数组中，这就可以看成是一个完全二叉树的顺序存储结构。 接下来就只需要把它调整成一个堆即可。
2. 处理堆顶记录：建好堆之后将待排序序列分为无序区和有序区两部分，其中无序区为堆，包括全部待排序记录，有序区是空的。将堆顶与堆中最后一个记录交换，则堆（无序区）中少了一记录，有序区增加一个记录。
3. 调整剩余记录成一个新的堆

如何把完全二叉树调整成堆？
以大根堆为例，堆的定义可以知道大根堆是双亲结点的值大于其左右孩子的节点，所以说在大根堆的调整过程中总是将根节点和左右孩子进行比较，若不满足堆的条件，则将根节点与左孩子或右孩子的较大者进行交换，这个调整过程一直进行到所有子树均为堆，或者被调整节点交换到叶子节点为止。

因为数据是存储在数组中的，由完全二叉树的定义可以知道，有n个结点的完全二叉树，最后一个双亲结点(最后一个叶子结点的双亲) 的位置是$\lfloor n/2 \rfloor$，则在数组中，只需要从$k= \lfloor n/2 \rfloor$位置开始，与其位置为$2k$和$2k+1$的孩子结点比较，然后逐个向前调整，一直调整到第一个记录。
再举个栗子，排序过程，待排序序列36,30,18,40,32,45,22,50

……后边步骤不放了，应该能自己知道。具体代码看最后实例部分。

代码

写法一
直接就这么写，从数组0号位开始，计算$k$的孩子结点就不能用$2k$和$2k+1$，而应该在这个基础上+1。（因为根结点在a[0]，$0*2=0，0*2+1=1$，但是a[0]的孩子结点应的a[1]a[2]）

void sift(int a[],int low,int high)
{
	int i=low,j=2*i+1;//i为待调整结点，j为其左孩子,注意数组是0开始的，所以左孩子在2*i+1的位置
	while(j<=high) //必须有=，保证剩两个结点时能进行堆重构
	{
		if (j<high && a[j]<a[j+1]) //比较左右孩子，选出较大者 
			j++;
		if(a[i]>=a[j])//符合堆条件 
			break;
		else//不符合堆的条件，进行调整 
		{
			swap(a[i],a[j]);
			i=j;
			j=2*i+1;
		}
	}
}
void HeapSort(int a[],int n)
{
	n--; //堆的第一个记录在数组的0号位，最后一个记录在数组的n-1号位 
	for(int i=n/2;i>=0;i--)//从n/2开始调整 
		sift(a,i,n);
	for (int i=0;i<n;i++)
		/*开始传入参数n为数组长度8，HeapSort中进行n--，此时n=7，
		进行7趟即可，最后只剩一个根节点时自动并入有序区*/
	{
		swap(a[0],a[n-i]);//将第一个与堆中最后一个交换
		sift(a,0,n-i-1);//此时堆就减少一个
	}
}

写法二
浪费一个数组空间a[0]，从a[1]开始存储数据。个人感觉这样写比较简单（其实没差别( ‘-ωก̀ )）。

void sift(int a[],int low,int high)
{
	int i=low,j=i*2;
	while(j<=high) 
	{
		if (j<high && a[j]<a[j+1]) 
			j++;
		if(a[i]>=a[j])
			break;
		else
		{
			swap(a[i],a[j]);
			i=j;
			j=2*i;
		}
	}
}
void HeapSort(int a[],int n)
{
	for(int i=n/2;i>=1;i--)
		sift(a,i,n);
	for (int i=1;i<n;i++)
	{
		swap(a[1],a[n-i+1]);
		sift(a,1,n-i);
	}
}

算法分析

/	时间复杂度	空间复杂度
最好情况	$O(nlog_2 n)$
最坏情况	$O(nlog_2 n)$
平均	$O(nlog_2 n)$	$O(1 )$

实例

写法一

#include<iostream>
using namespace std;
void print(int a[],int n)
{
	for (int i=0;i<n;i++) 	
		cout<<a[i]<<"  ";
	cout<<endl;
} 
void sift(int a[],int low,int high)
{
	int i=low,j=2*i+1;					//i为待调整结点，j为其左孩子
										//数组是0开始的，所以左孩子在2*i+1的位置
	while(j<=high) 						//必须有=，保证剩两个结点时能进行堆重构
	{
		if (j<high && a[j]<a[j+1]) 		//比较左右孩子，选出较大者 
			j++;
		if(a[i]>=a[j])					//符合堆条件 
			break;
		else							//不符合堆的条件，进行调整 
		{
			swap(a[i],a[j]);
			i=j;
			j=2*i+1;
		}
	}
}
void HeapSort(int a[],int n)
{
	n--; 								//堆的第一个记录在数组的0号位
										//最后一个记录在数组的n-1号位 
	for(int i=n/2;i>=0;i--)				//从n/2开始调整 
		sift(a,i,n);

	cout<<"无序区               有序区"<<endl;
	for (int i=0;i<n;i++)
		/*开始传入参数n为数组长度8，HeapSort中进行n--，此时n=7，
		进行7趟即可，最后只剩一个根节点时自动并入有序区*/
	{
		swap(a[0],a[n-i]);				//将第一个与堆中最后一个交换
		sift(a,0,n-i-1);				//此时堆就减少一个
		/*-----------输出过程-----------*/
		for (int j=0;j<n-i;j++)
			cout<<a[j]<<" ";
		cout<<" | ";
		for (int j=n-i;j<=n;j++)
			cout<<a[j]<<" ";
		cout<<endl;
	}
}
int main()
{
	int a[8]={36,30,18,40,32,45,22,50};
	cout<<"待排序数组："<<endl;
	print(a,8);
	HeapSort(a,8);
	cout<<"排序结果："<<endl;
	print(a,8);
	return 0;
}

写法二

#include<iostream>
using namespace std;
void print(int a[],int n)
{
	for (int i=1;i<=n;i++) 
		cout<<a[i]<<"  ";
	cout<<endl;
} 
void sift(int a[],int low,int high)
{
	int i=low,j=i*2;
	while(j<=high) 
	{
		if (j<high && a[j]<a[j+1]) 
			j++;
		if(a[i]>=a[j])
			break;
		else
		{
			swap(a[i],a[j]);
			i=j;
			j=2*i;
		}
	}
}
void HeapSort(int a[],int n)
{
	for(int i=n/2;i>=1;i--)
		sift(a,i,n);
	for (int i=1;i<n;i++)
	{
		swap(a[1],a[n-i+1]);
		sift(a,1,n-i);
	}
}
int main()
{
	int a[9]={0,36,30,18,40,32,45,22,50};
	cout<<"待排序数组："<<endl;
	print(a,8);
	cout<<endl;
	cout<<"HeapSort:"<<endl;
	HeapSort(a,8);
	print(a,8);
	cout<<endl;
	return 0;
}

---

各种排序的比较

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性	适用范围
直接插入排序	$O(n^2)$	$O(n)$	$O(n^2)$	O(1)	稳定	顺序存储、链式存储
希尔排序	/	/	$O(n^2)$	O(1)	不稳定	顺序存储
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	O(1)	稳定	顺序存储、链式存储
快速排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(n^2)$	$O(log_2n) - O(n^2)$	不稳定	顺序存储、链式存储
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	O(1)	不稳定	顺序存储、链式存储
堆排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	O(1)	不稳定	顺序存储、链式存储

补充：希尔排序比较特殊，详细看上边链接。