几种 排序算法,以及排序的算法.doc

常用的算法的时间复杂度和空间复杂度排序法最差时间分析平均时间复杂度稳定度空间复杂度冒泡排序O(n2)O(n2)稳定O(1)快速排序O(n2)O(n*log2n)不稳定O(log2n)O(n)选择排序O(n2)O(n2)稳定O(1)二叉树排序O(n2)O(n*log2n)不一顶O(n)插入排序O(n2)O(n2)稳定O(1)堆排序O(n*log2n)O(n*log2n)不稳定O(1)希尔排序OO不稳定O(1)1、时间复杂度（1）时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。（2）时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=(f(n),称(f(n) 为算法的渐进时间复杂度，简称时间复杂度。在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。 按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),.， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。 2、空间复杂度 与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。（3）渐进时间复杂度评价算法时间性能 主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。2、类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空I司复杂度与n成线性比例关系时，可表示为0(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。分类:数据结构及算法1. 排序 排序定义是将一个数据元素的任意序列，重新排列成为一个按关键字有序的序列 排序分类： 按待排序记录所在位置内在排序：待排序记录存放内存外部排序：外排序过程需对外存进行访问排序按排序依据原则： 插入排序：直接插入排序，折半插入排序，希尔排序 交换排序：冒泡排序，快速排序 选择排序：简单选择排序，堆排序 归并排序：2-路归并排序 基数排序插入排序（1） 直接插入排序每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。直接插入排序属于稳定的排序，最坏时间复杂性为O(n2)，空间复杂度为O(1)。public void Action(int array)for (int i = 1; i array.Length; i+)if (arrayi = 0 & tem arrayj; j-)arrayj + 1 = arrayj;arrayj+1 = tem;（二）折半插入排折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n2)，与直接插入排序算法相同。附加空间O(1)。#include typedef int ElemType ;ElemType arr=0,9,8,7,6,5,4,3,2,1;ElemType n=10,i,j;ElemType low,high,mid;void BinSort(ElemType r,ElemType n)for(i=2;in;i+)r0=ri;low=1; high=i-1;while (low=high)mid=(low+high)/2;if(r0=low;j-)ri=rj;i-;rlow=r0; void put(ElemType r,ElemType n)for(j=1;jn;j+)printf(%dt,rj);printf(n);void main()BinSort(arr,n);put(arr,n);（三 ）希尔排序先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2d1重复上述的分组和排序，直至所取的增量dt=1(dtdt-ld2d1)，即所有记录放在同一组中进行直接插入排序为止。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。Shell排序的算法实现:1 不设监视哨的算法描述void ShellPass(SeqList R，int d)/希尔排序中的一趟排序，d为当前增量for(i=d+1;i=n；i+) /将Rd+1n分别插入各组当前的有序区if(R i .key0&R0.key0) for(i=k;i=0&t0)for(int i = k;i= 0 & t =0 & t = k & t = k & t aj - k)aj = aj-k;j = j-k;aj = t;k /= 2;int main()int aN= 8,10,3,5,7,4,6,1,9,2;shellsort(a,sizeof(a)/sizeof(a0);for(int k = 0;k N;k+)printf(a%d = %dn,k,ak);return 0;交换排序（1） 冒泡排序void Bublesort(int a,int n) int i,j,k;for(j=0;jn;j+) /* 气泡法要排序n次*/ for(i=0;iai+1) /* 把值比较大的元素沉到底 */ k=ai; ai=ai+1; ai+1=k; （2） 快速排序void Quick_sort(int data,int low,int high) int mid; if(lowhigh) mid=Partition(data,low,high); Quick_sort(data,low,mid-1); /* 递归调用 */ Quick_sort(data,mid+1,high); int Partition(int data,int low,int high) int mid; data0=datalow; mid=datalow; while(low high) while(low = mid) -high; datalow=datahigh; /* 从high的位置开始往low的方向找，找到比datalow小的元素，存到datalow中 */while(low high) & (datalow mid) /* 新得到的datalow肯定小于原来的datalow即mid */ +low; datahigh=datalow; /* 从low的位置开始往high的方向找，找到比datahigh大的元素，存在datahigh中 */ datalow=data0; /* 把low的新位置存上原来的datalow据 */ return low; /* 递归时，把它做为右侧元素的low */ 选择排序（一） 简单选择排序设所排序序列的记录个数为n。i取1,2,n-1,从所有n-i+1个记录（Ri,Ri+1,Rn）中找出排序码最小的记录，与第i个记录交换。执行n-1趟 后就完成了记录序列的排序。#includemain()int a10,i,j,k,t;printf(input 10 numbers:n);for(i=0;i10;i+)scanf(%d,&ai);printf(n);for(i=0;i10;i+)k=i;for(j=i+1;jaj) k=j;if(k!=i) t=ai;ai=ak;ak=t;printf(the sorted numbers:n);for(i=0;i10;i+)printf(%-3d,ai);（二 ）堆排序 n个关键字序列Kl，K2，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：(1)ki=k(2i）且ki=号。/k(i）相当于二叉树的非叶子结点，K(2i）则是左子节点，k(2i+1）是右子节点若将此序列所存储的向量R1.n看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为O(1）.它是不稳定的排序方法。void HeapAdjust(int array, int i, int nLength)int nChild;int nTemp;for (nTemp = arrayi; 2 * i + 1 nLength; i = nChild)/ 子结点的位置=2*（父结点位置）+ 1nChild = 2 * i + 1;/ 得到子结点中较大的结点if ( nChild arraynChild)+nChild;/ 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点if (nTemp = 0; -i)HeapAdjust(array, i, length);/ 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素for (int i = length - 1; i 0; -i)/ 把第一个元素和当前的最后一个元素交换，/ 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的/ Swap(&array0, &arrayi);tmp = arrayi;arrayi = array0;array0 = tmp;/ 不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值HeapAdjust(array, 0, i);归并排序归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。#includeusing namespace std;void Merge(int a,int low,int mid,int high,int b);void MSort(int a,int low,int high,int b);void main()int a=4,5,9,10,51,6,46,36,6,56,67,45,36;int b13;MSort(a,0,12,b);for(int i=0;i13;i+)coutbi ;coutendl;for(int j=0;j13;j+)coutaj ;coutendl; void Merge(int a,int low,int mi