数据结构课程设计(各种排序算法实现).docx

数据构造

课程设计报告

题目：

专业：

班级：

学号：

姓名：

1

指导老师：

时间：

2

一、课程设计题目及所波及知识点

设计题目：排序算法实现

知识点：malloc申请连续储存空间、冒泡排序、迅速排序、直接插入排序的算法实现、

构造体的定义与调用、函数的递归调用

二、课程设计思路及算法描绘

设计思路：1、确立程序要实现的功能即（1）同意用户输入一组数据，随意多个。

2）由用户选择对该组数据进行排序的方法：直接插入排序、冒泡排序、迅速排序。并能够查察每趟排序的结果。

2、确立程序所需要的功能块，储存构造-构造体，malloc申请储存空间，各功能函数--冒泡

排序功能块maopao( )；、直接插入排序功能块insertsort( )；、迅速排序q_sort(）；、数据接见功

能块traveres( )；、数据输出功能块liststring( );主函数部分main( )；。

3、编写代码详细实现各项功能，并进行调试。

算法描绘：冒泡排序（BubbleSorting）的基本思想：

设待排序n个元素寄存在数组a[n]中,无序区范围初始为(a(0),a(1),a(2),...,a[n-1]),

冒泡排序方法是在目前无序区内,从最上边的元素a[0]开始,对每两个相邻的元素a[i+1]和

a[i](i=0,1,...,n-1)进行比较,且使值较小的元素换至值较大的元素之上(若a[i]>a[i+1],

则a[i]和a[i+1]的值交换),这样经过一趟冒泡排序后,假定最后下移的元素为a[k],则无序

区中值较大的几个元素抵达下端并从小到大挨次寄存在a[k+1],a[k+2],...a[n-1]中,这样

无序区范围变成(a[0],a[1],a[2],...,a[k])。在目前无序区内进行下一趟冒泡排序。这个

过程向来到某一趟排序中不出现元故旧换的动作，排序结束。整个排序过程最多履行n-1遍。

算法实现：

voidBubbleSort(SeqListR)

//R（l..n)是待排序的文件，采纳自下向上扫描，对R做冒泡排序

{

inti，j；

Booleanexchange；//交换标记

for(i=1;i<n;i++){//最多做n-1趟排序

exchange=FALSE；//本趟排序开始前，交换标记应为假

for(j=n-1;j>=i；j--)//对目前无序区R[i..n]自下向上扫描

if(R[j+1].key<R[j].key){//交换记录

R[0]=R[j+1]；//R[0]不是标兵，仅做暂存单元

R[j+1]=R[j]；

R[j]=R[0]；

exchange=TRUE；//发生了交换，故将交换标记置为真

}

if(!exchange)//本趟排序未发生交换，提早停止算法

return；

}//endfor(外循环)

}//BubbleSort

直接插入排序（StraightInsertionSorting）的基本思想：

把n个待排序的元素当作为一个有序表和一个无序表，开始时有序表中只包括一个元素，无序表中包括有n-1个元素，排序过程中每次从无序表中拿出第一个元素，将它插入到有序

表中的适合地点，使之成为新的有序表，重复n-1次可达成排序过程。

把a[i]插入到a[0]，a[1]，...,a[i-1]之中的详细实行过程为:先把a[i]赋值给变量t,然

后将t挨次与a[i-1],a[i-2],...进行比较,将比t大的元素右移一个地点,直到发现某个

3

j(0<=j<=i-1),使得a[j]<=t或j为(-1),把t赋值给a[j+1].

算法实现：

voidinsert_sort(ElemTypea[],intn)

待排序元素用一个数组a表示，数组有n个元素

{inti,j;

ElemTypet;

for(i=1;i<n;i++)//i表示插入次数，共进行n-1次插入

{t=a[i];//把待排序元素赋给t

j=i-1;

while((j>=0)&&(t<a[j])){

a[j+1]=a[j];j--;}//次序比较和挪动

a[j+1]=t;}

}

迅速排序算法：

在R[low..high]中任选一个记录作为