数据结构与算法总结

姓名：** 学号：** 班级：12计本（2）班

这个学期在老师的带领下我们学习了数据结构与算法这门课程。在本次数据结构与算法的学习中最令我深刻的是关于几种排序算法的学习，所以在这里我想对我本学期所学习的这几种排序算法做一个比较详细的总结。

首先我们要对排序有一个了解，排序是将一个数据元素或记录的任意序列，重新排列成一个按关键字有序的序列。排序按照不同的分类方式可以划分为不同的种类。按照稳定性划分，可以划分为稳定排序和不稳定排序。

稳定排序在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生改变，则称这种排序方法是不稳定的。即所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，则说这种排序算法是稳定的，反之，就是不稳定的。

稳定的排序算法如下表所示：   

   

    不稳定的排序算法如下表所示： 

一、插入排序   

    插入排序的基本思想是每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。

   直接插入排序具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序

2. 取出下一个元素，在已经排序的元素序列中从后向前扫描

　　3. 如果该元素（已排序）大于新元素，将该元素移到下一位置

　　4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

　　5. 将新元素插入到下一位置。

二、希尔排序

希尔(Shell)排序的基本思想是：先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取得第二个增量d2＜d1重复上述的分组和排序，直至所取的增量di=1，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

  一般取d1=n/2，di+1=di/2。如果结果为偶数，则加1，保证di为奇数。

三、冒泡排序

冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序

四、归并排序

  归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时，把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们两两合并。直到得到长度为n的有序表，排序结束。

  归并操作的工作原理如下：

　　1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

　　2、设定两个指针，最初位置分别为两个已经排序序列的起始位置

　　3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

　　4、重复步骤3直到某一指针达到序列尾

　　5、将另一序列剩下的所有元素直接复制到合并序列尾。

五、选择排序

  选择排序的基本思想是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。选择排序中主要使用直接选择排序和堆排序。

  直接选择排序的过程是：首先在所有记录中选出序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换......依次类推，直到所有记录排完为止。

6、快速排序

  快速排序采用了一种分治的策略，通常称其为分治法，其基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

  快速排序的具体过程如下：

  第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第1组各记录的排序码都小于等于该排序码，第2组各记录的排序码都大于该排序码，并把该记录排在这两组中间。

  第二步，采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止 

七、堆排序

   堆的定义：n个关键字序列Kl，K2，…，Kn称为(Heap)，当且仅当该序列满足如下性质(简称为堆性质)：

(1) ki≤K2i 且 ki≤K2i+1或

(2)Ki≥K2i 且 ki≥K2i+1(1≤i≤ n)

  若将此序列所存储的向量R[1..n]看作是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

  根结点(堆顶)的关键字是堆里所有结点关键字中最小者，称为小根堆；根结点的关键字是堆里所有结点关键字中最大者，称为大根堆。

  用大根堆排序的基本思想如下：

　　1、先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区

　　2、再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key

　　3、由于交换后新的根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]调整为堆。直到无序区只有一个元素为止。

八、二叉树排序

  二叉排序树（Binary Sort Tree）又称二叉查找树。它或者是一棵空树；或者是具有下列性质的二叉树：

    （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

    （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

    （3）左、右子树也分别为二叉排序树；

  我的理解是：二叉树排序，即先建一个二叉排序树，然后中序遍历，即得到一个从小到大的排序结果。

九，拓扑排序

拓扑排序是对有向无环图的一种排序，表示了定点按边的方向出现的先后顺序。如果有还就无法表示两个顶点的先后顺序。

拓扑排序的基本算法：

输入AOV网络，令定点数为N。

（1）在AOV网络中选一个没有直接前驱的顶点，并输出。

（2）从图中删除这个顶点，同时删去所有他发出的有向边。

（3）重复以上步骤，知道所有的顶点都已经输出，则拓扑序列形成。

二．学习感悟

以上就是我对于本学期所学的各种排序算法的总结，在学习的过程中遇到过很多的问题，包括是对概念认识的不清晰，还有运用不灵活等。在学习这门课程之前，我们学习过c语言，但由于我对c语言的掌握并不够扎实，导致我对这门课程没有什么信心。但在学完了这门课程后， 我对数据结构与算法有一定的了解，也加深了对C语言的理解，我感觉所以的致死框架都建立在基础概念之上。但是对于这门课程的学习，绝不是那种死记硬背，只有结合思考与运用才能够加以理解和掌握。

　　我们都知道，了解了在编程过程中采用好的算法可以降低程序的时间和空间复杂度。 对操作系统、编译原理、数据库管理系统、软件工程、人工智能等的学习都是很有益的，而且所有的计算机系统软件和应用软件都要用到各种类型的数据结构。再次温习这本书，增加了对数据结构与算法的理解，对数据结构的构建也有更深层次的体会。算法的每一次改进和提高，都凝聚着人类的智慧和辛勤劳动，每一次创新都给人类带来了巨大的进步。刚开始学习的时候就感觉这学期课好多，而且好难，每天都感觉很累很累。到学期中的时候，都有点鼓不起来干劲了，每天就是“快点下课快点下课”。重新调整好状态，发现落下不少，又努力的弥补。不管开心还是郁闷，这门课就要结束了，学会了很多，没学会的也多。胡老师是一个很细致的人，书上的每个知识点几乎都讲到了，也经常督促我们做课后习题，因为到了大学，大家都喜欢跳跃式前进，却经常顾此失彼，我更加倾向于一步一步的学习。在这里感谢胡老师一个学期的教导，也希望我能在接下来的考试中获得好成绩。

 

第二篇：数据结构排序方法总结

数据结构的内部排序

数据结构中的内部各种排序，大体上分为五大类，在我们对每个算法进行分析前，最重要的是搞清楚它的基本思想。

    ★插入类排序；

    ★交换类排序；

    ★选择类排序；

    ★归并排序；                                                           

    ★分配类排序；

一、插入类排序

基本思想是：在一个已经排好序的序列中，每一步都将下一个待排序的记录插入到已排好序的记录中，直到所有待排序的记录全部插入为止。

插入类排序又分为三大类：

    ●直接插入排序；

    ●折半插入排序；

    ●希尔排序；

下面我们以直接插入排序与希尔排序为例。

(1)     直接插入排序

算法思想：将第i个记录（i一般是从2开始）插入到前面i-1个已经排好序的记录中。

具体过程：将第i个记录的关键字K顺次与其前面记录的关键字进行比较。将所有关键字大于K的记录依次向后移动一个位置，直到遇到小于或等于K的关键字，就把K插入到其后面即可。

下面我们以一个例子为例，讲解它的具体实现过程。

直接插入排序举例

以12  2  16  30  8  28  4  10  20  6  18序列为例

第一趟：2  12  16 30  8  28  4  10  20  6  18

第二趟：2  8  12  16  30 28  4  10  20  6  18

第三趟：2  8  12  16  28  30 4  10  20  6  18

第四趟：2  4  8  12  16  28  30  10  20  6  18

第五趟：2  4  8  10  12  16  28  30  20  6  18

第六趟：2  4  8  10  12  16  20  28  30  6  18

第七趟：2  4  6  8  10  12  16  20  28  30  18

第八趟：2  4  6  8  10  12  16  18  20  28  30

功能实现：

输入：数组名称（也就是数组首地址）、数组中元素个数

================================================

算法思想简单描述：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

直接插入排序是稳定的。算法时间复杂度

=====================================================

void insert_sort(int *x, int n)

{

int i, j, t;

for (i=1; i<n; i++) /*要选择的次数：1~n-1共n-1次*/

{

    /*

     暂存下标为i的数。注意：下标从1开始，原因就是开始时第一个数即下标为0的数，前面没有任何数，单单一个，认为它是排好顺序的。

    */

    t=*(x+i);

    for (j=i-1; j>=0 && t<*(x+j); j--) /*注意：j=i-1，j--，这里就是下标为i的数，在它前面有序列中找插入位置。*/

    {

     *(x+j+1) = *(x+j); /*如果满足条件就往后挪。最坏的情况就是t比下标为0的数都小，它要放在最前面，j==-1，退出循环*/

    }

    *(x+j+1) = t; /*找到下标为i的数的放置位置*/

}

}

(2)     希尔排序

算法思想：将待排序记录序列分割成若干个较稀疏的子序列，分别进行直接插入排序。

具体过程：①首先选定记录间的距离d，将待排序的记录序列中所有间隔为d的记录分为一组，进行组内直接插入排序。

          ②继续选定记录间的距离d1（d1<d），将待排序的记录序列中所有间隔为d1的记录分为一组，进行组内直接插入排序。

          ③重复步骤②，直到记录间的距离为1，完成整个排序过程。

希尔排序举例

12  2  16  30  8  28  4  10  20  6  18

第一趟：d=5

12  2  10  20  6  18  4  16  30  8   28

第二趟：d=3

4   2  10   8    6  18 12 16  30  20  28

第三趟：d=1

2  4    6    8   10 12 16 18  20  28  30

功能实现：

输入：数组名称（也就是数组首地址）、数组中元素个数

====================================================

算法思想简单描述：在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。

下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量，以后每次减半，直到增量为1。

希尔排序是不稳定的。

=====================================================

void shell_sort(int *x, int n)

{

int h, j, k, t;

for (h=n/2; h>0; h=h/2) /*控制增量*/

{

    for (j=h; j<n; j++) /*这个实际上就是上面的直接插入排序*/

    {

     t = *(x+j);

     for (k=j-h; (k>=0 && t<*(x+k)); k-=h)

     {

      *(x+k+h) = *(x+k);

     }

     *(x+k+h) = t;

    }

}

}

二、交换类排序

算法思想：通过交换逆序元素进行排序的方法。

交换类排序又分为两大类：

    ●冒泡排序；

    ●快速排序；

下面我们以快速排序为例

(1)     冒泡排序

算法思想：将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

具体过程：①初始：R[1..n]为无序区。

②第一趟扫描：从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(R[n]，R[n-1])，(R[n- 1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1].key<R[j].key，则交换 R[j+1]和R[j]的内容。第一趟扫描完毕时，"最轻"的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R[1]上。
          ③第二趟扫描：扫描R[2..n]。扫描完毕时，"次轻"的气泡飘浮到R[2]的位置上……最后，经过n-1 趟扫描可得到有序区R[1..n]
注意：第i趟扫描时，R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置R[i]上，结果是R[1..i]变为新的有序区。

功能实现：

输入：数组名称（也就是数组首地址）、数组中元素个数

================================================

算法思想简单描述：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

下面是一种改进的冒泡算法，它记录了每一遍扫描后最后下沉数的位置k，这样可以减少外层循环扫描的次数。

冒泡排序是稳定的。算法时间复杂度

=====================================================

void bubble_sort(int *x, int n)

{

int j, k, h, t;

for (h=n-1; h>0; h=k) /*循环到没有比较范围*/

{

    for (j=0, k=0; j<h; j++) /*每次预置k=0，循环扫描后更新k*/

    {

     if (*(x+j) > *(x+j+1)) /*大的放在后面，小的放到前面*/

     {

      t = *(x+j);

      *(x+j) = *(x+j+1);

      *(x+j+1) = t; /*完成交换*/

      k = j; /*保存最后下沉的位置。这样k后面的都是排序排好了的。*/

     }

    }

}

}

(2)     快速排序

算法思想：从待排序记录中选取一个记录为枢轴，其关键字为K，然后将其余关键字小于K的记录移到前面，而将关键字大于K的记录移到后面，结果将待排序记录序列分成两个子表，最后将关键字为K的记录插到其分界线的位置处。

具体过程：先对序列进行第一次划分，进行一趟快速排序。然后分成两个子序列后，继续对其进行划分，直到最后所有的表长都不超过1为止。这样就形成了一个有序的序列。

快速排序举例 12  2  16  30  8  28  4  10  20  6  18

第一趟：6  2  10  4  8  12  28  30  20  16  18

第二趟：4  2  6  10  8  12  28  30  20  16  18

第三趟：2  4  6  10  8  12  28  30  20  16  18

第四趟：2  4  6  8  10  12  28  30  20  16  18

第五趟：2  4  6  8  10  12  18  16  20  28  30

第六趟：2  4  6  8  10  12  16  18  20  28  30

功能实现：

输入：数组名称（也就是数组首地址）、数组中起止元素的下标

====================================================

算法思想简单描述：快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。它是由C.A.R.Hoare于1962年提出的。

显然快速排序可以用递归实现，当然也可以用栈化解递归实现。下面的函数是用递归实现的，有兴趣的朋友可以改成非递归的。

快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n2)

void quick_sort(int *x, int low, int high)

{

int i, j, t;

if (low < high) /*要排序的元素起止下标，保证小的放在左边，大的放在右边。这里以下标为low的元素为基准点*/

{

    i = low;

    j = high;

    t = *(x+low); /*暂存基准点的数*/

    while (i<j) /*循环扫描*/

    {

     while (i<j && *(x+j)>t) /*在右边的只要比基准点大仍放在右边*/

     {

      j--; /*前移一个位置*/

     }

     if (i<j)

     {

      *(x+i) = *(x+j); /*上面的循环退出：即出现比基准点小的数，替换基准点的数*/

      i++; /*后移一个位置，并以此为基准点*/

     }

     while (i<j && *(x+i)<=t) /*在左边的只要小于等于基准点仍放在左边*/

     {

      i++; /*后移一个位置*/

     }

     if (i<j)

     {

      *(x+j) = *(x+i); /*上面的循环退出：即出现比基准点大的数，放到右边*/

      j--; /*前移一个位置*/

     }

    }

    *(x+i) = t; /*一遍扫描完后，放到适当位置*/

    quick_sort(x,low,i-1);    /*对基准点左边的数再执行快速排序*/

    quick_sort(x,i+1,high);    /*对基准点右边的数再执行快速排序*/

}

}

三、选择类排序

算法思想：每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列中第i个记录。

选择类排序又分为三大类：

    ●简单选择排序；

    ●树型选择排序；

    ●堆排序；

下面我们以简单选择排序和堆排序为例

(1)     简单选择排序

算法思想：从第i个记录开始，通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的和第i个记录进行交换。

具体过程：先从第一个记录开始，通过n-1次关键字比较。从n个记录中选取最小的关键字与第一个进行交换。然后从第二个记录开始，依照上面步骤继续寻找，交换。进行n-1次简单排序后，就排出了完整的序列。

简单选择排序举例12  2  16  30  8  28  4  10  20  6  18

第一趟：2  12  16 30  8  28   4  10  20  6  18

第二趟：2   4   16 30  8  28  12 10  20  6  18

第三趟：2   4    6  30  8  28  12 10  20 16 18

第四趟：2   4    6   8  30 28  12 10  20 16 18

第五趟：2   4    6   8  10 28  12 30  20 16 18

第六趟：2   4    6   8  10 12  28 30  20 16 18

第七趟：2   4    6   8  10 12  16 30  20 28 18

第八趟：2   4    6   8  10 12  16 18  20 28 30

功能实现：

功能：选择排序

输入：数组名称（也就是数组首地址）、数组中元素个数

================================================

算法思想简单描述：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

选择排序是不稳定的。算法复杂度

=====================================================

void select_sort(int *x, int n)

{

int i, j, min, t;

for (i=0; i<n-1; i++) /*要选择的次数：0~n-2共n-1次*/

{

    min = i; /*假设当前下标为i的数最小，比较后再调整*/

    for (j=i+1; j<n; j++)/*循环找出最小的数的下标是哪个*/

    {

     if (*(x+j) < *(x+min))

     {  

      min = j; /*如果后面的数比前面的小，则记下它的下标*/

     }

    } 

    if (min != i) /*如果min在循环中改变了，就需要交换数据*/

    {

     t = *(x+i);

     *(x+i) = *(x+min);

     *(x+min) = t;

    }

}

}

(2)     堆排序

算法思想：把待排序记录的关键字存放在一个数组中，将这个数组看成是一棵完全二叉树的顺序表示，每个结点表示一个记录，第一个记录作为二叉树的根，以下各记录依次逐层从左到右顺序排列。

具体过程：对于堆排序，我们先要建初堆，然后再初始大根堆，把栈顶元素与堆尾元素交换，最后对其前面的几个元素重新进行堆调整。

堆排序举例

建立初始堆                            2出列，调整堆

     

筛选                                 4出列，调整堆 

     

筛选                                  6出列，调整堆

        

筛选                                  8出列，调整堆 

        

筛选                                  10出列,调整堆

            

筛选                                 12出列，调整堆

              

筛选                                 16出列，调整堆

             

筛选                                18出列，调整堆

               

筛选                               28出列，调整堆

               

30出列，排序完成。

功能实现：

输入：数组名称（也就是数组首地址）、数组中元素个数

====================================================

算法思想简单描述：堆排序是一种树形选择排序，是对直接选择排序的有效改进。堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。

从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

堆排序是不稳定的。算法时间复杂度O(nlog2n)。

功能：渗透建堆

输入：数组名称（也就是数组首地址）、参与建堆元素的个数、从第几个元素开始

void sift(int *x, int n, int s)

{

int t, k, j;

t = *(x+s); /*暂存开始元素*/

k = s;    /*开始元素下标*/

j = 2*k + 1; /*右子树元素下标*/

while (j<n)

{

    if (j<n-1 && *(x+j) < *(x+j+1))/*判断是否满足堆的条件：满足就继续下一轮比较，否则调整。*/

    {

     j++;

    }

    if (t<*(x+j)) /*调整*/

    {

     *(x+k) = *(x+j);

     k = j; /*调整后，开始元素也随之调整*/

     j = 2*k + 1;

    }

    else /*没有需要调整了，已经是个堆了，退出循环。*/

    {

     break;

    }

}

*(x+k) = t; /*开始元素放到它正确位置*/

}

功能：堆排序

输入：数组名称（也就是数组首地址）、数组中元素个数

*/

void heap_sort(int *x, int n)

{

int i, k, t;

int *p;

for (i=n/2-1; i>=0; i--)

{

    sift(x,n,i); /*初始建堆*/

}

for (k=n-1; k>=1; k--)

{

    t = *(x+0); /*堆顶放到最后*/

    *(x+0) = *(x+k);

    *(x+k) = t;

    sift(x,k,0); /*剩下的数再建堆*/

}

}

四、归并排序

算法思想：将n个记录堪称n个有序的子序列，每一个子序列的长度为1，然后两两归并，得到n/2个长度为2的有序子序列。

(12)  (2)  (16)  ( 30)  (8)  (28)  (4)  (10)  (20)  (6)  (18)

第一趟

 (2  12)  (16  30)  (8  28)  (4  10)  (6  20)  (18)

第二趟

           (2  12  16  30)  (4  8  10  28)  (6  18  20)

第三趟

           (2  4  8  10  12  16  28  30)  (6  18  20)

第四趟

            2  4  6  8  10  12  16  18  20  28  30

五、分配类排序

算法思想：利用分配和收集两种基本操作进行排序。

下面我们以基数排序为例

            12  2  16  30  8  28  4  10  20  6  18

第一趟:

            30  10  20  12  2  4  16  6  8  28  18

第二趟:

           2  4  6  8  10  12  16  18  20  28  30

各种排序比较

1.稳定性比较

插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的

选择排序、希尔排序、快速排序、堆排序是不稳定的

2.时间复杂性比较

插入排序、冒泡排序、选择排序的时间复杂性为O(n2)

其它非线形排序的时间复杂性为O(nlog2n)

线形排序的时间复杂性为O(n);

3.辅助空间的比较

线形排序、二路归并排序的辅助空间为O(n),其它排序的辅助空间为O(1);

4.其它比较

插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。

反而在这种情况下，快速排序反而慢了。

当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。

若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。

当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。

当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下。

宜用归并排序。

当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。