排序-笔记

2023-12-17 17:41:27

1、排序的定义
2、排序的稳定性
3、排序的详细分类
4、待排记录的数据存储结构
5、排序算法的效率分析（时间，空间，稳定性）

文章目录

待排记录的数据存储结构

#define MAXSIZE 20
typedef int KeyType;//注意此处的引号
typedef struct
{
	KeyType key;
	OtherType data;
}RedType;
typedef struct
{
	RedType r[MAXSIZE+1];
	int length;
}Sqlist;

插入类—直接插入排序

算法分析：
首先存储一段序列时L.r[0]用作监视哨，初始时不存储数据，i从2开始记录，i之前为排好的有序序列，i之后为待插入的序列，故初始时有序序列为L.r[1]，之后由L.r[i].key<L.r[i-1].key来依次寻找接下来要插入的较小数据，并先存进监视哨中，然后从i-2开始向前与L.r[0]比较，寻找其需要插入的位置，比它大的数据都依次向后移，如果其为最小，就放在L.r[1]处。
改良后的：将序列分为两部分，一部分是排好的，另一部分是要向里面插入的，按照相邻位置依次去找小的数据，与之前数据比较找其需要插入的位置，同时其插入位置之后的数据要整体向后移动。（真正的去理解算法，而不只是翻译代码）
（不懂就举实例）
已知代码来看算法，和设计算法去写代码是截然不同的。
前者是算法就蕴含在代码中，后者是怎么将算法体现在代码中。
算法代码：

void Insertsort(Sqlist &L)
{
	int i,j;
	for(i=2;i<=L.length;i++)
	if(L.r[i].key<L.r[i-1].key)
	{
		L.r[0]=L.r[i];
		L.r[i]=L.r[i-1];    
		for(j=i-2;L.r[0].key<L.r[j].key;j--)
			L.[j+1]=L.[j];
		L.[j+1]=L.r[0];
	}
}
/*
L.r[i]=L.r[i-1];  这里的L.[i-1]已经与L.r[i]比较过，在L.r[0]=L.r[i]之后，进行i之前数据与L.r[0]的比较时，可不用再进行i-1与L.r[0]的比较，故之后是从i-2开始的
*/

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定
顺式链式均可，初始记录有序时更快；初始记录无序，n较大时不宜采用

插入类—折半插入排序

void BInsertsort(Sqlist &L)
{
	int i,j,low,high,mid;
	for(i=2;i<=L.length;i++)
	{
		L.r[0]=L.r[i];  //勿忘给监视哨赋值
		low=1;high=i-1;
		while(low<=high)
		{
			mid=(low+high)/2;
			if(L.r[0].key<L.r[mid].key) high=mid-1;
			else low=m+1;
		}
		for(j=i-1;j>=high+1;j--)
		  L.r[j+1]=L.r[j];
		L.r[high+1]=L.r[0];
	}
}

对于折半查找和排序的一个结论：low=high+1，即最终退出while循环时low与high之间的关系，也是日
若最终退出循环前执行high=mid-1，则会有high<mid=low；否则则为high=mid<low
故之后移动记录的for循环中，high+1就相当于low
同样若是递减排序，只需将if条件改为if(L.r[0].key>L.r[mid].key) 即可，只是次序改变，数据移动的方向和插入的位置不受影响

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定 （待进一步检验）
更适用于初始序列无序，不可用于链式结构

插入类—希尔排序

void Shellinsert(Sqlist &L,int dk)
{ 
	int i,j;
	for(i=dk+1;i<=L.length;i++)
		if(L.r[i].key<L.r[i-dk].key)
		{
			L.r[0]=L.r[i];
			for(j=i-dk;j>0&&L.r[0].key<L.r[j].key;j-=dk)
			 L.r[j+dk]=L.r[j];
			L.r[j+dk]=L.r[0];
		}
}
void Shellsort(Sqlist &L,int dt[],int t)
{
	int i;
	for(i=0;i<t;i++)
	Shellinsert(L,dt[i]);
}
/*
dk表示每次直接插入排序的分组增量
dt[]数组存储这些增量，即增量序列（其中增量之间应没有除1之外的公因子）
t表示所用的增量的个数
*/

希尔排序即为直接插入排序的推广和优化，即采用若干个分量将数据记录分为若干个小组，对每个小组进行直接插入排序，目的就是为了减少数据移动的次数，最后再用增量为1进行一次完整的直接插入排序。（理解增量的意义：若增量为5，则是第1个数据与第6个数据为一组）
时间复杂度：O(n^3/2)
O(n^1.3)
空间复杂度：O(1)
稳定性：是跳跃式的，所以不稳定
不可用链式结构，适用于n较大且数据无序

交换排序—冒泡排序

void Bubblesort(Sqlist &L)
{
	int m=L.length;
	int flag=1,i,j;
	RedType t;
	while((m>0)&&(flag==1))
	{
		flag=0;
		for(j=1;j<m;j++)
			if(L.r[j].key>L.r[j+1].key)
			{
				flag=1;
				t=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=t;
			}
			m--;
	}
}

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定
可用于链式结构，当初始记录无序，n较大时不宜采用

交换排序—快速排序

int Partition(Sqlist &L,int low,int high)
{
	int pivotkey;
	L.r[0]=L.r[low];
	pivotkey=L.r[low].key;
	while(low<high)
	{
		while(low<high&&L.r[high].key>=pivotkey) high--;
		L.r[low]=L.r[high];
		while(low<high&&L.r[low].key<=pivotkey) low++;
		L.r[high]=L.r[low];
	}
	L.r[low]=L.r[0];//注意这里是最后才对枢纽位置赋值，减少移动次数
	return low;
}
void Qsort(Sqlist &L,int low,int high)
{
	int pivotkey;
	if(low<high)//确定长度大于1
	{
		pivotkey=Partition(L,low,high);
		Qsort(L,low,pivotkey-1);
		Qsort(L,pivotkey+1,high);
	}
}
void Quicksort(Sqlist &L)
{
	Qsort(L,1,L.length);
}
  • pivotkey 是一个中间枢纽，其左右为两个子表，首先就是根据枢纽数据交换左右数据，求出枢纽位置，使左侧数据比枢纽数据小，右边比其大
  • 之后递归继续对其左右子表进行求枢纽分隔排序直到所有左右子表都只有一个数据时递归终止

时间复杂度：O(nlog2n)
空间复杂度：O(log2n)~O(n) (递归过程中调用栈所占用的空间)
稳定性：不稳定
难以用链式结构，适用于n较大，初始数据无序（n较大时平均速度是内部排序中最快的）

选择排序—简单选择排序（直接选择排序）

void Selectsort(Sqlist &L)
{
	RedType t;
	int i,j,k;
	for(i=1;i<L.length;i++)
	{
		k=i;
		for(j=i+1;j<=L.length;j++)
			if(L.r[j].key<L.r[k].key) k=j;
		if(k!=i)
		{t=L.r[i];L.r[i]=L.r[k];L.r[k]=t;}
	}
}
  • 就是对n个数据进行n-1次查找，先找出一个最小值，之后每次都在已排好序列之后找出一个最小的值，将其交换到前面，只要知道怎么遍历求最小值即可

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：理论上稳定，但因为有交换数据的代码，可能会出现不稳定现象
可以用链式结构

选择排序—树形选择排序

  • 为了减少简单选择排序中的比较次数，树形选择排序将n个数据两两比较选出较小值，再在这些较小值之间继续选择，由此构造完全二叉树，则根结点即为最小值，之后将根结点原本终端结点位置数据改为无穷，再次比较，可求出次大值

时间复杂度：O(nlog2n)
空间复杂度：辅助空间占用较多

选择排序—堆排序

  • 堆的定义：当一个序列按照完全二叉树排列后，其所有双亲结点都大于等于其孩子结点或者小于等于其孩子结点，则该序列为一个堆
  • 大根堆：根结点为最大值的堆；小根堆：根结点为小结点的堆
void Heapadjust(Sqlist &L,int s,int m)
{
	RedType rc;
	int j,m,s;
	rc=L.r[s];
	for(j=2*s;j<=m;j*=2)
	{
		if(j<m&&L.r[j].key<L.r[j+1].key) j++;
		if(rc.key>=L.r[j].key) break;
		L.r[s]=L.r[j]; s=j;
	}
	L.r[s]=rc;
}
void Creatheap(Sqlist &L)
{
	int n,i;
	n=L.length;
	for(i=n/2;i>0;i--)
	Heapadjust(L,i,n);
}
void Heapsort(Sqlist &L)
{
	RedType x;
	int i;
	Creatheap(L);
	for(i=L.length;i>1;i--)
	{
		x=L.r[1];
		L.r[1]=L.r[i];
		L.r[i]=x;
		Heapadjust(L,1,i-1);
	}
}

代码分为堆调整，建初堆，堆排序三个部分

  • 堆排序就是首先建立大根堆，（为将其排成小根堆），每次将根结点与此时最末位结点交换，再调用堆调整将其调成大根堆，直到最后的大根堆中只剩一个根结点。注意这里的树并没有链式关系，只是以序列位置按照完全二叉树来排列，故每次交换都会筛选出一个当前的最大值在序列后方排列好，之前的序列再继续交换。
  • 堆调整是认为r[s+1…m]已经是一个堆，此时加入r[s]后再将其调整为一个新堆，即对于加入的根结点，交换结点，将其调整为一个新的符合堆关系的完全二叉树序列
  • 建初堆是从完全二叉树序列的最后一个非终端结点开始直到根结点，均进行堆调整以建成大根堆或小根堆

时间复杂度：O(nlog2n)
空间复杂度：O(1)
稳定性：不稳定
只可用于顺式结构，不可用于链式
记录较少时不宜采用，数据较多时高效

归并排序—2-路归并

void Merge(RedType R[],RedType T[],int low,int mid,int high)
{
	int i=low,j=mid+1,k=high;
	while(i<=mid&&j<=high)
	{
		if(R[i].key<=R[j].key) T[k++]=R[i++];
		else T[k++]=R[j++];
	}
	while(i<=mid) T[k++]=R[i++];
	while(j<=high) T[k++]=R[j++];
}
void Msort(RedType R[],RedType T[],int low,int high)
{
	int mid;
	RedType S[MAXSIZE+1];
	if(low==high) T[low]=R[low];
	else
	{
		mid=(high+low)/2;
		Msort(R,S,low,mid);
		Msort(R,S,mid+1,high);
		Merge(S,T,low,mid,high);
	}
}
void Mergesort(Sqlist &L)
{
	Msort(L.r,L.r,1,L.length);
}
  • 归并排序就是把两个或两个以上的有序表归并为一个有序表，2-路归并即为归并两个有序表
  • 算法思想：将一个长度为n的序列看成是n个长度为1的子序列，然后相邻的两个序列不断两两合并直到得到一个有序序列即可
  • 算法步骤分为合并和整体的归并排序，合并就是实现将一个有序表中的两个子序列排序后放入一个新表中；归并排序就是先不断递归分裂至n个子序列，然后调用合并算法归并回来
  • 时间复杂度：O(nlog2n)
  • 空间复杂度：O(n)
  • 稳定性：稳定
  • 可用于链式结构
上一篇：快速排序


下一篇：LeetCode-099-恢复二叉搜索树