文档库 最新最全的文档下载
当前位置:文档库 › c语言之希尔排序

c语言之希尔排序

c语言之希尔排序
c语言之希尔排序

#include

#define MAX 255

int R[MAX];

void ShellPass(int d, int n)

{/* 希尔排序中的一趟排序,d 为当前增量*/

int i,j;

for(i=d+1;i<=n;i++) /* 将R[d+1..n]分别插入各组当前的有序区*/

if(R[i]

{

R[0]=R[i];j=i-d; /* R[0] 只是暂存单元,不是哨兵*/

do {/* 查找R[i]的插入位置*/

R[j+d]=R[j];/* 后移记录*/

j=j-d; /* 查找前一记录*/

}while(j>0&&R[0]

R[j+d]=R[0]; /* 插入R[i]到正确的位置上*/

} /* endif */

} /* end of ShellPass */

void Shell_Sort(int n)

{

int increment=n; /* 增量初值,设n>0 */

do {

increment=increment/3+1; /* 求下一增量*/

ShellPass(increment,n); /* 一趟增量为increment 的Shell插入排序*/

}while(increment>1);

} /* ShellSort */

void main()

{

int i,n;

//clrscr();

puts("Please input total element number of the sequence:");

scanf("%d",&n);

if(n<=0||n>MAX)

{

printf("n must more than 0 and less than %d.\n",MAX);

exit(0);

}

puts("Please input the elements one by one:");

for(i=1;i<=n;i++)

scanf("%d",&R[i]);

puts("The sequence you input is:");

for(i=1;i<=n;i++)

printf("%4d",R[i]);

Shell_Sort(n);

puts("\nThe sequence after shell_sort is:");

for(i=1;i<=n;i++)

printf("%4d",R[i]);

puts("\n Press any key to quit...");

getch();

}

数据结构课程设计(内部排序算法比较_C语言)

数据结构课程设计 课程名称:内部排序算法比较 年级/院系:11级计算机科学与技术学院 姓名/学号: 指导老师: 第一章问题描述 排序是数据结构中重要的一个部分,也是在实际开发中易遇到的问题,所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决!该系统通过对各种内部排序算法如直接插入排序,冒泡排序,简单选择排序,快速排序,希尔排序,堆排序、二路归并排序等,以关键码的比较次数和移动次数分析其特点,并进行比较,估算每种算法的时间消耗,从而比较各种算法的优劣和使用情况!排序表的数据是多种不同的情况,如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。

第二章系统分析 界面的设计如图所示: |******************************| |-------欢迎使用---------| |-----(1)随机取数-------| |-----(2)自行输入-------| |-----(0)退出使用-------| |******************************| 请选择操作方式: 如上图所示该系统的功能有: (1):选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并 打印出结果。 (2)选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 (3)选择0 打印“谢谢使用!!”退出系统的使用!! 第三章系统设计 (I)友好的人机界面设计:(如图3.1所示) |******************************| |-------欢迎使用---------| |-----(1)随机取数-------| |-----(2)自行输入-------| |-----(0)退出使用-------|

C语言程序设计冒泡排序教学案例

C语言程序设计冒泡排序教学案例 永川职业教育中心杨进【案例背景】 排序是计算机学科中一项复杂而重要的技术,在各种软件中使用频率都很高,因此专家们研究了各种排序算法。在中职类设计课程教学中,常以冒泡排序来讲解排序的原理,它简单,但过程繁琐,传统教学很难激发学生兴趣,学生不易理解,也很难编写掌握冒泡排序。因此,如何合理设计教学过程,让学生掌握冒泡排序的思想和编程方法,又能发散思维,扩充知识,进而激发学生对编程课程的兴趣,是一个关键问题。 1、学情分析 学生已学习了程序设计的三种结构,学习使用了数组。但在学习排序算法的过程中学生可能会对数组变量的变化在理解上存在一定困难,在排序算法中,对双重循环内外层的作用及有关循环参数的设置可能会产生一些不合理或是错误,需要通过实践的体验进行强化使用规范。 2、教学目标 知识目标:掌握冒泡排序的原理;能结合冒泡排序的原理看懂冒泡排序的主要代码;理解冒泡排序的流程图; 能力目标:学会使用冒泡排序思想设计解决简单排序问题的算法;进一步理解程序设计的基本方法,进一步体会算法与程序实现的关系; 情感目标:培养学生分析问题、发现规律的能力,激发学生学习热情;培养良好的读程习惯; 3、教学重点、难点 重点:冒泡排序算法的基本思想,双重循环应用 难点:双重循环程序的解读,冒泡排序算法实现后对程序的理解 4、教学策略与手段 以循序渐进、层层深入为教学的指导方针,采用讲解法、演示法、讨论合作、分析归纳法引导学生参与思考,由特殊到一般,有效地突出重点突破难点,逐步深化对冒泡算法、循环思想和执行过程的理解。

5、课前准备 PPT课件、冒泡排序的视频文件。 【案例描述】 师:在前面的学习中,我们学过了用EXCEL进行一些简单的数据处理方法,请同学们说说看你是怎么对同学的成绩排次序的? 生:先选好数后,点排序就行了。 师:是的。只要用EXCEL的排序功能就可以了,点点鼠标就能完成。在前面的学习中,我们已经解开了很多单击鼠标就可以完成某一个任务的秘密,今天我们就来探访一下排序的秘密。 师:先让我们来做个舞蹈视频,同时要求同学们谈谈看后的自己的想法。并要请几位同学模拟示范。 这段真人编排的排序算法的舞蹈视频,非常生动有趣,能充分吸引学生的眼球,极大激发了学生的兴趣。 播放完毕,老师提问:请同学们说说你们看到了什么? 生:议论并说自己的想法。(冒泡排序的过程) 由于视频播放相对较快,为了让学生更好理解与参与,老师还根据具体情况请了四位涌跃分子来作下一个游戏。 请四位同学从前到后坐好并拿好老师给你们的数字,然后从后面开始两个两个比较你们手中的数,如果后面的同学数小的话就和前面的同学换一下座位,直到拿到最小数的同学坐在第一个位子为止。 现在开始,请其他同学注意观察。 请同学们说说你们看到了什么? 生:议论并说自己的想法 师:我听到了同学们的发言了,你们都看到了最小数已经在最前面了,并且是经过了3次的比较。想一想,如果要让拿第二小的数的同学坐上第二个座位,还要进行几次的比较呢?(注意只能从后开始两两比较)请拿数的同学演示一下。几次? 生:两次 师:对了,是两次,比第一次少了一次。请四位同学回到座位。刚才我们通过四位

C语言的四种排序

简单选择排序 /*对整型数组的元素进行简单选择排序(源程序的整型简单选择排序)*/ #include #include #define N 6 void taxis(int b[],int k) { int i,j,temp; for(i=0;ib[j]) { temp=b[i]; b[i]=b[j]; b[j]=temp; } } void main() { int a[N]={9,8,5,6,2,0},i; clrscr(); taxis(a,N); for(i=0;i #include #define N 6 void taxis(int *p1,int k) { int temp,*p2,*p3; for(p2=p1;p2*p3) { temp=*p2; *p2=*p3; *p3=temp; } } void main() { int a[N]={9,8,5,6,2,0},*p; clrscr(); taxis(a,N); for(p=a;p

printf("%d",*p); if(p #include #include #define N 5 void taxis(char *p1[],int k) { int i,j; char *temp; for(i=0;istrlen(p1[j])) { temp=p1[i]; p1[i]=p1[j]; p1[j]=temp; } } void main() { char *a[]={"Follow","BASIC","Great","FORTRAN","Computer"}; int i; clrscr(); taxis(a,N); printf("The result of taxis is:\n"); for(i=0;i #include #include #define N 5 void taxis(char *p1[],int k) { int i,j; char *temp; for(i=0;i0) { temp=p1[i]; p1[i]=p1[j]; p1[j]=temp; } }

C语言冒泡排序法的简单程序

求一个C语言冒泡排序法的简单程序 悬赏分:50 - 解决时间:2007-9-4 11:16 我不明白怎么写 随便给我个就行 谢谢了 提问者:redangel0002 - 助理二级最佳答案 main() { int i,j,temp; int a[10]; for(i=0;i<10;i++) scanf ("%d,",&a[i]); for(j=0;j<=9;j++) { for (i=0;i<10-j;i++) if (a[i]>a[i+1]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp;} } for(i=1;i<11;i++) printf("%5d,",a[i] ); printf("\n"); } -------------- 冒泡算法 冒泡排序的算法分析与改进 交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。 应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。 冒泡排序 1、排序方法 将被排序的记录数组R[1..n]垂直排列,每个记录R看作是重量为R.key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。 (1)初始 R[1..n]为无序区。 (2)第一趟扫描 从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者在上,则交换二者的位置。即依次比较(R[n],R[n-1]),(R[n-1],R[n-2]),…,(R[2],R[1]);对于每对气泡(R[j+1],R[j]),若R[j+1].key

c语言的三种排序(冒泡,快速,选择)

关于本周学习汇总 1起泡排序: 过程:首先将第一个记录的关键字和第二字的关键字进行比较,若为逆序,则将两个记录交换。然后再比较第二个记录跟第三个记录关键字。以此类推,直到第n-1个记录和第n个记录关键字进行比较为止。这样做出了第一趟排序。其结果是使得最大的数在第n的记录。然后对前n-1的记录进行同样的操作。结果得出次大的大在n-1记录上。最后直到只有第1个和第2个记录进行比较后,完成所有的排序。由此可以看出需要进行k(1<=k void swap(int *,int *); void bubble(int a[];int n); int main(viod) { Int n ,a[8]; Int i; Printf(“enter n(n<=8):”); scanf(“%d”,&n); printf(“enter a[%d]”,n); for(i=0;ia[j+1]) swap2(&a[j],&a[j+1]); } void swap2(int *px,int *py) { Int t; t=*px; px=*py; py=t;

c语言程序设计(排序算法)

《高级语言程序设计》 课程设计报告 题目: 排序算法 专业: 班级: 姓名: 指导教师: 成绩: 计算机与信息工程系 2015年3月26日 2014-2015学年 第2学期

目录 引言 (1) 需求分析 (1) 第一章程序内容及要求 (1) 1.1 冒泡排序 (1) 1.2 选择排序 (2) 1.3 插入排序 (3) 第二章概要设计 (4) 2.1冒泡排序 (4) 2.2选择排序 (5) 2.3插入排序 (6) 第三章程序的比较及其应用 (7) 3.1时间复杂度 (7) 3.2空间复杂度 (7) 3.3稳定程度 (7) 3.4应用及其改进 (8) 第四章程序设计结果 (8) 附录 (9) 参考文献 (12)

引言 伴随着社会的发展,数据也变得越来越庞大。如何将庞大的数据进行很好的排序,使用户更加方便的查找资料,成了一件越来越重要的问题。对于程序员来说,这将是一个挑战。 经常查找资料的朋友都会知道,面对海量的资料,如果其查找资料没有进行排序,那么其查找资料将会是一家非常痛苦的事情。针对这一问题,我们自此通过一个课程设计来解决它。 理论上排序算法有很多种,不过本课程设计只涉及到三种算法。这三种算法包括:冒泡排序,选择排序,直接插入排序。 本课程设计通过对这三种算法的运行情况进行对比,选择最优秀的算法出来。希望通过我的努力能解决一些问题,带来一些方便。 需求分析 本课程题目是排序算法的实现,由于各方面的原因,本科程设计一共需要设计三种排序算法。这三种算法包括:冒泡排序,选择排序,直接插入排序。三种排序算法各有独到之处,因此我们要通过各种调试分析来比较其优劣长短。 由于使用的调试软件及操作系统不一样。因此个别程序在不同的软件上可能会报错。 本课程软件运行的的操作系统为Windows7 64位操作系统。所使用的软件为Microsoft Visual C++6.0以及Turbo C2.0 第一章程序内容及要求 1.1 冒泡排序 冒泡排序(Bubble Sort,台湾译为:泡沫排序或气泡排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。

常见经典排序算法(C语言)1希尔排序 二分插入法 直接插入法 带哨兵的直接排序法 冒泡排序 选择排序 快速排

常见经典排序算法(C语言) 1.希尔排序 2.二分插入法 3.直接插入法 4.带哨兵的直接排序法 5.冒泡排序 6.选择排序 7.快速排序 8.堆排序 一.希尔(Shell)排序法(又称宿小增量排序,是1959年由D.L.Shell提出来的) /* Shell 排序法*/ #include void sort(int v[],int n) { int gap,i,j,temp; for(gap=n/2;gap>0;gap /= 2) /* 设置排序的步长,步长gap每次减半,直到减到1 */ { for(i=gap;i= 0) && (v[j] > v[j+gap]);j -= gap ) /* 比较相距gap远的两个元素的大小,根据排序方向决定如何调换*/ { temp=v[j]; v[j]=v[j+gap]; v[j+gap]=temp; } }

} } 二.二分插入法 /* 二分插入法*/ void HalfInsertSort(int a[], int len) { int i, j,temp; int low, high, mid; for (i=1; i temp) /* 如果中间元素比但前元素大,当前元素要插入到中间元素的左侧*/ { high = mid-1; } else /* 如果中间元素比当前元素小,但前元素要插入到中间元素的右侧*/ { low = mid+1; } } /* 找到当前元素的位置,在low和high之间*/ for (j=i-1; j>high; j--)/* 元素后移*/ { a[j+1] = a[j]; } a[high+1] = temp; /* 插入*/ } }

C语言冒泡排序及流程图(思路解析)

1、功能:冒泡排序 输入:数组名称(也就是数组首地址)、数组中元素个数 ================================================ */ /* ==================================================== 算法思想简单描述: 在要排序的一组数中,对当前还未排好序的范围内的全部数,自上 而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较 小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要 求相反时,就将它们互换。 下面是一种改进的冒泡算法,它记录了每一遍扫描后最后下沉数的 位置k,这样可以减少外层循环扫描的次数。 冒泡排序是稳定的。算法时间复杂度O(n2)--[n的平方] ===================================================== */ void bubble_sort(int *x, int n) { int j, k, h, t; for (h=n-1; h>0; h=k) /*循环到没有比较范围*/ { for (j=0, k=0; j *(x+j+1)) /*大的放在后面,小的放到前面*/ { t = *(x+j); *(x+j) = *(x+j+1); *(x+j+1) = t; /*完成交换*/ k = j; /*保存最后下沉的位置。这样k后面的都是排序排好了的。*/ } } } } 2 在要排序的一组数中,对当前还未排好序的范围内的全部数,自上 而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较

C语言 选择排序

(一)基本思想 每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果: ①初始状态:无序区为R[1..n],有序区为空。 ②第1趟排序 在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 …… ③第i趟排序 第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R交换,使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 [编辑本段]排序过程 【示例】: 初始关键字[49 38 65 97 76 13 27 49] 第一趟排序后13 [38 65 97 76 49 27 49] 第二趟排序后13 27 [65 97 76 49 38 49] 第三趟排序后13 27 38 [97 76 49 65 49] 第四趟排序后13 27 38 49 [49 97 65 76] 第五趟排序后13 27 38 49 49 [97 65 76] 第六趟排序后13 27 38 49 49 65 [97 76] 第七趟排序后13 27 38 49 49 76 [97 76] 最后排序结果13 27 38 49 49 76 76 97 (二)C语言过程 void selectionSort(Type* arr,long len) { long i=0,j=0;/*iterator value*/ long maxPos; assertF(arr!=NULL,"In InsertSort sort,arr is NULL\n"); for(i=len-1;i>=1;i--) { maxPos=i; for(j=0;j

c语言冒泡法详解

最简单的排序方法是冒泡排序方法。 这种方法的基本思想是,将待排序的元素看作是竖着排列的“气泡”,较小的元素比较轻,从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理,就是自底向上检查一遍这个序列,并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对,即“轻”的元素在下面,就交换它们的位置。显然,处理一遍之后,“最轻”的元素就浮到了最高位置;处理二遍之后,“次轻”的元素就浮到了次高位置。在作第二遍处理时,由于最高位置上的元素已是“最轻”元素,所以不必检查。一般地,第i 遍处理时,不必检查第i高位置以上的元素,因为经过前面i-1遍的处理,它们已正确地排好序。 void doit(float* in,int count) { int x; int y; float temp; for(y=0;y(*(in+x-1))) { temp=(*(in+x-1)); (*(in+x-1))=(*(in+x)); (*(in+x))=temp; } } } } 冒泡排序的算法分析与改进 交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。 应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。 冒泡排序 1、排序方法 将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。(1)初始 R[1..n]为无序区。

c语言各种排序法详细讲解

一插入排序 1.1 直接插入排序 基本思想:每次将一个待排序额记录按其关键码的大小插入到一个已经排好序的有序序列中,直到全部记录排好序。 图解:

1.//直接顺序排序 2.void InsertSort(int r[], int n) 3.{ 4.for (int i=2; i

代码实现: [cpp]view plain copy 1.//希尔排序 2.void ShellSort(int r[], int n) 3.{ 4.int i; 5.int d; 6.int j; 7.for (d=n/2; d>=1; d=d/2) //以增量为d进行直接插入排序 8. { 9.for (i=d+1; i0 && r[0]

C语言常用排序算法

/* ===================================================================== ======== 相关知识介绍(所有定义只为帮助读者理解相关概念,并非严格定义): 1、稳定排序和非稳定排序 简单地说就是所有相等的数经过某种排序方法后,仍能保持它们在排序之前的相对次序,我们就 说这种排序方法是稳定的。反之,就是非稳定的。 比如:一组数排序前是a1,a2,a3,a4,a5,其中a2=a4,经过某种排序后为 a1,a2,a4,a3,a5, 则我们说这种排序是稳定的,因为a2排序前在a4的前面,排序后它还是在a4的前面。假如变成a1,a4, a2,a3,a5就不是稳定的了。 2、内排序和外排序 在排序过程中,所有需要排序的数都在内存,并在内存中调整它们的存储顺序,称为内排序; 在排序过程中,只有部分数被调入内存,并借助内存调整数在外存中的存放顺序排序方法称为外排序。 3、算法的时间复杂度和空间复杂度 所谓算法的时间复杂度,是指执行算法所需要的计算工作量。 一个算法的空间复杂度,一般是指执行这个算法所需要的内存空间。 ===================================================================== =========== */ /* ================================================ 功能:选择排序 输入:数组名称(也就是数组首地址)、数组中元素个数 ================================================ */ /* ==================================================== 算法思想简单描述:

C语言综合实现所有排序方法及效率比较

#include #include #include #include #define N 50000 typedef char elemtype; typedef struct { int key; elemtype otheritem; }recdtype,*Recdtype; recdtype R[N]; //直接插入排序 void InsertSort(Recdtype R,int n) { int i,j; for(i=2;i<=n;i++) { R[0]=R[i]; j=i-1; while(R[0].key=high+1;j--) R[j+1]=R[j]; R[high+1]=R[0];

} }/*BinSort*/ //希尔排序 void ShellSort(recdtype R[],int n) { int i,j; for(int d=N/2;d>=1;d=d/2) { for(i=1+d;i<=n;i++) { R[0]=R[i]; j=i-d; while(j>0&&R[0].key=i;j--) { if(R[j+1].key

数据结构(C语言版)实验报告-(内部排序算法比较)

数据结构与算法》实验报告 一、需求分析 问题描述:在教科书中,各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。 基本要求: (l )对以下 6 种常用的内部排序算法进行比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 (2 )待排序表的表长不小于100000 ;其中的数据要用伪随机数程序产生;至少要用 5 组不同的输入数据作比较;比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换计为 3 次移动)。 ( 3 )最后要对结果作简单分析,包括对各组数据得出结果波动大小的解释。数据测试:二.概要设计 1. 程序所需的抽象数据类型的定义: typedef int BOOL; typedef struct StudentData { } Data; typedef struct LinkList { Data Record[MAXSIZE]; int num; // 存放关键字 int Length; // 数组长度// 用数组存放所有的随机数 // 说明BOOL 是int 的别名 } LinkList int RandArray[MAXSIZE]; // 定义长度为MAXSIZE 的随机数组 void RandomNum() // 随机生成函数

void InitLinkList(LinkList* L) // 初始化链表 // 比较所有排序 2 . 各程序模块之间的层次(调用)关系: BOOL LT(int i, int j,int* CmpNum) // 比较 i 和 j 的大小 void Display(LinkList* L) // 显示输出函数 void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum) void QuickSort (LinkList* L, // 快速排序 void HeapSort (LinkList* L, // 堆排序 void BubbleSort(LinkList* L, // 冒泡排序 void SelSort(LinkList* L, // 选择排序 int* CmpNum, int* ChgNum) int* CmpNum, int* ChgNum) int* CmpNum, int* ChgNum) * CmpNum, int* ChgNum) void Compare(LinkList* L,int* CmpNum, int* ChgNum) // 希尔排序

C语言之选择排序

选择法排序是相对好理解的排序算法。假设要对含有n个数的序列进行升序排列,算法步骤是: 1、从数组存放的n个数中找出最小数的下标(算法见下面的“求最值”),然后将最小数与第1个数交换位置; 2、除第1个数以外,再从其余n-1个数中找出最小数(即n个数中的次小数)的下标,将此数与第2个数交换位置; 3、重复步骤1 n-1趟,即可完成所求。 好了,接下来看代码:

1.#include 2.#include 3.#define n 10 4.int main() 5.{ 6.int a[n],i,j,k,t; 7. printf("随机产生10个100以内的数:\n"); 8.for(i=0;i

排序算法C语言版:直接插入排序

直接插入排序 算法思想简单描述: 在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排 好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。 直接插入排序是稳定的。算法时间复杂度O(n^2) 算法实现: /* 功能:直接插入排序 输入:数组名称(也就是数组首地址)、数组中元素个数 */ void insert_sort(int *x, int n) { int i, j, t; for (i=1; i

*/ t=*(x+ I ); for (j=i-1; j>=0 && t<*(x+j); j--) /*注意:j=i-1,j--,这里就是下标为i的数,在它前面有序列中找插入位置。*/ { *(x+j+1) = *(x+ j ); /*如果满足条件就往后挪。最坏的情况就是t比下标为0的数都小,它要放在最前面,j==-1,退出循环*/ } *(x+j+1) = t; /*找到下标为i的数的放置位置*/ } }

#include "stdio.h" #include "conio.h" main() { int a[11]={1,4,6,9,13,16,19,28,40,100}; int temp1,temp2,number,end,i,j; printf("original array is:\n"); for(i=0;i<10;i++) printf("%5d",a[i]); printf("\n"); printf("insert a new number:"); scanf("%d",&number); end=a[9]; if(number>end) a[10]=number; else { for(i=0;i<10;i++) { if(a[i]>number) { temp1=a[i]; a[i]=number; for(j=i+1;j<11;j++) { temp2=a[j]; a[j]=temp1; temp1=temp2; } break; } } } for(i=0;i<11;i++) printf("%6d",a[i]); getch();

C语言冒泡排序法

main() { int i,j,temp; int a[10]; for(i=0;i<10;i++) scanf ("%d,",&a[i]); for(j=0;j<=9;j++) { for (i=0;i<10-j;i++) if (a[i]>a[i+1]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp;} } for(i=1;i<11;i++) printf("%5d,",a[i] ); printf("\n"); } -------------- 冒泡算法 冒泡排序的算法分析与改进 交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。 应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。 冒泡排序 1、排序方法 将被排序的记录数组R[1..n]垂直排列,每个记录R看作是重量为R.key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。 (1)初始 R[1..n]为无序区。 (2)第一趟扫描 从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者在上,则交换二者的位置。即依次比较(R[n],R[n-1]),(R[n-1],R[n-2]),…,(R[2],R[1]);对于每对气泡(R[j+1],R[j]),若R[j+1].key

C语言三种基本排序(简单排序,选择排序,插入排序)演示程序(含注释、每一个步骤,原创) -修订

/******************************************************* 三种基本排序演示程序 说明:此程序适用于理解三种基本排序原理(简单排序,选择排序,插入排序)以及排序的每一个步骤。并且在重要部分有注释. 本人是一家计算机培训机构的兼职教师(培训计算机C二级的),看到许多同学对于排序非常头疼,当然这是二级C的必考点之一,也是贯穿C语言各种知识点的拿分大项。 本程序是自己按照原理写的原创代码,所以定为1分吧(辛苦费吧,一般我搜集的都是免费的(*^__^*) ……,望大家支持下) 此程序我调试运行成功的,如果你复制到编译器不成功,可能是编译器区别造成的。 如果能自己写出这三种排序的同学,我觉得其对C语言基础知识学习就比较牢固了。 时间:2012年12月3日 ********************************************************/ #include #include void main() { int a[5]={5,4,3,2,1}; int i,j,temp,k,s; for(s=0;s<5;s++) { printf("%3d",a[s]); } printf("简单排序\n"); for(i=0;i<5-1;i++)//基准位到倒数第二个就行了,因为最后一个数没有比较 { printf("%d\n",i);/////////////////////////////// for(j=i+1;j<5;j++) { if(a[j]

C语言用函数冒泡排序

C语言程序设计实验报告 1实验目的 1.透彻理解函数的概念。 2.掌握函数的定义方法。 3.了解函数地形参和实参之间的对应关系及“值传递”地方式。 4.了解函数的返回值的概念。 2实验内容 写一主函数输入一数组,写一子函数实现对该数组的冒泡排序并输出。 输入数据:12,21,33,5,19,27,6,4,38,47,29,56,97 3算法描述流程图

主函数:子函数bub:

4源程序 #include int bub(int a[13]) { int i,j,k; for(j=0;j<13;j++) for(i=0;i<13-j;i++) { if(a[i]>a[i+1]) { k=a[i+1]; a[i+1]=a[i]; a[i]=k; } } printf("排序好的数为;"); for(i=0;i<13;i++) printf("%4d",a[i]); printf("\n"); return 0; } void main() { int m[13],k; for(k=0;k<13;k++) scanf("%d",&m[k]); for(k=0;k<13;k++) printf("%4d",m[k]); printf("\n"); bub(m); } 5测试数据 输入数据:12,21,33,5,19,27,6,4,38,47,29,56,97 6运行结果

7出现问题及解决方法 开始时不知道如何进行控制循环仅用一个for循环无法实现冒泡排序,只能找出最大值; 用两个for循环。 8实验心得 C语言在实践中更容易掌握。

C语言冒泡、插入法、选择排序算法分析

C语言中三种常见排序算法分析 一、冒泡法(起泡法) 算法要求:用起泡法对10个整数按升序排序。 算法分析:如果有n个数,则要进行n-1趟比较。在第1趟比较中要进行n-1次相邻元素的两两比较,在第j趟比较中要进行n-j次两两比较。比较的顺序从前往后,经过一趟比较后,将最值沉底(换到最后一个元素位置),最大值沉底为升序,最小值沉底为降序。 算法源代码: # include main() { int a[10],i,j,t; printf("Please input 10 numbers: "); /*输入源数据*/ for(i=0;i<10;i++) scanf("%d",&a[i]); /*排序*/ for(j=0;j<9;j++) /*外循环控制排序趟数,n个数排n-1趟*/ for(i=0;i<9-j;i++) /*内循环每趟比较的次数,第j趟比较n-j次*/ if(a[i]>a[i+1]) /*相邻元素比较,逆序则交换*/ { t=a[i]; a[i]=a[i+1]; a[i+1]=t; } /*输出排序结果*/ printf("The sorted numbers: "); for(i=0;i<10;i++) printf("%d ",a[i]); printf("\n"); } 算法特点:相邻元素两两比较,每趟将最值沉底即可确定一个数在结果的位置,确定元素位置的顺序是从后往前,其余元素可能作相对位置的调整。可以进行升序或降序排序。 算法分析:定义n-1次循环,每个数字比较n-j次,比较前一个数和后一个数的大小。然后交换顺序。二、选择法 算法要求:用选择法对10个整数按降序排序。 算法分析:每趟选出一个最值和无序序列的第一个数交换,n个数共选n-1趟。第i趟假设i为最值下标,然后将最值和i+1至最后一个数比较,找出最值的下标,若最值下标不为初设值,则将最值元素和下标为i的元素交换。 算法源代码: # include main() { int a[10],i,j,k,t,n=10; printf("Please input 10 numbers:"); for(i=0;i<10;i++) scanf("%d",&a[i]);

相关文档
相关文档 最新文档