【笔记】大话数据结构-排序

排序的稳定性

排序前相等的两个关键字的记录r1与r2，此时r1在r2前面，排序后若仍然是r1在r2前面，则为稳定的；否则不稳定。

内排序与外排序

内排序：排序过程中，待排序所有记录全部放在内存中。
外排序：记录过多，不能同时放在内存，整个排序过程需要内外存之间多次交换数据。

冒泡排序

void BubbleSort(Sqlist *L)
{
	int i,j;
	for(i=1;i<L->length;i++)
	{
		for(j=L->length-1;j>=1;j--)
		{
			if(L->r[j]>L->r[j+1])
			{
				swap(L,j,j+1);
			}
		}
	}
}

3. 冒泡排序优化：减少没有交换数据的循环。

void BubbleSort(Sqlist *L)
{
	int i,j;
	Status flag=TRUE;	//flag做标记
	for(i=1;i<L->length && flag;i++)
	{
		flag = FALSE;
		for(j=L->length-1;j>=1;j--)
		{
			if(L->r[j]>L->r[j+1])
			{
				swap(L,j,j+1);
				flag = TRUE;
			}
		}
	}
}

复杂度：O(n²)

简单选择排序

通过n-1次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1≤i≤n)个记录交换之。

void SelectSort(SqList *L)
{
	int i,j,min;
	for(i=1;i<L->length;i++)
	{
		min=i;
		for(j=i+1;j<=L->length;j++)
		{
			if(L->r[min]>L->r[j])
				min=j;
		}
		if(i!=min)
			swap(L,i,min);
	}
}

复杂度：O(n²)

直接插入排序

将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

void InsertSort(SqList *L)
{
	int i,j;
	for(i=2;i<L->length;i++)
	{
		if(L->r[i]<L->r[i-1])	//若后一个小于前一个
		{
			L->r[0]=L->r[i];	//后一个赋值到哨兵
			for(j=i-1;L->r[j]>L->r[0];j--)	//从前一个开始若前一个大于第一个则再向前一个
				L->r[j+1]=L->r[j];	//后一个等于前一个
			L->r[j+1]=L->r[0];	//插入
		}
	}
}

复杂度：O(n²)

希尔排序

选择一个“增量”，每次比较相隔此增量的两个关键字；然后改变增量，直到最后增量为1，相当于直接插入排序。

vodi ShellSort(SqList *L)
{
	int i,j;
	int increment=L->Length;
	do
	{
		increment=increment/3+1;
		for(i=increment+1;i<L->Length;i++)
		{
			if(L->r[i]<L->r[i-increment])
			{
				L->r[0]=L->r[i]
				for(j=i-increment;j>0&&L->r[0]<L->r[j];j-=increment)
					L->r[j+increment]=L->r[j];
				L->[j+increment]=L->r[0];
			}
		}
	}while(increment>1);
}

复杂度：当增量序列为dlta=2^t-k+1-1(0≤k≤t≤[log₂(n+1)])时，复杂度O(n^3/2)，优于直接排序的O(n²)。需注意，增量序列最后一个增量值必须为1。

堆排序

堆：是一种完全二叉树。每个结点的值都≥左右孩子，称为大顶堆；每个结点的值都≤左右孩子，称为小顶堆。
堆排序：（假设是大顶堆）将待排序序列构造成大顶堆。整个序列最大值就是堆顶根节点，将它与堆数组末尾元素交换，将剩下n-1个序列重新构造成堆。同理，反复执行。

void HeapSort(SqList *L)
{
	int i;
	for(i=L->Length/2;i>0;i--)	//为length/2的原因是刚好i就是有左右孩子的所有结点
		HeapAdjust(L,i,L->Length);

	for(i=L->Length;i>1;i--)
	{
		swap(L,1,i);
		HeapAdjust(L,1,i-1);	//重新构造堆
	}
}

void HeapAdjust(SqList *L,int s,int m)
{
	int temp,j;
	temp=L->r[s];
	for(j=2*s;j<=m;j*=2)
	{
		if(j<m&&L->r[j]<L->r[j+1])
			++j;
		if(temp>L->r[j])
			break;
		L->r[s]=L->r[j];
		s=j;
	}
	L->[s]=temp;
}

复杂度：O(nlogn)

归并排序

n个记录看作n个长度为1的有序子序列，然后两两归并，得到⌈n/2⌉(向上取整)个长度为2或1的有序子序列；再两两归并，……；重复操作，直到得到长度为n的有序序列为止；这种方法称为2路归并排序。

void MergeSort(SqList *L)
{
	MSort(L->r,L->r,1,L->length);
}
void MSort(int SR[],int TR1[],int s,int t)
{
	int m;
	int TR2[MAXSIZE+1];
	if(s==t)
		TR1[s]=SR[S];
	else 
	{
		m=(s+t)/2;
		MSort(SR,TR2,s,m);	//得到TR2[s,...,m]
		MSort(SR,TR2,m+1,t);	//得到TR2[m+1,...,t]
		Merge(TR2,TR1,s,m,t);
	}
}
void Merge(int SR[],int TR[],int i,int m,int n)
{
	int j,k,l;
	for(j=m+1,k=i;i<=m&&j<=n;k++)
	{
		if(SR[i]<SR[j])
			TR[k]=SR[i++];
		else
			TR[k]=SR[j++];
	}
	if(i<=m)	//将归并剩下的数组数据移动到TR后面
	{
		for(l=0;l<=m-i;i++)
			TR[k+1]=SR[i+1];			
	}
	if(j<=n)	//将归并剩下的数组数据移动到TR后面
	{	
		for(l=0;l<=n-j;j++)
			TR[k+1]=SR[j+1];
	}
}

复杂度：O(nlogn)

快速排序

通过一趟排序将待排序列分成两独立部分，其中一部分关键字比另一部分小，重复此过程。

void QuickSort(SqList *L)
{
	QSort(L,1,L->Length);
}
void QSort(SqList *L,int low,int high)
{
	int pivot;
	if(low<high)
	{
		pivot=Partition(L,low,high);
		QSort(L,low,pivot-1);
		QSort(L,pivot,high);
	}
}
int Partition(SqList *L,int low,int high)
{
	int pivotkey;
	pivotkey=L->r[low];
	while(low<high)
	{
		while(low<high&&L->r[high]>=pivotkey)
			high--;
		swap(L,low,high);
		while(low<high&&L->[low]<=pivotkey)
			low++;
		swap(L,low,high);
	}
	return low;
}

复杂度：最优O(nlogn)，最坏O(n²)。平均O(nlogn)。
快排优化：1.优化选取枢轴（三数取中、九数取中）2.优化不必要交换（交换改为替换）3.优化小数组时排序方案（小数组采用直接插入排序）4.优化递归操作