第九章， 排序 学习笔记

排序：假设含有n个记录的序列为{}，其相应的关键字分别为{}，需确定1，2，......，n的一种排列，使其相应的关键字满足（非递减或非递增）关系，即使使得序列成为一个按关键字有序的序列{},这样的操作就称为排序。

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

本章一共要讲解七种排序的算法，按照算法的复杂度分为两大类，冒泡排序、简单选择排序和直接插入排序术语简单算法，而希尔排序、堆排序、归并排序、快速排序术语改进算法 

排序用到的结构和函数

#define MAXSIZE 10000  
typedef struct
{
	int r[MAXSIZE+1];	
	int length;			
}SqList;


void swap(SqList *L,int i,int j) 
{ 
	int temp=L->r[i]; 
	L->r[i]=L->r[j]; 
	L->r[j]=temp; 
}

冒泡排序（Bubble Sort）：一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录位置。

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

上边是初级冒泡算法，下边是正宗的

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

 冒泡排序优化：增加一个标记变量flag来实现这一算法的改进：

void BubbleSort2(SqList *L)
{ 
	int i,j;
	Status flag=TRUE;			
	for(i=1;ilength && flag;i++) 
	{
		flag=FALSE;				
		for(j=L->length-1;j>=i;j--)
		{
			if(L->r[j]>L->r[j+1])
			{
				 swap(L,j,j+1);	
				 flag=TRUE;		
			}
		}
	}
}

简单选择排序

        简单选择排序法（Simple Selection Sort）就是通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1≤i≤n） 个记录交换之。

void SelectSort(SqList *L)
{
	int i,j,min;
	for(i=1;ilength;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);				
	}
}

---

直接插入排序

直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

void InsertSort(SqList *L)
{ 
	int i,j;
	for(i=2;i<=L->length;i++)
	{
		if (L->r[i]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]; 
		}
	}
}

---

希尔排序

void ShellSort(SqList *L)
{
	int i,j,k=0;
	int increment=L->length;
	do
	{
		increment=increment/3+1;
		for(i=increment+1;i<=L->length;i++)
		{
			if (L->r[i]r[i-increment]) 
			{ 
				L->r[0]=L->r[i]; 
				for(j=i-increment;j>0 && L->r[0]r[j];j-=increment)
					L->r[j+increment]=L->r[j]; 
				L->r[j+increment]=L->r[0]; 
			}
		}
		printf("	第%d趟排序结果: ",++k);
		print(*L);
	}
	while(increment>1);

}

---

堆排序

        堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。 

 

         堆排序（Heap Sort）：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列。

void HeapSort(SqList *L)
{
	int i;
	for(i=L->length/2;i>0;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(jr[j]r[j+1])
			++j; 
		if(temp>=L->r[j])
			break; 
		L->r[s]=L->r[j];
		s=j;
	}
	L->r[s]=temp; 
}

---

 归并排序

归并排序（Merging Sort）就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]([x]表示不小于x的最小整数)个长度为2或1的有序子序列；再两两归并，.........，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。

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);		
		MSort(SR,TR2,m+1,t);	
		Merge(TR2,TR1,s,m,t);	
	}
}


void MergeSort(SqList *L)
{ 
 	MSort(L->r,L->r,1,L->length);
}


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] 

快速排序 
快速排序（Quick Sort）的基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。 
 
void QuickSort(SqList *L)
{ 
	QSort(L,1,L->length);
}


void QSort(SqList *L,int low,int high)
{ 
	int pivot;
	if(lowr[low]; 
	while(lowr[high]>=pivotkey)
			high--;
		 swap(L,low,high);
		 while(lowr[low]<=pivotkey)
			low++;
		 swap(L,low,high);
	}
	return low; 
}
 

 
 
 
 
 
（未完，）