C课件3.数组幻灯片.pptVIP

* * * 排序过程： 将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].keyr[2].key，则交换；然后比较第二个记录、第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序结果使关键字最大的记录被安置在最后一个记录上。 对前n-1个记录进行第二趟冒泡排序，使关键字次大的记录被安置在第n-1个记录位置。 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。 性质：属于最简单的排序 ，效率最差，算法最简单。仅适合数据量较少的场合 。 交换排序——冒泡排序 使关键字最小的数据如气泡一般，逐渐往上“漂浮”，使最大的逐渐“下沉” 。如图所示： 97 例： 初始状态 第一趟 第二趟 第三趟 第四趟 第五趟 第六趟 38 49 97 97 27 30 97 65 76 76 49 27 30 13 13 30 65 13 13 49 76 65 49 27 30 27 38 38 38 76 13 65 49 97 76 65 30 27 13 38 27 38 49 97 76 65 30 30 38 49 97 76 65 第七趟 30 38 49 97 76 65 27 13 8个元素 void BubbleSort( int a[], int n ) { //数组中有n个元素 int i，j，x; for(i=1;in;i++) { for(j=0;jn-i;j++) //找到一组中最大者 { if(a[j]a[j+1]) //进行交换 { x = a[j]; a[j] = a[j+1]; a[j+1] = x; } } } } “趟”扫描. 只做n-2次 每“趟”中作元素比 较扫描.也做n-2次 冒泡排序实现 P 插入排序 直接插入排序： 直接插入排序是一种简单的、稳定排序方法。 排序过程： 整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序的子序列，然后从第2个记录开始，逐个加入到前面的有序子序列中，直至整个原序列中的元素处理完为止。 算法示意图： 已排好的 未排的 将当前元素插入合适位置上 原序列： 49 38 65 97 76 13 27 i=2 ( 38 49 ) 65 97 76 13 27 i=3 ( 38 49 65 ) 97 76 13 27 i=4 ( 38 49 65 97 ) 76 13 27 i=5 ( 38 49 65 76 97 ) 13 27 i=6 ( 13 38 49 65 76 97 ) 27 i=1 ( ) i=7 ( 13 27 38 49 65 76 97 ) 97 76 65 13 13 27 38 49 65 76 97 排序结果： 38 括号内是有序子序列 27 7个元素 void InsertSort( RecType R[], int n ) { int i,j; RecType temp; for ( i=1; in; ++i ) { temp=R[i]; j=i-1; // 从右向左在R[0..i-1]内找R[i]的插入位置 while (j=0 temp.keyR[j].key) { R[j+1]=R[j]; //将关键字大于R[i].key的记录后移 j--; // 向前移动一个位置 } R[j+1]=temp; // 在合适的位置j+1处插入R[i]