【考研】C语言排序和查找算法总结

更新历史：

声明：本文部分图片来源于网络，如若侵权，请联系作者删除。

  在程序设计中，经常使用数组来保存大量的数据，当对数据进行增加、删除、更新、查找操作时经常会使用到排序和查找算法对数组中的元素进行排序和查找。排序 (sorting) 是把一系列无序的数据按照特定的顺序（升序或者降序）重新排列为有序序列的过程，而查找 (searching) 则是在一种特定的数据结构中搜索一个特定元素的处理过程。本文将介绍并实现众多的排序和查找算法并给予总结，比较各种排序和查找算法的时空效率。

  一个排序算法可以使得序列中的元素具有一定的有序结构，比如序列中有n个记录，通过排序希望得到一个升序（ascending order）或者降序（descending order）序列，这种有序序列有利于数据的增删改查操作的进行。在本文中将结合学生成绩管理系统讨论一些内部排序算法，内部排序是一种待排序列完全存放在内存中所进行的排序过程，相应的外部排序算法超出了讨论的范围。根据排序的思想，可将各类内部排序算法分为以下几类：

交换排序 包括 冒泡排序（气泡排序）和 快速排序（快排）；

选择排序 包括 简单选择排序 和 堆排序 ；

插入排序 包括 直接插入排序 、折半插入排序 和 希尔排序；

归并排序 常用的有 二路归并排序；

基数排序 不基于关键字比较的算法。

  查找算法是基于用户所关心的关键字或查找条件而对序列中元素的查找，查找的结果是有可能查找到，也有可能没有找到，这是取决于查找条件的。同时，查找算法不仅仅在一个线性结构（如数组等）中进行查找，也可能在一定的非线性结构(如树、图)中查找，它们的实现方式不同，但原理是类似的，本文将主要叙述线性结构的查找，特别是基于数组等结构的查找。一定程度上，如果序列是有序的，那么查找序列中的元素时是容易的，这也是先叙述排序算法的原因之一。根据查找的思想，可将各类查找算法分为以下几类：

顺序查找

折半查找

分块查找

  算法效率的度量一般是通过时间复杂度和空间复杂度来描述的。算法的效率是和算法处理数据的规模（记为n）有关的，因此算法的运行时间和占用内存是和n有关的，是n的函数，通常用O(f(n))来表示，其中f(n)是实际的运行时间。用O(f(n))来表示近似的运行时间的意义在于O(f(n))表示了实际运行时间f(n)的上界，这个上界表示运行该算法所需最多的时间。比如看下面求解前n项和的算法主体：

  快速排序，简称快排，是冒泡排序的优化。冒泡排序每一趟都会比较相邻的两个元素，实际上有很多次都是冗余比较，而对于快速排序而言，快速排序是基于分治法的，快速排序不断地将所排序列分成两部分，每一部分都递归地求解。具体来说，快排有以下几个步骤：

选定一个基准元素（pivot），用该基准元素将序列二划分：小于等于pivot的一部分 + pivot +大于pivot的一部分，此时pivot在最终的排序位置；

然后递归地对小于等于pivot的一部分、大于pivot的一部分进行求解，终止条件为一个元素自然有序（即不断划分时，某一部分只有1个元素，此时该元素即在最终的位置）。

  算法的核心思想为如下图所示（一次划分），在这里pivot取第一个元素：

  算法的C语言实现有：

  希尔排序也是一种插入排序，其基于直接插入排序算法改进而来，又称为缩小增量排序。算法的思想是清晰的，下面有图示给出：   希尔排序关键在于增量d的选择，一般而言初始时增量d会选择为数据量(n)的一半，然后逐渐减半，直至d等于1。之所以希尔排序的效率较高是因为当增量d逐渐减小时，数据量已经基本有序，对于大致有序的数据而言直接插入排序可以达到O(n)的时间复杂度，希尔排序正是利用了这一点。

  插入排序的思想都是简单的，在生活中的扑克牌游戏的整理牌的过程就由此而来，对于三种插入排序而言，他们的时空效率有：

  值得注意的是，希尔排序的时间复杂度和增量d的选择有关，不同的选择时间复杂度不一样，由于这涉及到数学上未解决的问题，所以在一定情况下其时间复杂度在O(n1.3)和O(n2)之间。

  归并排序是将序列划分成若干个元素数相同的子序列后，依次将多个有序的子序列合并为一个子序列的过程，在这里将介绍一下二路归并排序，也即将依次将两个有序子序列合并为一个子序列的过程，其基本思想如图所示：

  归并排序的精髓在于子序列归并的过程，由于两个子序列都有序，因此可以通过双指针法访问两个子序列来合并成一个子序列。其C语言实现有：

  算法是简单的，但是可能任意一个程序设计人员都知道这不是一个高效的算法，现在用平均查找长度来衡量一下：   对于上面的序列，假设任意一个元素被查找的概率相同，那么其查找成功和查找失败的平均查找长度为：   查找失败的平均查找长度要比较n个元素还有最后的一个空元素（即这里认为查找到空元素时才认为查找失败）。可以看出查找成功和查找失败的平均查找长度都是n的线性倍数的。

  正如前面s所提及的那样，顺序查找效率不高，因为一遍都需要遍历序列中的一半的元素，那么下面介绍的折半查找算法是一种高效率的算法，不要折半查找算法要求序列是有序的。其基本思想是：针对有序序列，先用待查找元素和序列的中间元素进行比较，比较完之后判断待查找元素可能在原序列上/下半部分，然后在上/下半部分极继续执行上面的操作，直至找到元素或未找到元素。   下面是C语言实现：

  折半查找的查找成功和查找失败的平均查找长度是不容易求解的，一般需要写出折半查找的判定树之后进行求解，在此不再赘述。

  分块查找结合了顺序查找和折半查找的优点，既有动态结构，又适于快速查找。分块查找的基本思想是：将查找表分为若干个子块。块内元素是无序的，而块间元素是有序的其中会建立索引，取每块的最大元素建立索引表。分块查找的过程分为两步：

在索引表中确定待查记录所在的块，可以通过顺序查找和折半查找索引表；

在块内顺序查找。

  下面分析分块查找的效率，对于长度为n的查找表，假设均分成b块，每块有s个元素，在等概率的情况下，若在块内和索引表总均采用顺序查找，则平均查找长度为（查找成功）：

  顺序查找、折半查找和分块查找方式都是常用的查找方式，值得注意的是，在一些存储连续的序列中（如链表）只能采取顺序查找的方式，而对于数组等存储方式是可以采取折半查找的方法的。

  当然还有一些其他的查找算法，如B-树查找、散列查找等，这些查找算法都是建立了一定的数据结构从而来查找的，因此在讨论算法是是不可以忽视采用的数据结构的。

周建钦. 超快速排序算法[J]. 计算机工程与应用, 2006. ↩︎