排序算法总结
【篇一：排序算法总结】
1、稳定排序和非稳定排序
简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。反之，就是非稳定的。
比如：一组数排序前是a1，a2，a3，a4，a5，其中a2=a4，经过某种排序后为a1，a2，a4，a3，a5，
则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1，a4，a2，a3，a5就不是稳定的了。
2、内排序和外排序
在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；
在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。
所谓算法的时间复杂度，是指执行算法所需要的计算工作量。一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。
功能：选择排序
输入：数组名称（也就是数组首地址）、数组中元素个数
算法思想简单描述：
在要排序的一组数中，选出最小的一个数与第一个位置的数交换励志网http://wWw.qqZf.cN/；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。选择排序是不稳定的。
【篇二：排序算法总结】
在计算机科学所使用的排序算法通常被分类为：
计算的复杂度（最差、平均、和最好性能），依据列表（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（d2<d1）。
③。重复上述分组和排序操作；直到取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】。key<r【j-1】。key，则把记录r【j】与r【j-1】交换位置，否则不进行交换。最后是r【2】。key与r【1】。key对比，关键字较小的记录就换到r【1】的位置上，到此第一趟结束。最小关键字的记录就象最轻的气泡冒到顶部一样换到了文件的前边。
（2）让j取n至3，重复上述的比较对换操作，最终r【2】之中存放的是剩余n-1个记录（r【1】除外）中关键字最小的记录。
（3）让j取n至i+1，经过一系列对联对比交换之后，r【i】之中是剩余若干记录中关键字最小的记录。
（4）让j取n至n-1，将r【n】。key与r【n-1】。key对比，把关键字较小的记录交换到r【n-1】之中。
算法时间复杂度：该算法的时间复杂度为O（n2）。但是，当原始关键字序列已有序时，只进行一趟比较就结束，此时时间复杂度为O（n）。
二）快速排序
快速排序由霍尔（Hoare）提出，它是一种对冒泡排序的改正。由于其排序速度快，故称快速排序（quicksort）。快速排序方法的实质是将一组关键字【K1，K2，…，Kn】进行分区交换排序。
算法思路
①以第一个关键字K1为控制字，将【K1，K2，…，Kn】分成两个子区，使左区所有关键字小于等于K1，右区所有关键字大于等于K1，最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。
②将右区首、尾指针（记录的下标号）保存入栈，对左区进行与第①步相类似的处理，又得到它的左子区和右子区，控制字居中。
③重复第①、②步，直到左区处理完毕。然后退栈对一个个右子区进行相类似的处理，直到栈空。
由以上三步可以看出：快速排序算法总框架是进行多趟的分区处理；而对某一特定子区，则应把它看成又是一个待排序的文件，控制字总是取子区中第一个记录的关键字。现在设计一个函数hoare，它仅对某一待排序文件进行左、右子区的划分，使控制字居中；再设计一个主体框架函数quicksort，在这里多次调用hoare函数以实现对整个文件的排序。
快速排序主体算法时间运算量约O（log2n），划分子区函数运算量约O（n），所以总的时间复杂度为O（nlog2n），它显然优于冒泡排序O（n2）。
三、选择排序
选择排序（SelectionSort）的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。
一）简单选择排序
简单选择排序（simpleselectionsort）也是直接选择排序。此方法在一些高级语言课程中做过介绍，是一种较为容易理解的方法。
算法思想：对于一组关键字{K1，K2，…，Kn}，首先从K1，K2，…，Kn中选择最小值，假如它是Kz，则将Kz与K1对换；然后从K2，K3，…，Kn中选择最小值Kz，再将Kz与K2对换。如此进行选择和调换n-2趟，第（n-1）趟，从Kn-1、Kn中选择最小值Kz将Kz与Kn-1对换，最后剩下的就是该序列中的最大值，一个由小到大的有序序列就这样形成。即：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
选择排序是不稳定的。
该算法的时间复杂度为O（n2）。并且排序是稳定的。
二）堆排序
定义：树形选择排序（锦标赛排序），1964年威洛姆斯（J。Willioms）提出了进一步改正的排序方法，即堆排序（heapsort）。
堆是n个元素的有限序列{K1，K2，…，Kn}，它当且仅当满足如下关系：
这是一个上小、底大的堆。若是一个上大、底小的堆，只需把“<=”改为“>=”即可。堆是一种数据元素之间的逻辑关系，常用向量做存储结构。对于满二叉树，当对它的结点由上而下，自左至右编号之后，编号为i的结点是编号为2i和2i+1结点的双亲。反过来讲，结点2i是结点i的左孩子，结点2i+1是结点i的右孩子。图9、7表示完全二叉树和它在向量中的存储状态。结点编号对应向量中的下标号。用堆的概念分析向量中的数据，它显然满足（上小、底大）堆的关系。不难看出满足堆的逻辑关系的一组数据，可画成二叉树的形状，并且它是一棵完全二叉树树形。因此，也可借助完全二叉树来描述堆的概念。若完全二叉树中任一非叶子结点的值小于等于（或大于等于）其左、右孩子结点的值，则从根结点开始按结点编号排列所得的结点序列就是一个堆。在图9、8中（a）、（c）是堆，（b）、（d）不是堆。
堆排序的算法思想：堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。
（1）用大根堆排序的基本思想
①。先将初始文件R【1、n】建成一个大根堆，此堆为初始的无序区
②。再将关键字最大的记录R【1】（即堆顶）和无序区的最后一个记录R【n】交换，由此得到新的无序区R【1、n-1】和有序区R【n】，且满足R【1、n-1】。keys≤R【n】。key
③。由于交换后新的根R【1】可能违反堆性质，故应将当前无序区R【1、n-1】调整为堆。然后再次将R【1、n-1】中关键字最大的记录R【1】和该区间的最后一个记录R【n-1】交换，由此得到新的无序区R【1、n-2】和有序区R【n-1、n】，且仍满足关系R【1、n-2】。keys≤R【n-1、n】。keys，同样要将R【1、n-2】调整为堆。
④。……
⑤。直到无序区只有一个元素为止。
（2）大根堆排序算法的基本操作：
①初始化操作：将R【1、n】构造为初始堆；
②每一趟排序的基本操作：将当前无序区的堆顶记录R【1】和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。
注意：
①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
堆排序中heap算法的时间复杂度与堆所对应的完全二叉树的树高度log2n相关。而heapsort中对heap的调用数量级为n，所以堆排序的整个时间复杂度为O（nlog2n）。并且堆排序是不稳定的。
四、归并排序
归并排序（mergesort）是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序有多路归并排序、两路归并排序，可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。
两路归并排序算法思路：
①。把n个记录看成n个长度为l的有序子表；
②。进行两两归并使记录关键字有序，得到n/2个长度为2的有序子表；
③。重复第②步直到所有记录归并成一个长度为n的有序表为止。
算法实现：此算法的实现不像图示那样简单，现分三步来讨论。首先从宏观上分析，首先让子表表长L=1进行处理；不断地使L=2*L，进行子表处理，直到L>=n为止，把这一过程写成一个主体框架函数mergesort。然后对于某确定的子表表长L，将n个记录分成若干组子表，两两归并，这里显然要循环若干次，把这一步写成一个函数mergepass，可由mergesort调用。最后再看每一组（一对）子表的归并，其原理是相同的，只是子表表长不同，换句话说，是子表的首记录号与尾记录号不同，把这个归并操作作为核心算法写成函数merge，由mergepass来调用。
（1）稳定性归并排序是一种稳定的排序。
（2）存储结构要求可用顺序存储结构。也易于在链表上实现。
（3）时间复杂度对长度为n的文件，需进行趟二路归并，每趟归并的时间为O（n），故其时间复杂度无论是在最好情况下还是在最坏情况下均是O（nlgn）。
（4）空间复杂度需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O（n），显然它不是就地排序。
注意：若用单链表做存储结构，很容易给出就地的归并排序。
【篇四：排序算法总结】
到目前为止，基本上常见的四大排序类型的算法已经列出来了，现在，我向从分组的概念上去总结一下各种排序算法。
首先列出四种类型常见的排序算法：
插入排序（插入排序，shell排序）交换排序（冒泡排序，快速排序）
选择排序（选择排序，堆排序）归并排序（归并排序）
对于插入排序：第一种简单的插入排序是单纯的插入排序算法，比较老实的一步一步地移动。分组思想体现在排序的整个过程，把列表分成两段：前面是有序的，后面是无序的。整个过程就是将无序元素转入有序之中。第二种插入排序是不老实的插入排序，移动时，是几步几步的跨。分组思想体现在，每一次进行n的跨越时，把相邻n长度的元素看作一组，然后对这n个组进行插入排序。
对于交换排序：第一种是简单的老实的交换排序，老老实实地交换。分组思想体现在整个过程，列表分成两部分，后面部分保存有序大元素，从前面部分不断的找较大元素，放入后面部分。与插入排序时，不要找放入位置，放入位置每次是固定的。第二种是复杂的不老实的交换，交换一般不发生在相邻元素之间，分组的思想体现在分组依赖于一个基准，使得列表可分成左右两部分，基准左部分小于基准，基准右部分大于基准，并且其中体现了划分的思想。
对于选择排序：第一种是简单的老实的选择排许，老老实实的选出较大元素，与特定位置的元素交换，分组体现在整个过程中，列表由两部分组成，有序部分和无序部分，无序边界朝有序发展。第二种排序是一种特别的有趣的排序算法，过程中，所有元素依然被分为有序和无序部分，但是在处理时，把元素分成了一个个家庭，家庭里有父亲，和左右孩子。这时的分组只是帮助完成有序到无序的转换。
对于归并排序：这是一种显而易见的含有分组思想的排序算法。归并当中，将列表层层分解，到最小单位，然后层层聚合，使得最顶上的一层有序，和其他算法不一样，整个过程，并没有明显的有序和无序的分组。励志名人名言http://www.qqzf.cn/
【篇五：各种排序算法总结】
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
1、冒泡法：O（n*n）
2、直接插入排序：O（n*n）
3、选择排序：O（n*n）
4、快速排序：平均时间复杂度log2（n）*n，所有内部排序方法中最高好的
5、归并排序：log2（n）*n
6、堆排序：log2（n）*n
7、希尔排序：算法的复杂度为n的1、2次幂
（1）冒泡排序
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
（2）选择排序
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列58529，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
（3）插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
（4）快速排序
快速排序有两个方向，左边的i下标一直往右走，当a【i】<=a【center_index】，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a【j】>a【center_index】。如果i和j都走不动了，i<=j，交换a【i】和a【j】，重复上面的过程，直到i>j。交换a【j】和a【center_index】，完成一趟快速排序。在中枢元素和a【j】交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为53343891011，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a【j】交换的时刻。
（5）归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。
（6）基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
（7）希尔排序（shell）
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o（n^2）好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
（8）堆排序
我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1，n/2-2，……1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
【篇六：内排序算法总结】
二分法插入排序：
算法思想简单描述：
在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们
中间的那个元素比，如果小，则对前半再进行折半，否则对后半
进行折半，直到left>right，然后再把第i个元素前与目标位置之间
的所有元素后移，再把第i个元素放在目标位置上。
二分插入排序是稳定的，平均时间O（n2）
本文地址：排序算法总结http://www.qqzf.cn/lizhi18275/