排序依据所涉及的存储器不同,分为两大类:一类是内部排序,指的是待排序记录存放在计算机存储器中进行的排序过程;另一类则是外部排序,指的是待排序记录数量很大,以至内存不能容纳全部记录,在排序过程中尚需对外存进行访问的排序过程。本文将主要讨论内部排序中的直接插入排序、冒泡排序和简单选择排序三种排序,并简要的分析一下快速排序的稳定性。

    与其它算法相比,排序也是数据结构中的一种算法,只不过它所实现的功能比较具体,即实现无序系列的排序。同样,它也涉及到一种算法的设计思想、参数的引用及时间复杂度等相关因素;与其它算法有所不同,排序算法涉及到了稳定性与不稳定性的概念,即关键字相同,排序后它们的顺序不变的排序方法称为稳定排序,顺序有可能发生改变的排序方法称为不稳定排序。例如,数据结构中内部排序算法的分析,序列中有两个2,标记为。用一种排序方法进行排序,排序后,若始终在的前面,则称稳定的排序,若有可能在的后面,则称不稳定的排序。

    排序按排序过程中依据的不同原则对内部排序进行分类,大致可分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。其实现过程主要进行比较和移位两种操作,即比较关键字的大小,将记录从一个位置移动到另一个位置,最后得到一个有序序列。学习排序的过程,其关键在于理解排序的思想,分析各种排序的特点,从分类到实现,利用流程来实现过程。

    1 几种排序算法的实现过程

    内部排序按其算法设计思想的不同,可分为直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序和基数排序,其中插入的排序有直接插入排序、折半插入排序和希尔排序三种,交换的排序有冒泡排序和快速排序,选择的排序有简单选择排序和堆排序。

    从排序的稳定性来看,稳定的排序有:直接插入排序、折半插入排序、冒泡排序和归并排序,不稳定的排序有:希尔排序、快速排序、简单选择排序和堆排序;从排序算法的时间复杂度来看,直接插入排序、折半插入排序、冒泡排序、简单选择排序的时间复杂度为,希尔排序的时间复杂度为,快速排序、堆排序和归并排序的时间复杂度为稳定性。

    本文将从排序算法的设计思想、流程图、程序设计、稳定性和时间复杂度等五个方面具体分析,主要介绍直接插入排序、冒泡排序、快速排序、简单选择排序和堆排序。此外,在程序的设计过程中,将引用一个数组啊a[n]来保存排序序列,排序序列中的所有元素均为整型元素,且均按把序列排成升序的过程来实现。

    1.1 直接插入排序

    1.1.1 程序设计思想

    直接插入排序可把序列分成已排序列和未排序列两个部分,最开始时,第一个元素为排序列,后面的所有元素均为未排序列,在排序的过程中,是把前面的序列看成一个已经排好的序列,把后面的元素逐个插入到前面已排好的序列中。例如序列:25,17,8,49,23,15,20。

    一次排序,25是一个已排好的序列,17,8,49,23,15,20是未排序列,选择未排序列中第一个数17插入到前面的已排序列中,形成序列:17,25,8,49,23,15,20。此时17,25是已排序列,8,49,23,15,20是未排序列。

    二次排序,选择未排序列中第一个数8插入到前面的已排序列,形成已排序列8,17,25,未排序列49,23,15,20,此时整个序列为8,17,25,49,23,15,20。依次类推,直至整个序列有序。