各种排序算法总结(C语言版)概要.ppt

6.1.5 选择排序 算法实现： 输入n 个数给a[1] 到 a[n] for i=1 to n-1 for j=i+1 to n a[j]a[k] 真 假 k=j 输出a[1] 到 a[n] k=i a[i]?a[k] i != k 真 假 #include stdio.h main() { int a[11],i,j,k,x; printf(Input 10 numbers:\n); for(i=1;i11;i++) scanf(%d,a[i]); printf(\n); for(i=1;i10;i++) { k=i; for(j=i+1;j=10;j++) if(a[j]a[k]) k=j; if(i!=k) { x=a[i]; a[i]=a[k]; a[k]=x;} } printf(The sorted numbers:\n); for(i=1;i11;i++) printf(%d ,a[i]); } 阶段小节 几种常见的排序算法 冒泡排序的特点 快速排序的特点，一趟排序的子过程 本章总结 数据结构与算法初步 常见的排序算法 重点讲述冒泡排序和快速排序的特，同时大概了解直接插入排序，希尔排序和选择排序的基本思路 实验1 题目 题目：实现对数组{265，301，751，129，937，863，742，694，076，438}进行排序，用快速排序方法来实现。并列出每趟排序的结果 实验目的 考察快速排序算法的基本思路 了解快速排序算法的每趟操作流程 实验分析 建立一个数组，并初始化 进行数据的第一趟快速排序 了解快速排序每趟操作结果，分析排序快速的最快数组类型和最慢数组类型 冒泡排序 快速排序 直接插入排序 希尔排序 选择排序 堆排序 归并排序 6.1.1 冒泡排序 算法描述 设待排序记录序列中的记录个数为n 一般地，第i趟起泡排序从1到n-i+1 依次比较相邻两个记录的关键字，如果发生逆序，则交换之 其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上，最多作n-1趟。 6.1.1 冒泡排序 算法实例 21 25 25* 16 08 0 1 2 3 4 5 21 25* 49 25 16 49 chang=1 08 25* chang=1 08 16 chang=1 25* 25 21 49 21 25 16 08 49 6.1.1 冒泡排序 算法实例 25* 0 1 2 3 4 5 i = 4 49 16 chang=1 08 25 21 25* i = 5 49 16 chang=0 08 25 21 6.1.1 冒泡排序 算法实例 21 08 25 49 25 16 21 49 25 25 16 08 21 49 25 25 16 08 21 49 25 25 16 08 21 49 25 25 16 08 21 49 25 25 16 08 初始关键字 第一趟排序 第四趟排序 第二趟排序 第三趟排序 第五趟排序 6.1.1 冒泡排序 算法实现 输入n 个数给a[1] 到 a[n] for j=1 to n-1 for i=1 to n-j a[i]a[i+1] 真 假 a[i]?a[i+1] 输出a[1] 到 a[n] #include stdio.h main() { int a[11],i,j,t; printf(Input 10 numbers:\n); for(i=1;i11;i++) scanf(%d,a[i]); printf(\n); for(j=1;j=9;j++) for(i=1;i=10-j;i++) if(a[i]a[i+1]) {t=a[i]; a[i]=a[i+1]; a[i+1]=t;} printf(The sorted numbers:\n); for(i=1;i11;i++) printf(%d ,a[i]); } 6.1.2 快速排序 算法特点： 快速排序是通过比较关键码、交换记录， 以某个记录为界(该记录称为支点)，将待排序列分成两部分 一部分所有记录的关键码大于等于支点记录的关键码 另一部分所有记录的关键码小于支