吳昊

摘 要：“排序算法”是“數(shù)據(jù)結(jié)構(gòu)”課程中很重要的一個(gè)章節(jié)內(nèi)容，其部分算法思想在“C語(yǔ)言程序設(shè)計(jì)”課程中也進(jìn)行過(guò)程序描述，算法思想和程序轉(zhuǎn)換對(duì)于初學(xué)者來(lái)說(shuō)較難理解，因此，實(shí)現(xiàn)這兩種形式的對(duì)接是教學(xué)工作的重點(diǎn)。本文通過(guò)設(shè)置變量的初始值，巧妙將關(guān)鍵變量的使用實(shí)現(xiàn)“兩步走”，幫助初學(xué)者加強(qiáng)對(duì)算法的理解。

關(guān)鍵詞：排序;程序設(shè)計(jì);算法

本文將具體對(duì)直接插入法進(jìn)行詳細(xì)地介紹，幫助初學(xué)者更好地理解這幾種排序算法的程序設(shè)計(jì)思路。

1. 三種簡(jiǎn)單排序算法的實(shí)現(xiàn)思想及C程序?qū)崿F(xiàn)過(guò)程

（1）直接插入排序。①算法思想。直接插入排序把序列分成有序序列 （前）和無(wú)序序列（后）兩個(gè)部分，其實(shí)質(zhì)是把無(wú)序序列中的第一個(gè)元素插入到有序序列的對(duì)應(yīng)位置。如果序列中的元素為n，則需要進(jìn)行n-1次插入，每次插入需要做若干次比較。②C程序?qū)崿F(xiàn)過(guò)程。

#define N 10

main（）

{

int a[N]，i，j，t; ? ? //i，j分別用來(lái)做插入和比較的循環(huán)計(jì)數(shù)變量

//此外，i還用來(lái)表示無(wú)序序列中第一個(gè)元素的下標(biāo)

//從鍵盤(pán)中輸入數(shù)給數(shù)組a[N]中的每個(gè)元素

for（i=0;i

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

for（i=1;i

if（a[i]

{ ? ? ? ? ? //的最后一個(gè)元素小，則需插入

t=a[i];

a[i]=a[i-1];//有序序列中的最后一個(gè)元素后移

for（j=i-2;j>=0;j--）//從有序序列的倒數(shù)第二個(gè)元素開(kāi)始比較

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

else break;

a[j+1]=t;

}

}

（2）冒泡排序。①算法思想。冒泡排序把序列分成無(wú)序（前）和有序 （后）兩個(gè)序列，其實(shí)質(zhì)是把無(wú)序序列中相鄰兩個(gè)元素依次比較，大者下沉 （后移），移動(dòng)到最后的元素即為有序序列的第一個(gè)元素，多次冒泡以后直至序列有序。如果序列中的元素為n，則需要進(jìn)行n-1次冒泡，每次冒泡需要做若干次比較。②C程序?qū)崿F(xiàn)過(guò)程。

#define N 10

main（）

{

int a[N]，i，j，t;//i，j分別用來(lái)做冒泡和比較的循環(huán)計(jì)數(shù)變量，

//此外，i還用來(lái)表示無(wú)序序列中倒數(shù)第二個(gè)數(shù)

//從鍵盤(pán)中輸入數(shù)給數(shù)組a[N]中的每個(gè)元素

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]）//無(wú)序序列中的相鄰兩個(gè)元素兩兩相互比較

{

t=a[j+1];

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

a[j]=t;

}

}

（3）簡(jiǎn)單選擇排序。①算法思想。簡(jiǎn)單選擇排序把序列分成有序（前）和無(wú)序（后）兩個(gè)部分，其實(shí)質(zhì)是在無(wú)序序列中選擇一個(gè)最小的數(shù)放在無(wú)序序列的開(kāi)始，并作為有序序列的最后一個(gè)數(shù)，若干次選擇以后直至序列有序。如果序列中的元素為n，則需要進(jìn)行n-1次選擇，每次選擇需要做若干次比較。②C程序?qū)崿F(xiàn)過(guò)程。

#define N 10

main（）

{

int a[N]，i，j，k，t; ? //i，j分別用來(lái)做選擇和比較的循環(huán)計(jì)數(shù)變量，

//此外，i用來(lái)表示無(wú)序序列中的第一個(gè)元素

//k用來(lái)記錄無(wú)序序列中最小元素的下標(biāo)

//從鍵盤(pán)中輸入數(shù)給數(shù)組a[N]中的每個(gè)元素

for（i=0;i

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

for（i=0;i

{ ?k=i; //把無(wú)序序列中的第一個(gè)元素作為最下的數(shù)

for（j=i+1;j

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

t=a[i];a[i]=a[k];a[k]=t;//把無(wú)序序列中的最小元素放到無(wú)序序列首位

}

}

2.結(jié)束語(yǔ)

本文主要針對(duì)“數(shù)據(jù)結(jié)構(gòu)”中的一些簡(jiǎn)單排序算法的程序設(shè)計(jì)方法進(jìn)行了一些探討研究，其主要思路是更好地設(shè)計(jì)程序中的變量，清晰地表述每個(gè)變量的作用和意義，便于學(xué)生理解和掌握。但排序中還有很多較為復(fù)雜的算法，其教學(xué)過(guò)程具有靈活性、多樣性，其教學(xué)方法還有待于深入探討和研究。

（作者單位：廣西師范學(xué)院師園學(xué)院）