C程序设计中关于排序的探讨.pdfVIP

ISSN1009-3044 E-mail: xsjl@ ComputerKnowledgeandTechnology电脑知识与技术 第8卷第31期 (2012年11月) ComputerKnowledgeandTechnology 电脑知识与技术 Vol.8,No.31,November 2012. Tel:+86-551-5690963 5690964 C++程序设计中关于排序的探讨 朱洪莉 （遵义职业技术学院 计科系，贵州 遵义 563000） 摘要：排序就是在计算机中对不规则数据进行升序或降序排列实现的方法；排序算法有冒泡排序、选择排序和插入排序 等，各种算法的实现其复杂度都不一样，复杂度的大小体现了算法的优劣。 关键词：冒泡排序；选择排序；插入排序 中图分类号：TP311 文献标识码：A 文章编号：1009-3044(2012)31-7504-04 排序（Sorting）是C++程序设计中基本并且常用的算法，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关 键字有序的序列。本文将讨论三种排序算法的实现，并对三种排序算法进行比较分析。 1排序的分类 [1] 1.1按是否涉及数据的内、外存交换分为 ： 1）内部排序: 内部排序(简称内排序)，是带排序纪录存放在计算机内存中进行的排序过程。 2）外部排序:外部排序(简称外排序)，是带排序纪录的数量很大，以至于内存一次不能容纳全部纪录，在排序过程中，只有部分 数被调入内存，并借助内存调整数在外存中的存放顺序的排序方法。 1.2按策略划分内部排序可分为 1）插入排序，包括：直接插入排序，其它插入排序，希尔排序； 2）快速排序，包括：冒泡排序，快速排序； 3）选择排序，包括：简单选择排序，树形选择排序，堆排序； 4）归并排序； 5）基数排序，包括：多关键字的排序，链式基数排序。 2排序的实现 由于排序有很多种方法，本文主要讨论内部排序的几种实现。 2.1冒泡排序 算法实现思想：将被排序的数组R[1...n]垂直排列，即将元素R[1]到R[n]排列垂直如气泡状，约定数据小的为轻气泡，大的为重气 泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上”飘浮[2]”。如此反复进 行，直到最后任何两个气泡都是轻者在上，重者在下为止（图1）。 图1 冒泡排序实例 程序设计如下: #includeiostream.h 收稿日期：2012-10-14 作者简介：朱洪莉（1976-），女，贵州遵义人，讲师，本科，研究方向为计算机语言的教学与研究。 7504 软件设计开发 本栏目责任编辑：谢媛媛 第8卷第31期 (2012年11月) ComputerKnowledgeandTechnology电脑知识与技术 voidBubbleSort(int*p，intCount) {intitemp； for(inti=1；iCount；i++) {for(intj=0；jCount-i；j++) { if(p[j]p[j+1]) {itemp=p[j]；p[j]=p[j+1]；p[j+1]=itemp； } } } } voidmain() { intdata[]={49，38，65，97，76，13，27，49}； cout“排序前的数据序列：”； for(inti=0；i=7；i++) coutdata[i]“”； BubbleSor