软件技术基础排序.ppt

教学目标 了解有关排序的 基本概念 排序的典型算法 二叉排序树 排序(Sorting) 将一个无序序列整理成按值非递减（或非递增）顺序排列的有序序列。 排序可以在不同的存储结构上实现。 基本排序是在顺序存储的线性表中实现的； 二叉排序树利用二叉树的链式存储结构实现无序表的有序化。 三种基本排序方法： 交换排序 （如 冒泡排序和快速排序）； 插入排序 （如 简单插入排序和希尔排序）； 选择排序 （如 简单选择排序和堆排序）； 排序算法的数据结构 顺序存储结构（C语言描述）： #define N n struct record { int key ； /* 关键字项 */ int otherterm；/* 其它项 */ } ； typedef struct record RECORD； RECORD file[N+1]； 二、典型排序算法 冒泡排序 快速排序 简单插入排序 希尔排序 简单选择排序 堆排序 交换排序 冒泡排序 冒泡排序（Bubble sort）是基于交换排序的一种算法。它是依次两两比较待排序元素；若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”。每趟冒泡都将待排序列中的最大关键字交换到最后（或最前）位置。直到全部元素有序为止。 ? ? ? … ? a1 a2 a3 … an-1 an 冒泡排序算法举例 设有数列{ 65,97,76,13,27,49,58 } 比较次数 第1趟 {65，76，13，27，49，58}，{97} 6 第2趟 {65，13，27，49，58}，{76，97} 5 第3趟 {13，27，49，58}，{65，76，97} 4 第4趟 {13，27，49}，{58，65，76，97} 3 第5趟 {13，27}，{49，58，65，76，97} 2 第6趟 {13}，{27，49，58，65，76，97} 1 总计： 21 次 冒泡排序算法 bubble(int *item,int count) { int a,b，t; for(a=1;acount;++a)/* n-1 趟冒泡处理 */ for(b=1;b=count-a;b++)/*每趟n-i次比较 */ if(item[b-1]item[b])/*若逆序,则交换*/ { t=item[b-1]; /* 它们的位置 */ item[b-1]=item[b]; item[b]=t; } } 冒泡排序算法主程序 #define N 7 #include stdio.h main() { int s[]={65,97,76,13,27,49,58},i; bubble(s,N); /* 调用选择排序函数 */ printf(The sorted string is:\n); for(k=0;kN;k++) printf( %d,s[k]); } 改进的冒泡排序算法 从上述举例中可以看出，从第4趟冒泡起，序列已有序，结果是空跑了3趟。若两次冒泡处理过程中，没有进行交换，说明序列已有序，则停止交换。这就是改进的冒泡算法的处理思想。 用改进的冒泡算法处理，比较次数有所减少。 数列{ 65,97,76,13,27,49,58 } 比较次数 第1趟 {65，76，13，27，49，58}，{97} 6 第2趟 {65，13，27，49，58}，{76，97} 5 第3趟 {13，27，49，58}，{65，76，97} 4 第4趟 {13，27，49}，{58，65，76，97} 3 总计： 18 次 改进的冒泡排序算法 bubble_a(int *item,int count) { int a,b,t,c; for(a=1;acount;++a) /* n-1趟的循环 */ { c=1; /* 设置交换标志 */ for(b=1;b=count-a;b++)