萍乡中学排序

排序排序的分类O(n2)的排序冒泡排序插入排序选择排序（不稳定的）O(nlog2n)的排序二叉排序树排序归并排序快排（不稳定的）堆排（不稳定的）冒泡排序首先将所有待排序的数字放入工作列表中。从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。重复2号步骤，直至再也不能交换。冒泡排序的平均时间复杂度为平方级的，效率不高，但是容易实现。插入排序首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。重复2号步骤，直至原数列为空。插入排序的平均时间复杂度也是平方级的，效率不高，但是容易实现。它借助了“逐步扩大成果”的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。选择排序设数组内存放了n个待排数字，数组下标从1开始，到n结束。i=1从数组的第i个元素开始到第n个元素，寻找最小的元素。将上一步找到的最小元素和第i位元素交换。如果i=n-1算法结束，否则回到第3步选择排序的平均时间复杂度也是O(n^2)的。快速排序快排的基本思想：把待排序的数据读入一维数组，选取数组中的某个元素的值a[i]作为关键字，再采用分治策略，把小于a[i]的所有数据放在左区间，大于a[i]的放在右区间，一分为二，左区间的所有元素小于等于右区间的元素。然后再对左右区间重复上面的操作，直到左右区间都仅有一个元素，排序成功。如：原数据：75634210初始时：l=1,r=8,mid=4第一轮：056342170和7交换后：l=2,r=7第二轮：01634257

5和1交换后：l=3,r=6第三轮：01234657

2和6交换后：l=4,r=5第四轮：012,3,46573和4不交换，l=4,r=4，形成左右区间快速排序快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。归并排序归并排序的基本思想：归并排序充分应用分治算法的策略，将n个数分成n个单独的有序数列，每个数列中仅有一个数字；再将相邻的两列数据合并成一个有序数列，每个数列中有2个数（最后一列可能仅有一个数)；再重复上面的合并操作，直到合成一个有序数列。按照分治三步法来说：（1）划分：把序列分成元素个数相等的两半；（2）递归求解：把两半分别排序；（3）合并：把两个有序表合成一个有序表；如：原数据：75634210第一轮：7，5，6，3，4，2，1，0第二轮：57，36，24，01第三轮：3567，0124第四轮：01234567归并排序显然，前两部分是很容易完成的，关键在于如何把两个有序表合成一个。每次只需要把两个有序表中当前的最小元素加以比较，删除较小元素并加入合并后的新表中。归并排序核心参考代码procedureMergeSort(left,right:integer)//归并排序beginifleft=rightthenexit;//只有一个元素mid:=(left+right)div2;//找中间位

MergeSort(left,mid);//对左边归并

MergeSort(mid+1,right);//对右边归并

i:=left;j:=mid+1;p:=left;//合并左右while(i<=midandj<=right)do

if(a[i]>a[j])thenbegintemp[p]:=a[j];inc(p);inc(j);endelsebegintemp[p]:=a[i];inc(p);inc(i);end;while(i<=mid)dobegintemp[p]:=a[i];inc(p);inc(i);endwhile(j<=right)dobegintemp[p]:=a[j];inc(p);inc(i);endfori:=lefttorightdoa[i]:=temp[i];

End;归并排序合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。堆排序堆的定义：n个元素的序列{a1,a2,…,an}当且仅当满足如下关系时，称之为堆(heap)。(1)ai>=a2*i且ai>=a2*i+1(i=1,2,……,ndiv2)大根堆(2)ai<=a2*i且ai<=a2*i+1(i=1,2,……,ndiv2)小根堆877853456509311723123456789877853456509311723123456789大根堆91765234578875331123456789小根堆91765234578875331123456789堆排序堆的关键操作：建堆维护堆堆(以小根堆为例)3建堆开始……65752313877152163613建堆完毕……算法描述（建堆）procedurebuild;fori:=1tondoread(x);push(x);endf;endp;begininc(num);a[num]:=x;j:=x;i:=num;whilea[idiv2]>a[i]doswap(i,idiv2);i:=idiv2;endw;end;堆——选择与维出堆顶节点71273728833868一、取出二、调整算法描述（堆排序）proceduresort;build;fori:=1tondowriteln(a[1]);delete(1);endp;类似于push,不过push是把小元素向上换，delete是把最小的删掉后，把最后一个元素放上来，这样就变成了把一个大元素向下放的过程，具体方法请自己思考。堆排序算法PROCshift(varr:listtype;k,m:integer);beigni:=k.j:=2*I;x:=r[k].key;finish:=false;t:=r[k];while(j<=m)andnotfinishdobeginif(j<m)andr[j].key>r[j+1].key)thenj:=j+1;ifx<=r[j].keythenfinish:=trueElsebeginr[i]:=r[j];i:=j;j:=2*Iend;end;r[i]:=t;End;PROCheapsort(varr:listtype);Fori:=ndiv2downto1shift(r,I,n);Fori:=ndownto2do[r[1]与r[i]交换;shift(r,1,i-1)]endP堆排序堆排序适合于数据量非常大的场合（百万数据）。堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。二叉排序树二叉排序树是具有以下性质的非空二叉树：若根的左子树不空，则左子树的所有结点值均小于根结点值；若根的右子树不空，则右子树的所有结点值均不小于根结点值；根结点的左、右子树也分别为二叉排序树。例：输入序列a1,a2……an（1<=n<=1000），将a按照递增顺序排列后输出。构造二叉排序树的方法：令a1为二叉树的根；若a2<a1，则令a2为a1左子树的根结点，否则令a2为a1右子树的根结点；对a3，a4……an递归重复②。二叉排序树例：a序列为：35403090823233373540309082323337中序遍历：3032333537408290二叉排序树定义：Constm=树中结点数上限;Typenode=recordkey:keytype;left,right,p:0..m;end;Treetype=array[1..m]ofnode;Varbst:treetype;二叉排序树procedurecreatetree;beginfillchar(b,sizeof(b),0);b[1].key:=a[1];fori:=2tondobeginb[i].key:=a[i];p:=1;whiletruedoifa[i]<b[p].keythenifb[p].l<>0thenp:=b[p].lelsebeginb[p].l:=i;break;endelseifb[p].r<>0thenp:=b[p].relsebeginb[p].r:=i;break;end;end;end;二叉排序树主程序Beginreadln(n); fori:=1tondoread(a[i]);writeln;createtree;ino