排序算法总结.doc

排序算法总结排序算法总结1、稳定排序和非稳定排序简单地说就是所有相等的数经过某种排序方法后,仍能保持它们在排序之前的相对次序,我们就说这种排序方法是稳定的。反之,就是非稳定的。比如:一组数排序前是a1,a2,a3,a4,a5,其中a2=a4,经过某种排序后为a1,a2,a4,a3,a5,则我们说这种排序是稳定的,因为a2排序前在a4的前面,排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。2、内排序和外排序在排序过程中,所有需要排序的数都在内存,并在内存中调整它们的存储顺序,称为内排序;在排序过程中,只有部分数被调入内存,并借助内存调整数在外存中的存放顺序排序方法称为外排序。3、算法的时间复杂度和空间复杂度所谓算法的时间复杂度,是指执行算法所需要的计算工作量。一个算法的空间复杂度,一般是指执行这个算法所需要的内存空间。功能:选择排序输入:数组名称(也就是数组首地址)、数组中元素个数算法思想简单描述:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。选择排序是不稳定的。【篇二:排序算法总结】在计算机科学所使用的排序算法通常被分类为:计算的复杂度(最差、平均、和最好性能),依据列表(list)的大小(n)。一般而言,好的性能是O(nlogn),且坏的性能是O(n2)。对于一个排序理想的性能是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要O(nlogn)。内存使用量(以及其他电脑资源的使用)稳定度:稳定排序算法会依照相等的关键(换言之就是值)维持纪录的相对次序。也就是一个排序算法是稳定的,就是当有两个有相等关键的纪录R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前。一般的方法:插入、交换、选择、合并等等。交换排序包含冒泡排序和快速排序。选择排序包含希尔排序和堆排序【篇三:排序算法的总结】基数、冒泡、插入、简单选择、归并是稳定的,快速、堆、希尔是不稳定的。一、插入排序一)直接插入排序定义:直接插入排序(straightinsertionsort)是一种最简单的排序方法。它的基本操作是将一个记录插入到一个长度为m(假设)的有序表中,使之仍保持有序,从而得到一个新的长度为m,1的有序表。算法思路:设有一组关键字,K1,K2,,Kn,;排序开始就认为K1是一个有序序列;让K2插入上述表长为1的有序序列,使之成为一个表长为2的有序序列;然后让K3插入上述表长为2的有序序列,使之成为一个表长为3的有序序列;依次类推,最后让Kn插入上述表长为n-1的有序序列,得一个表长为n的有序序列。算法时间复杂度:此算法外循环n-1次,在一般情况下内循环平均比较次数的数量级为,(n),所以算法总时间复杂度为,(n2)。直接插入排序的稳定性:直接插入排序是稳定的排序方法二)折半插入排序定义:当直接插入排序进行到某一趟时,对于r【i】。key来讲,前边i-1个记录已经按关键字有序。此时不用直接插入排序的方法,而改为折半查找,找出r【i】。key应插的位置,然后插入。三)2-路插入排序四)表插入排序五)希尔排序定义:希尔排序(shellsort)是D(,(希尔(D。L。Shell)提出的缩小增量的排序方法。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步(增量较大)间隔比较,使记录跳跃式接近它的排序位置;然后增量缩小;最后增量为1,这样记录移动次数大大减少,提高了排序效率。希尔排序对增量序列的选择没有严格规定。算法思路:?。先取一个正整数d1(d1;n),把全部记录分成d1个组,所有距离为d1的倍数的记录看成一组,然后在各组内进行插入排序;?。然后取d2(d2d1)。?。重复上述分组和排序操作;直到取di=1(i=1),即所有记录成为一个组为止。一般选d1约为n/2,d2为d1/2,d3为d2/2,,di=1。二、交换排序交换排序主要是根据记录的关键字的大小,将记录交换来进行排序的。交换排序的特点是:将关键字值较大的记录向序列的后部移动,关键字较小的记录向前移动。这里介绍两种交换排序方法,它们是冒泡排序和快速排序。一)冒泡排序将被排序的记录数组R【1、n】垂直排列,每个记录R【i】看作是重量为R【i】。key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上飘浮。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。1、算法思路(1)让j取n至2,将r【j】。key与r【j-1】。key比较,如果r【j】。keyr【j-1】。key,则把记录r【j】与r【j-1】交换位置,否则不进行交换。最后是r【2】。key与r【1】。k