C语言数据排序专题复习

1、C语言数据排序专题复习排序是将一个无序的数据序列按照某种顺序重新排列。用数组存放要排序的数据序列。本专题介绍几种常用的排序方法，均假设数据从小到大排序。1. 冒泡排序(又称起泡法)基本思路：每轮排序找余下的数据中的最小值定位在最前，故每经过一轮排序确定一个位置，余下的数据就减少一个。n个数排序要经过 n-1轮排序。排序要用二重循环实现，外循环表示排序的轮次，内循环示每轮排序将最小值交换到最前面。(以10个数从小到大排序为例 )第1轮排序，下标i的值为0,找a0 a9,10个数中找最小值，将最小值交换到a0位置，最小值初值为 a0,要将a1 a9每个元素逐一 与a0 比较，如果比a0 小,就与a

2、0交换。第2轮排序，下标i的值为1,找a1-a9,9个数中找最小值，将最小 值交换到 a 1位置，最小值初值为 a1,要将a2 a9每个元素逐一与a1比较，如 果比a1 小,就与a1交换。依次类推。10个数排序，外循环变量i的取值从0 8 (小于9)表示要经过9轮排 序，注意观察i=0,第1轮排序，内循环与最小值比较的元素是a 1到a 9,i =1,第2轮排序，内循环与最小值比较的元素是a 2到a 9,内循环用j表示元素下标，终值固定为 9,初值i=0时,j=1; i=1 时,j=2; j=i+1 程序清单：main。 int i, j, a10, t; /*t用于交换的变量*/for(i=0

3、;i<10;i+)scanf( "%d ” , &ai);for(i=0;i<9;i+)for(j=i+1 ; j<10; j+)if(ajvai)(t=ai;ai=aj;aj=t;for(i=0;i<10;i+)prin tf( "%4d" ,ai); 冒泡排序另外一种表达形式：前面程序是每轮排序找最小值定位在最前面，换一种思路，每一轮排序找最大值定位在最后面。每轮排序将相邻的元素两两比较，如果前面元素较大，则交换到后面。程序清单:mainOint i, j, a10, t;for(i=0;i<10;i+)scanf ( &

4、quot;%d ” ，&ai);for(i=0;i<9;i+)for(j=0;j<9-i;j+)if (aj>aj+1) (t=aj ;aj=aj+1 ;aj+1=t;for(i=0;i<10;i+)pr intf ( "%4d ” ,ai); 选择排序 ( 冒泡排序的改进 ) 在冒泡排序的基础上增加了一个变量，表示每轮排序的最小值的下标。如 果每 轮排序找出最小值的下标与初始值不一致时，则应交换该两个下标对 应的元素， 选择排序每轮排序最多交换了一次数据，大大减少了数据交换 的次数。 程序清单： main 。 int i, j, k, t;for(i

5、=0;i<10;i+)scanf ( "%d ” , &ai);for(i=0;i<9;i+) k=i ;for(j=i+1;j<10;j+) if(aj<ak)k=j;if (k! = i) t=ai ;ai=ak ;ak=t; for(i=0;i<10;i+)pr intf( "%4d ” ,ai); . 插入排序排序的基本思路：将数组元素分为两个区域，有序区 a0 ai-1, 无序 区 ai a9, 每轮排序是将无序区的第一个元素插入到有序区中，首 先将无 序区的第一个元素与有序区的最后一个元素比较，如果小，继续与 有序区的倒 数

6、第二个元素比，依次类推，直到比有序区的某个元素大时就 找到了插入位置， 既插到该元素后。每经过一轮排序有序区增加一个元素， 第一轮排序前，有序 区元素个数为 1, 既只有 a0.程序清单： ma i n () int i, j, t, a10:for(i=0;i<10;i+)scanf( "%d" , &ai);for(i=1;i<10;i+)if (ai<ai-1)( t=ai;j=i-1:do aj+1=aj ;/* 有序区的元素向后移 */j- ；/*j 下标自减，继续与有序区的前一个元素比较*/wh iIe(j>=O&&

7、;t<aj);aj+1=t; /* 将无序区的元素插入到该元素后 */for(i=0;i<10;i+)printf( "%4d ” ,ai); . 归并排序法： ( 前提是两个数组的元素均已按同一规律排好了序，此题 均 已从小到大排好了序 )如果有 2 个数组均已从小到大排好了序，现将该两个数组的元素合并成一个数组，合并后仍从小到大排列。程序清单 :main() int i, j, k, a10, b10, c20:for(i=0;i<10;i+)scanf( "%d ” , &ai);for(i=0;i<10;i+)scanf ( &quo

8、t;%d ” ， &bi); 注意：两个数组元素输入时，均按从小到大 顺序 输入i=0, j=0, k=0;while(i<10&&j<10)if (ai<bj)(ck+=ai;i+;e I se(ck+=bj;j+;whi le(i<10)ck+=ai;i+ ； whi le(j<10)ck+=bj;j+ ； for(i=0;i<20;i+)pr intf( "%4d ” ,ci); . 字符串的排序输入五个字符串，将它们按从小到大的顺序排序后输出。分析：因为在 C 语言中没有字符串变量，对字符串的操作可用字符数组或 指向

9、 字符串的指针实现，又由于此题涉及到多个字符串，可用字符串的二 维数组实 现。另外字符串的赋值与比较只能用专用函数strcpy () 和 strcmpO 实现。对于数值型数据的交换，可通过一个中间变量用一组赋值语句实现， 但对于字符 串的交换，不能用中间变量实现交换，只能用一个字符串数组来代替此中间变量。程序清单如下：#include <str ing. h>#include <stdio.h>/*t 数组用于实现字符串的交换 */ma i n () char str5 20,t20;int i, j;for(i=0;i<5;i+) gets(str i);for

10、(i=0;i<4;i+) for(j=i+1;j<5;j+) if (strcmp(strj, stri)<0) (strcpy (t,stri);strcpy(stri, strj);strcpy(strj, t);1 for(i=0;i<5;i+) puts(str i); 利用指针对字符串排序 #include <str ing. h> #include <stdio.h> void sort (char *str) (char *t; int i, j;for(i=0; i<4;i+) for(j=i+1;j<5;j+) if

11、 (strcmp(strj, stri)<0) t=stri ;stri=strj ;strj=t; ma i n ()( int i;char *sL5J-t china , indan , japan , russia , korea J; sort (s);for(i=0; i<5;i+)n” ， si); 以上程序是实现将已知的五个字符串，从小到大排列后输出 利用二级指针对多个字符串从小到大排序 #i nclude "std i o.h" #i nclude "str i ng. h" void sort (char *s,char

12、*p) (char *q, *t, *r;for (q 二 p;q s+4;q+)for (t=q+1;t<s+5;t+)if (strcmp(*t, *q)<0)(r=*q;*q=*t;*t=r;vo i d ma i n ()char *str L5J-1 china , russia , japan , austrla , indan ), *p; p=&str0;sort (str,p);for(p=str;p<str+5;p+)puts (*p); . 对链表中结点的数据域从小到大排序后输出 假设链表已创建成功 struct nodeint c j;struct node *next;struct node *sort (struct node *head) /*head 为链表头指针 */ ( struct node *p, *q;int t;for(p 二 head;p!=NULL;p=p->next)for (q=p->next;q!=NULL;q=q->next)i f (q->cj<p->cj)t=p->cj;p-