资源描述：
《C语言常见排序算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、上章回顾二叉树的定义树深度的定义什么样的二叉树是满二叉树中序遍历的规则常见排序算法第六章预习检查课程目标本章概述几种常见排序算法。本章目标熟悉常见的查找算法和排序算法难点快速排序算法本章结构数据结构与算法初步常见的排序算法6.1常见的排序算法冒泡排序快速排序直接插入排序希尔排序选择排序堆排序归并排序6.1.1冒泡排序算法描述设待排序记录序列中的记录个数为n一般地，第i趟起泡排序从1到n-i+1依次比较相邻两个记录的关键字，如果发生逆序，则交换之其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上，最多作n-1趟
2、。6.1.1冒泡排序算法实例212525*16080123452125*49251649chang=10825*chang=10816chang=125*25214921251608496.1.1冒泡排序算法实例25*012345i=44916chang=108252125*i=54916chang=00825216.1.1冒泡排序算法实例210825492516214925251608214925251608214925251608214925251608214925251608初始关键字第一趟排序第四趟排序第二趟排序第三趟排序第
3、五趟排序6.1.1冒泡排序算法实现输入n个数给a[1]到a[n]forj=1ton-1fori=1ton-ja[i]>a[i+1]真假a[i]a[i+1]输出a[1]到a[n]#includemain(){inta[11],i,j,t;printf("Input10numbers:");for(i=1;i<11;i++)scanf("%d",&a[i]);printf("");for(j=1;j<=9;j++)for(i=1;i<=10-j;i++)if(a[i]>a[i+1]){t=a[i];a[i]=
4、a[i+1];a[i+1]=t;}printf("Thesortednumbers:");for(i=1;i<11;i++)printf("%d",a[i]);}6.1.2快速排序算法特点：快速排序是通过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将待排序列分成两部分一部分所有记录的关键码大于等于支点记录的关键码另一部分所有记录的关键码小于支点记录的关键码6.1.2快速排序算法描述：任取待排序记录序列中的某个记录(例如取第一个记录)作为基准(枢),按照该记录的关键字大小,将整个记录序列划分为左右两个子序列左侧子序列中
5、所有记录的关键字都小于或等于基准记录的关键字右侧子序列中所有记录的关键字都大于基准记录的关键字基准记录则排在这两个子序列中间(这也是该记录最终应安放的位置)。然后分别对这两个子序列重复施行上述方法，直到所有的记录都排在相应位置上为止。基准记录也称为枢轴（或支点）记录。取序列第一个记录为枢轴记录，其关键字为Pivotkey指针low指向序列第一个记录位置指针high指向序列最后一个记录位置6.1.2快速排序算法实例：2108254925*16始关键字08254925*162108254925*1608254925*1608254925
6、*1608254925*1621pivotkey一次交换二次交换三次交换high-1完成一趟排序lowhighlowlowlowlowlowhighhighhighhighhigh6.1.2快速排序算法实例：15254925*162108254925*162108完成一趟排序分别进行快速排序有序序列08254925*16216.1.2快速排序算法分析：快速排序是一个递归过程;利用序列第一个记录作为基准，将整个序列划分为左右两个子序列。只要是关键字小于基准记录关键字的记录都移到序列左侧；快速排序的趟数取决于递归树的高度。如果每次划分对
7、一个记录定位后,该记录的左侧子序列与右侧子序列的长度相同,则下一步将是对两个长度减半的子序列进行排序,这是最理想的情况166.1.3直接插入排序算法描述：记录存放在数组R[0….n-1]中，排序过程的某一中间时刻，R被划分成两个子区间R[0…i-1]和R[i….n-1]，其中：前一个子区间是已排好序的有序区；后一个子区间则是当前未排序的部分。基本操作将当前无序区的第1个记录R[i]插入到有序区R[0….i-1]中适当的位置，使R[0…i]变为新的有序区6.1.3直接插入排序操作细节：当插入第i(i≥1)个对象时,前面的r[0],r[
8、1],…,r[i-1]已经排好序。用r[i]的关键字与r[i-1],r[i-2],…的关键字顺序进行比较(和顺序查找类似)，如果小于，则将r[x]向后移动(插入位置后的记录向后顺移)找到插入位置即将r[i]插入6.1.3直接插入排序实
