插入与合并排序.txt

插入排序与合并排序的算法描述等

[] 表示一个块
{} 表示注释

kernel_code  kernel_code只考虑最一般的、最基本的情况，不作输入等检查，它不应该给外界直接调用。

//插入排序
{逻辑结构：线性表}
算法思想：
1。从第二个元素开始，依次取出各个数据元素。
2。取出的数据元素跟已经有序的序列作比较，从右往左，至到所有数据比较完毕，或找到一个比取出元素要小的元素为止，设这个元素的位序为i。
3。把取出的数据元素插入到i+1处。

//算法描述
InsertSort( LinearListA )
	for i=2 to Length(LinearListA) do
	[
		x = GetElement(LinearListA, i);
		j = i-1;
		while j>0 and GetElement(LinearListA,j)>x
		[
			SetElement(LinearListA,j+1, GetElement(LinearListA,j)); // 元素后移
			j--;
		]
		SetElement(LinearListA,j+1);
	]
{InsertSort end}

//算法时间复杂度（最坏）
O(n^2)



// 代码实现
/// 存储结构：顺序表--基本数组
// kernel_code 
template< typename T >
void	InsertSort( 
				   T LinearList[], 
				   const int nListLen 
				   )
{
	int  nTotalPos = 0;
	for ( nTotalPos = 1; nTotalPos < nListLen; nTotalPos ++ )
	{
		T  element = LinearList[nTotalPos];
		int  nSortedPos = nTotalPos - 1;
		while ( nSortedPos >= 0 && LinearList[nSortedPos] > element )
		{
			LinearList[nSortedPos+1] = LinearList[nSortedPos];
			nSortedPos --;
		}

		LinearList[nSortedPos+1] = element;
	}
}

*******************************

//合并两个已经排好序的线性表
{逻辑结构：线性表}
{存储结构：顺序表}
算法思想：
1。初始化。产生一个线性表LinearListC，表长预定为Length(LinearListA)+Length(LinearListB)。
2。i=1, j=1, k=1分别代表LinearListA、LinearListB和LinearListC的位序。
3。同时从LinearListA和LinearListB中取出两个数据元素x和y并作比较，如果x<=y，则把x插入到LinearlistC并
i=i+1,k=k+1，否则把y插入到LinearListC并j=j+1,k=k+1。
4。如果LinearListA已经全部取完，则把LinearListB中剩下的数据无素依序插入到LinearListC中，否则把
LinearListB中剩下的元素依序插入到LinearListC中。

//算法描述
Merge( L[], R[] )
	n1 = Length(L);
	n2 = Length(R);
	// create new LinearList and initial
	A = CreateList[1..(n1+n2)];
	i = 1;
	j = 1;
	k = 1;
	while i<=n1 and j<=n2 
	[
		x = L[i];
		y = R[j];
		if x <= y 
		[
			A[k] = x;
			i = i + 1;
			k = k + 1;
		]
		else 
		[
			A[k] = y;
			j = j + 1;
			k = k + 1;	
		]
	]
	while i<=n1
	[
		A[k] = L[i]
		i = i + 1;
		k = k + 1;
	]
	while j<n2
	[
		A[k] = R[j];
		j = j + 1;
		k = k + 1;
	]
{Merge end}

//算法时间复杂度（最坏）
O(n)

// 代码实现
/// 存储结构：顺序表--基本数组
// kernel_code
template<typename T>
void	MergeSortedList( 
						const T L[], 
						const int nLLen, 
						const T R[], 
						const int nRLen,
						T A[]  // 输出
						)
{
	int nLPos = 0;
	int nRPos = 0;
	int nAPos = 0;

	while ( nLPos < nLLen && nRPos < nRLen )
	{
		T  leftElement = L[nLPos];
		T  rightElement = R[nRPos];
		if ( leftElement <= rightElement )
		{
			A[nAPos] = leftElement;
			nAPos ++;
			nLPos ++;
		}
		else 
		{
			A[nAPos] = rightElement;
			nAPos ++;
			nRPos ++;
		}
	}

	while ( nLPos < nLLen )
	{
		A[nAPos] = L[nLPos];
		nAPos ++;
		nLPos ++;
	}
	while ( nRPos < nRLen )
	{
		A[nAPos] = R[nRPos];
		nAPos ++;
		nRPos ++;
	}
}


//在同一个线性表中合并这个线性表中已经排好序的两个部分的数据
{逻辑结构：线性表}
{存储结构：顺序表}
{数据特点：在同一个线性表}
{算法特点：产生两个新的线性表并在表尾加上无穷大的数，避免最后判断某张表是否已经取完}
算法思想：
1。初始化。假设要合并的两部分数据的个数分别为n1和n2。
产生两个线性表LinearListA和LinearListB，长度分别设为(n1+1)和(n2+1)。
2。把原始线性表LinearListC中要合并的两部分数据分别拷贝到LinearListA和LinearListB。
3。在LinearListA和LinearListB末尾分别加入一个无穷大的数。
4。i=1, j=1, k=p分别代表LinearListA、LinearListB和LinearListC的位序。
5。同时从LinearListA和LinearListB中取出两个数据元素x和y并作比较，如果x<=y，则把x插入到LinearlistC并
i=i+1,k=k+1，否则把y插入到LinearListC并j=j+1,k=k+1。
6。当插入基本操作达到(n1+n2)次时，算法结束。

//算法描述
Merge( srcList, p, q, r )  
// srcList为原始线性表，p到q为已排序的数据集1，p+1到r为已排序的数据集2
	n1 = q - p + 1;
	n2 = r - q;
	// create two new LinearList and initial
	L = CreateList[1..(n1+1)];
	R = CreateList[1..(n2+1)];
	// copy
	for i=1 to n1
	[
		L[i] = srcList[p+i-1];	
	]
	for j=1 to n2
	[
		R[i] = srcList[q+j];
	]
	// 分别加入一个无穷大的数InfiniteNum
	L[n1+1] = InfiniteNum;
	R[n2+1] = InfiniteNum;

	i = 1;
	j = 1;
	for k=p to r
	[
		x = L[i];
		y = R[j];
		if x <= y 
		[
			A[k] = x;
			i = i + 1;
		]
		else 
		[
			A[k] = y;
			j = j + 1;
		]
	]
{Merge end}

//算法时间复杂度（最坏）
O(n)

// 代码实现
/// 存储结构：顺序表--基本数组
////// 按照算法描述本来应该给新产生的线性表加入“哨兵值”，但由于不知客户指定的数据类型故
////// 无法加入。没有找到解决方法，暂时使用最后判断表是否取完的方法。
// kernel_code
template< typename T >
void	MergeSortedList( 
						T  srcList[],
						const int leftPos, 
						const int midPos, 
						const int rightPos
						)
{
	int	nLeftListLen = midPos - leftPos + 1;
	int nRightListLen = rightPos - midPos;
	T * pLeftList = new T[nLeftListLen];
	T * pRightList = new T[nRightListLen];

	for ( int nLeftPos = 0; nLeftPos < nLeftListLen; nLeftPos ++ )
	{
		pLeftList[nLeftPos] = srcList[leftPos + nLeftPos];
	}
	for ( int nRightPos = 0; nRightPos < nRightListLen; nRightPos ++ )
	{
		pRightList[nRightPos] = srcList[ midPos + 1 + nRightPos ];
	}
	
	// how to add the infinite number when not know the type T?  so now cancel this operate

	int nLeftPos = 0;
	int nRightPos = 0;
	int nSrcPos = leftPos;
	while ( nLeftPos < nLeftListLen && nRightPos < nRightListLen )
	{
		T  leftElement = pLeftList[nLeftPos];
		T  rightElement = pRightList[nRightPos];
		if ( leftElement <= rightElement )
		{
			srcList[nSrcPos] = leftElement;
			nSrcPos ++;
			nLeftPos ++;
		}
		else 
		{
			srcList[nSrcPos] = rightElement;
			nSrcPos ++;
			nRightPos ++;
		}
	}
	while ( nLeftPos < nLeftListLen )
	{
		srcList[nSrcPos] = pLeftList[nLeftPos];
		nSrcPos ++;
		nLeftPos ++;
	}
	while ( nRightPos < nRightListLen )
	{
		srcList[nSrcPos] = pRightList[nRightPos];
		nSrcPos ++;
		nRightPos ++;
	}

	delete [] pLeftList;
	pLeftList = NULL;
	delete [] pRightList;
	pRightList = NULL;
}

*******************************************

//合并排序
{逻辑结构：线性表}
{存储结构：顺序表}
{使用上面的合并算法，非原地排序，因为Merge不能原地进行}
算法思想：
1。如果线性表的长度大于1，则把线性表从中间划分为LeftList和RightList两部分。
2。对LeftList递归的使用本算法完成自身的排序。
3。对RightList递归的使用本算法完成自身的排序。
4。合并LeftList和RightList。

//算法描述
MergeSort( LinearListA, p, r ) // LinearListA为线性表, p、r分别为要求排序的最小和最大位序
	if p < r 
	[
		// 取得中心点
		mid = (p+r)/2;
		// 递归完成自身的排序
		MergeSort(LinearListA, p, mid);
		MergeSort(LinearListA, mid+1, r);
		// 合并，这个算法在前面已经实现
		Merge(LinearListA, p, mid, r);
	]	
{MergeSort end}

//算法时间复杂度（最坏）
O(nlgn)

// 代码实现
/// 存储结构：顺序表--基本数组
// kernel_code
template< typename T >
void	MergeSort( 
				  T srcList[],
				  const int leftPos, 
				  const int rightPos
				  )
{
	if ( leftPos < rightPos )
	{
		int mid = (leftPos + rightPos) / 2;
		MergeSort( srcList, leftPos, mid );
		MergeSort( srcList, mid + 1, rightPos );
		MergeSortedList( srcList, leftPos, mid, rightPos );
	}
}