幾種簡單排序算法的實現研究

吳昊

摘 要：“排序算法”是“數據結構”課程中很重要的一個章節內容，其部分算法思想在“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.結束語

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

（作者單位：廣西師范學院師園學院）