几种简单排序算法的实现研究

吴昊

摘 要：“排序算法”是“数据结构”课程中很重要的一个章节内容，其部分算法思想在“C语言程序设计”课程中也进行过程序描述，算法思想和程序转换对于初学者来说较难理解，因此，实现这两种形式的对接是教学工作的重点。本文通过设置变量的初始值，巧妙将关键变量的使用实现“两步走”，帮助初学者加强对算法的理解。

关键词：排序;程序设计;算法

本文将具体对直接插入法进行详细地介绍，帮助初学者更好地理解这几种排序算法的程序设计思路。

1. 三种简单排序算法的实现思想及C程序实现过程

（1）直接插入排序。①算法思想。直接插入排序把序列分成有序序列 （前）和无序序列（后）两个部分，其实质是把无序序列中的第一个元素插入到有序序列的对应位置。如果序列中的元素为n，则需要进行n-1次插入，每次插入需要做若干次比较。②C程序实现过程。

#define N 10

main（）

{

int a[N]，i，j，t;     //i，j分别用来做插入和比较的循环计数变量

//此外，i还用来表示无序序列中第一个元素的下标

//从键盘中输入数给数组a[N]中的每个元素

for（i=0;i

scanf（"%d"，&a[i]）;

for（i=1;i

if（a[i]

{           //的最后一个元素小，则需插入

t=a[i];

a[i]=a[i-1];//有序序列中的最后一个元素后移

for（j=i-2;j>=0;j--）//从有序序列的倒数第二个元素开始比较

if（a[j]>t）a[j+1]=a[j];

else break;

a[j+1]=t;

}

}

（2）冒泡排序。①算法思想。冒泡排序把序列分成无序（前）和有序 （后）两个序列，其实质是把无序序列中相邻两个元素依次比较，大者下沉 （后移），移动到最后的元素即为有序序列的第一个元素，多次冒泡以后直至序列有序。如果序列中的元素为n，则需要进行n-1次冒泡，每次冒泡需要做若干次比较。②C程序实现过程。

#define N 10

main（）

{

int a[N]，i，j，t;//i，j分别用来做冒泡和比较的循环计数变量，

//此外，i还用来表示无序序列中倒数第二个数

//从键盘中输入数给数组a[N]中的每个元素

for（i=0;i

scanf（"%d"，&a[i]）;

for（i=N-2;i>=0;i--）

for（j=0;j<=i;j++）

if（a[j]>a[j+1]）//无序序列中的相邻两个元素两两相互比较

{

t=a[j+1];

a[j+1]=a[j];

a[j]=t;

}

}

（3）简单选择排序。①算法思想。简单选择排序把序列分成有序（前）和无序（后）两个部分，其实质是在无序序列中选择一个最小的数放在无序序列的开始，并作为有序序列的最后一个数，若干次选择以后直至序列有序。如果序列中的元素为n，则需要进行n-1次选择，每次选择需要做若干次比较。②C程序实现过程。

#define N 10

main（）

{

int a[N]，i，j，k，t;   //i，j分别用来做选择和比较的循环计数变量，

//此外，i用来表示无序序列中的第一个元素

//k用来记录无序序列中最小元素的下标

//从键盘中输入数给数组a[N]中的每个元素

for（i=0;i

scanf（"%d"，&a[i]）;

for（i=0;i

{  k=i; //把无序序列中的第一个元素作为最下的数

for（j=i+1;j

if（a[k]>a[j]）  k=j;

t=a[i];a[i]=a[k];a[k]=t;//把无序序列中的最小元素放到无序序列首位

}

}

2.结束语

本文主要针对“数据结构”中的一些简單排序算法的程序设计方法进行了一些探讨研究，其主要思路是更好地设计程序中的变量，清晰地表述每个变量的作用和意义，便于学生理解和掌握。但排序中还有很多较为复杂的算法，其教学过程具有灵活性、多样性，其教学方法还有待于深入探讨和研究。

（作者单位：广西师范学院师园学院）