数学和计算机科学板块_辛酸网

数据结构与算法18

  如何使得无序的东西有序，这就得排序。一般来说只要不加特别说明都是数的升序排序。 在C/C++的考试中，如果没时间或者不会写排序的函数，那就直接调用头文件algorithm中的sort函数。排序问题的复杂度现在已有定论，最高效的算法时间复杂度也得有O(logn)。 人类历史上曾经有过各种各样的排序算法，甚至出现了像睡眠排序这样的奇怪作品——对所有要排序的数分别设立一个线程，数的大小即为线程睡眠时间，什么时候一个线程醒来， 就把这个时间记一下，然后把时间从前到后写一遍就是排序结果。【老人 地铁 手机】

  最简单的排序方法是冒泡排序：首先取第一个数作为【最大值】的暂定值，然后逐个和后面的数比较。 如果当前的【最大值】小于被比较数，则交换二者位置，并将那个数设为新的【最大值】。就这样，经过一轮处理后我们就挑出了整体的最大值，而且整体上这些数的有序性也得到了提高。 接下来如法炮制，挑选剩下的数中的最大值，也就是整体的第二大的数。n个数在经过n轮处理后就得到了n的最大值，也就成了一个有序数列。今有示例如下，'*'右是有序部分。

  注意，每一轮挑选最大值的时候，如果中间出现了【最大值】小于被比较数的情况，一定要交换顺序，这是和选择排序的根本区别。 因为这种对最大值的选取是由【最大值】从左向右冒泡的过程，所以他叫冒泡排序。显然，外有挑选最大值的轮，内有【最大值】与乱序部分的逐个比较之轮，故时间复杂度O(n²)。 对应C代码示例如下：

int* bubbling(int a[],int length)
{
	int max;
	int result[length];
	for(int i=0;i<length;i++)
	{
		max=a[0];
		for(int j=0;j<length-i;j++)
		{
			if(max<a[j]){int t=max;max=a[j];a[j]=t;}
		}result[length-i]=max;
	}return result;
}

  插入排序是这样的：将整个被排序内容分为有序部分为无序部分两大块。每次都要选取无序部分最前面的那个数，然后将其插入到有序部分里。 无序部分最前面的那个数，要和有序部分里的每一个数逐个比较，直到找到合适的位置——前一个小于等于它，后一个数大于等于它，这时它就插在两数中间以确保有序部分还是有序的。 因为这个插入的操作，插入排序就叫插入排序。平均来说，插入排序的时间复杂度也是O(n²)，但要是这个数列本来就有序，那只要O(n)的时间复杂度， 但要是反过来本就是降序还非得做升序排序，那就是最坏情况也是O(n²)的数量级。 同上，对[15 34 87 97 28 44 92 50 88 38]进行升序排序如下：

  对应代码如下：

node *insertsort(node *start,int length)
{//因为这里要插入，为了省时间就放弃数组改用链表了
	node* s=start;int sortedlen=2;//明确初始的有序与无序部分之边界
	node* firstnode=start;//新的起始结点地址
	while(sortedlen<=length)//大轮定位
	{
		for(j=0;j<sortlen;j++)s=s>next;//每一轮，找到要插入的元素
		if(s->value<firstnode->value){s->next=firstnode;firstnode=s;}//如果比最前面的还小就直接放在最前面
		else{//如果比最小的那个大，就一个个比较直到发现小于要插入的元素的那个结点，插入在其后
			node* p=firstnode;
			for(int j=0;j<sortlen;j++,p=p->next)//小轮比较
				if(s-&ft;value<p->value){s->next=p->next;p->next=s;break;}
		}
	sortedlen+=1;
	}return firstnode;
}

  选择排序和插入排序一样要把整个数列分为有序部分和无序部分，只不过，在选择排序中，有序部分是较小的那一部分， 而无序部分是较大的那一部分。每一轮只需要在无序部分中直接选取最小的哪一个，它同时也是大于等于有序部分最大的那个。于是，选取的整个元素直接放在有序部分的末尾， 成为新的有序部分的最大值。和冒泡排序相比，就是没有在无序部分中的交换工作。因为冒泡排序能让无序部分变得有序来加快工作，所以小规模中冒泡排序快于选择排序。 但是在大规模排序中，因为交换操作本身要消耗不少时间所以选择排序会快于冒泡排序。

  同上，选择排序过程如下：

  快速排序及归并排序都是分治算法，递归地反复将被排序元素分为左右两部分，然后合并子问题的解为整体的解。 快速排序是这样的：首先选取整体上的第一个元素作为基准，逐个和其它元素比较，凡是比它小的放在左边，比它大的放在右边。这样整体的序列化作左右两半， 凡是左半边的都小于右半边的，凡是右半边的都大于左半边的。接着对左右两半递归地进行快速排序。由于每次的子问题解合并代价，就是基准元素在整体上的逐个比较。 所以快速排序的时间复杂度满足前文所述的$\mathrm{f(n)=2f(}\frac{\mathrm{n}}{2}\mathrm{)+n}$， 画递归树很容易就能看出来，快速排序一般而言的时间复杂度为O(nlogn)。但在最坏情况下，基准元素两边长度差异巨大，使得一边几乎占了全部元素， 要是每一层都这样，那么快速排序就有了O(n²)的最坏时间复杂度。

  同样的，上例子：

  代码：

int quicksort(int a[],int length)
{
	if(length==1)return a;//长度为1直接返回
	else if(length==2)//长度为2，两数相比较安排好位置后返回
	{int b[2];b[0]=a[0]<a[1]?a[0]:a[1];b[1]=a[0]>a[1]?a[0]:a[1];return b;}
	else{
		int left[length],right[length];int leftlength=0,rightlength=0;//定义左右部分及其长度
		for(int i=1;i<length;i++)
		{
			if(a[0]>a[i]){left[leftlength]=a[i];leftlength++;}//比基准小的放在左边
			else{right[rightlength]=a[i];rightlength++;}//比基准大的放在右边
			quicksort(left,leftlength);quicksort(right,rightlength);//递归调用
			return mergearray(left,right);//合并为一个有序的大数组，合并用的代码自己编，可以用双指针算法
		}
	}
}

  归并排序则是没有基准直接分开：按照初始的乱序直接找到最中间的元素作为分界线将整体分为左右两半， 然后左右两部分分别递归地划为各自的左右两半，直到被分出来的片段长度为1或2为止。接着回溯，将左右两半，这些最小的片段进行合并，使其成为一个有序的大片段。 因为大片段也是更大的片段的一半，所以还要再往上继续合并，得到更大的有序的片段，直到整体的左右两半分别变得有序，再合并形成新的有序的整体。
  请看，先分后合：

  因为你可以在原地直接进行递归工作，归并排序的空间复杂度只有O(n)。代码如下：

int *mergesort(int a[],int length)
{
	if(length==1)return a;else if(length==2)
	{int b[2];b[0]=a[0]<a[1]?a[0]:a[1];b[1]=a[0]>a[1]?a[0]:a[1];return b;}
	else{
		int left[length/2]=a[0],right[length/2]=a[length/2+1];//左右相分，地址相传
		left=mergesort(left,length/2);right=mergesort(right,length/2);//递归
		return mergearray(left,right);
	}
}

辛酸网 ©版权所有