内容发布更新时间 : 2024/11/16 13:03:05星期一 下面是文章的全部内容请认真阅读。

龙源期刊网 http://www.qikan.com.cn

常用C语言排序算法解析

作者：毛广敏

来源：《软件导刊》2012年第11期

摘 要：排序是计算机科学中最重要的研究问题之一，也是学习C语言程序设计过程中重点研究问题之一。主要介绍了顺序比较法、选择排序法、冒泡排序法、改进的冒泡排序法和直接插入排序法，并从排序算法的思想、模拟排序执行过程、实现排序的算法代码及算法性能分析4个方面进行了详细的解析，可以帮助C语言初学者轻松理解几种常用的排序算法。 关键词：C语言；排序；算法思想；数组

中图分类号：TP301.6 文献标识码：A 文章编号：16727800（2012）011005103 ________________________________________

作者简介：毛广敏（1978-），女，宿迁经贸高等职业技术学校讲师，研究方向为计算机软件。0 引言

在数据处理中，数据排序是相当重要的，它可以使数据更有条理，方便数据的处理。排序是程序设计的常见问题，解决排序问题也有多种算法，常用的算法有顺序比较排序法、选择排序法、冒泡排序法、直接插入排序法、快速排序和希尔排序法等排序算法。在学习C语言程序设计过程中排序算法也是重点研究问题之一，本文主要用C语言来描述几种常见的排序算法，以及分析实现算法的基本思路、模拟相应算法实现排序的过程及算法性能分析。文中所涉及的排序均为升序排序。 1 顺序比较排序法 1.1 算法思想

假设数组有n个元素，从第一个元素开始为第一趟，第一个元素和第二个元素开始到第n个元素按顺序作比较，如果第一个元素大于某个元素则第一个元素和该元素进行交换，第一个元素和其后的n1个元素一一进行两两比较结束后将是所有元素中的最小值。接下来第二趟从第二个元素开始逐一和其后的n2个元素两两比较，在进行n2次比较后第二个元素将是剩下n1个元素中的最小值。依次类推一直到第n1趟最后两个元素进行比较并得到第n1个元素是剩下的两个元素中的较小值。 1.2 模拟排序执行过程

假设一个整型数组有5个元素，分别为23、12、5、16、10，排序执行过程如下所示：

龙源期刊网 http://www.qikan.com.cn

第一趟： 23 12 5 16 10 （第一趟比较前元素） 第一次：122351610（由于23>12 两元素交换） 第二次：523121610（由于12>5 两元素交换） 第三次：523121610（由于5 第四次：523121610（由于5

第二趟：523121610（第二趟比较前元素） 第一次：512231610（由于23>12 两元素交换） 第二次：512231610（由于12

第三次：510231612（由于12>10 两元素交换） 第三趟：510231612（第三趟比较前元素） 第一次：510162312（由于23>16 两元素交换） 第二次：510122316（由于16>12 两元素交换） 第四趟：510122316（第四趟比较前元素） 第一次：510121623（由于23>16 两元素交换） 1.3 实现顺序比较排序法核心代码 for（i=0；i for（j=i+1；j

if（a[i]>a[j]） //如果当前趟的第一个元素大于当前元素，则进行交换 {t=a[i]； a[i]=a[j]； a[j]=t；}

龙源期刊网 http://www.qikan.com.cn

1.4 算法性能分析

有n个元素参加排序要进行n1趟比较，第i趟要进行ni次两两比较。时间复杂度为O（n2）。顺序比较排序算法稳定，比较次数已知，但是该算法速度慢。 2 冒泡排序法 2.1 算法思想

假设数组有n个元素，第一趟从第一个元素开始依次比较两个相邻元素的值，如果前一个元素的值大于后一个元素的值则两个相邻元素进行交换，第一趟比较n1次，经过一趟排序n个元素中的最大值存放到最后一个数组元素中。第二趟从第一个元素开始到第n1个元素相邻两个元素作比较，如果前一个数大于后一个数则两个相邻的元素进行交换，经过n2次比较，这一趟中最大值放在第n1个数组元素的位置。依次类推一直到第n1趟第一个元素和第二个元素两个元素进行比较，两个元素中的较大值放在第二个数组元素的位置，较小值放在第一个数组元素的位置。

2.2 模拟排序执行过程

假设一个整型数组有5个元素，分别为23、12、5、16、10，用变量k保存最小值的下标，排序执行过程如下所示：

第一趟： 23 12 5 16 10 （第一趟比较前元素）

第一次： 12 23 5 16 10 （由于23>12 两元素交换位置） 第二次： 12 5 23 16 10 （由于23>5 两元素交换位置） 第三次： 12 5 16 23 10 （由于23>16 两元素交换位置） 第四次： 12 5 16 10 23 （由于23>10 两元素交换位置） 第二趟： 12 5 16 10 23 （第二趟比较前元素） 第一次： 5 12 16 10 23 （由于12>5 两元素交换位置） 第二次： 5 12 16 10 23 （由于12

第三次： 5 12 10 16 23 （由于16>10 两元素交换位置） 第三趟： 5 12 10 16 23 （第三趟比较前元素）