各种排序算法大全ppt课件

《各种排序算法大全ppt课件》由会员分享，可在线阅读，更多相关《各种排序算法大全ppt课件（35页珍藏版）》请在装配图网上搜索。

1、6.1 常见的排序算法常见的排序算法 冒泡排序 快速排序 直接插入排序 希尔排序 选择排序 堆排序 归并排序 6.1.1 冒泡排序冒泡排序 算法描画 设待排序记录序列中的记录个数为n 普通地，第i趟起泡排序从1到n-i+1 依次比较相邻两个记录的关键字，假设发生逆序，那么交换之 其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上，最多作n-1趟。6.1.1 冒泡排序冒泡排序 算法实例0 1 2 3 4 56.1.1 冒泡排序冒泡排序 算法实例0 1 2 3 4 56.1.1 冒泡排序冒泡排序 算法实例初始关键字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序6.1.1

2、 冒泡排序冒泡排序 算法实现输入n 个数给a1 到 anfor j=1 to n-1for i=1 to n-jaiai+1真假aiai+1输出a1 到 an#include main()int a11,i,j,t;printf(Input 10 numbers:n);for(i=1;i11;i+)scanf(%d,&ai);printf(n);for(j=1;j=9;j+)for(i=1;iai+1)t=ai;ai=ai+1;ai+1=t;printf(The sorted numbers:n);for(i=1;i11;i+)printf(%d,ai);6.1.2 快速排序快速排序 算法特点

3、：快速排序是经过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将待排序列分成两部分 一部分一切记录的关键码大于等于支点记录的关键码 另一部分一切记录的关键码小于支点记录的关键码 6.1.2 快速排序快速排序 算法描画：任取待排序记录序列中的某个记录(例如取第一个记录)作为基准(枢),按照该记录的关键字大小,将整个记录序列划分为左右两个子序列 左侧子序列中一切记录的关键字都小于或等于基准记录的关键字 右侧子序列中一切记录的关键字都大于基准记录的关键字 基准记录那么排在这两个子序列中间(这也是该记录最终应安放的位置)。然后分别对这两个子序列反复施行上述方法，直到一切的记录都排在相应位置上

4、为止。基准记录也称为枢轴或支点记录。取序列第一个记录为枢轴记录，其关键字为Pivotkey 指针low指向序列第一个记录位置 指针high指向序列最后一个记录位置6.1.2 快速排序快速排序 算法实例：始关键字始关键字pivotkey一次交换一次交换二次交换二次交换三次交换三次交换high-1完成一趟排序完成一趟排序lowhighlowlowlowlowlowhighhighhighhighhigh6.1.2 快速排序快速排序 算法实例：10完成一趟排序完成一趟排序分别进展快速排序分别进展快速排序有序序列有序序列6.1.2 快速排序快速排序 算法分析：快速排序是一个递归过程;利用序列第一个记录

5、作为基准，将整个序列划分为左右两个子序列。只需是关键字小于基准记录关键字的记录都移到序列左侧；快速排序的趟数取决于递归树的高度。假设每次划分对一个记录定位后,该记录的左侧子序列与右侧子序列的长度一样,那么下一步将是对两个长度减半的子序列进展排序,这是最理想的情况 116.1.3 直接插入排序直接插入排序 算法描画：记录存放在数组R0.n-1中，排序过程的某一中间时辰，R被划分成两个子区间R0i-1和Ri.n-1，其中：前一个子区间是已排好序的有序区；后一个子区间那么是当前未排序的部分。根本操作 将当前无序区的第1个记录Ri插入到有序区R0.i-1中适当的位置，使R0i变为新的有序区 6.1.3

6、 直接插入排序直接插入排序 操作细节：当插入第i(i1)个对象时,前面的r0,r1,ri-1曾经排好序。用ri的关键字与ri-1,ri-2,的关键字顺序进展比较(和顺序查找类似)，假设小于，那么将rx向后挪动(插入位置后的记录向后顺移)找到插入位置即将ri插入6.1.3 直接插入排序直接插入排序 适用例子：知待序的一组记录的初始陈列为：21,25,49,25*,16,080 1 2 3 4 56.1.3 直接插入排序直接插入排序 适用例子：0 1 2 3 4 5 temp250 1 2 3 4 5 temp4925*0 1 2 3 4 56.1.3 直接插入排序直接插入排序 适用例子：0 1

7、2 3 4 5 temp160 1 2 3 4 5 temp080 1 2 3 4 5完成6.1.3 直接插入排序直接插入排序 算法实现：void InsertSort(int r,int n)/假设关键字为整型，放在向量假设关键字为整型，放在向量r中中 int i,j,temp;for(i=1;i0;j-)/从后向前顺序比较，并依次后移从后向前顺序比较，并依次后移 if(temp rj-1)rj=rj-1;else break;rj=temp;6.1.3 直接插入排序直接插入排序 算法分析：关键字比较次数和记录挪动次数与记录关键字的初始陈列有关。最好情况下,排序前记录已按关键字从小到大有序,

8、每趟只需与前面有序记录序列的最后一个记录比较1次,挪动2次记录,总的关键字比较次数为 n-1,记录挪动次数为 2(n-1)在平均情况下的关键字比较次数和记录挪动次数约为 n2/4。直接插入排序是一种稳定的排序方法直接插入排序最大的优点是简单，在记录数较少时，是比较好的方法6.1.4 希尔排序希尔排序 希尔排序又称减少增量排序 是1959年由D.L.Shell提出来的 算法描画 先取定一个小于n的整数d作为第一个增量，把表的全部记录分成d组 一切间隔为d1的倍数的记录放在同一组中，在各组内进展直接插入排序 然后取第二个增量d2d1 反复上述的分组和排序，直至增量d1，即一切记录放在同一组中进展直

9、接插入排序为止。6.1.4 希尔排序希尔排序 算法特点 先取定一个小于n的整数d作为第一个增量，把表的全部记录分成d组 一切间隔为d1的倍数的记录放在同一组中，在各组内进展直接插入排序 然后取第二个增量d2d1 反复上述的分组和排序，直至增量d1，即一切记录放在同一组中进展直接插入排序为止。6.1.4 希尔排序希尔排序 运用实例 先取定一个小于n的整数d作为第一个增量，把表的全部记录分成d组 一切间隔为d1的倍数的记录放在同一组中，在各组内进展直接插入排序 然后取第二个增量d2d1 反复上述的分组和排序，直至增量d1，即一切记录放在同一组中进展直接插入排序为止。6.1.4 希尔排序希尔排序 希

10、尔排序又称减少增量排序 是1959年由D.L.Shell提出来的 算法描画 首先取一个整数 gap n(待排序记录数)作为间隔,将全部记录分为 gap 个子序列,一切间隔为 gap 的记录放在同一个子序列中 在每一个子序列中分别施行直接插入排序。然后减少间隔 gap,例如取 gap=gap/2 反复上述的子序列划分和排序任务，直到最后取gap=1,将一切记录放在同一个序列中排序为止。6.1.4 希尔排序希尔排序 运用实例 知待排序的一组记录的初始陈列为：21,25,49,25*,16,080 1 2 3 4 5 6.1.4 希尔排序希尔排序 运用实例t 30 1 2 3 4 50 1 2 3

11、4 5t 2t 16.1.4 希尔排序希尔排序 算法分析 开场时 gap 的值较大,子序列中的记录较少,排序速度较快 随着排序进展,gap 值逐渐变小,子序列中记录个数逐渐变多,由于前面大多数记录已根本有序,所以排序速度依然很快 Gap的取法有多种。shell 提出取 gap=n/2，gap=gap/2，直到gap=1。6.1.5 选择排序选择排序 排序过程：排序过程：首先经过首先经过n-1次比较，从次比较，从n个数中找出最小的，个数中找出最小的，将它将它与第一个数与第一个数 交换交换第一趟选择排序，结果最小的数被安顿在第第一趟选择排序，结果最小的数被安顿在第一个元素位置上一个元素位置上 再经

12、过再经过n-2次比较，从剩余的次比较，从剩余的n-1个数中找出关键字个数中找出关键字次小的记录，次小的记录，将它与第二个数交换将它与第二个数交换第二趟选择排序第二趟选择排序 反复上述过程，共经过反复上述过程，共经过n-1趟排序后，排序终了趟排序后，排序终了6.1.5 选择排序选择排序 排序实例：排序实例：例初始：49 38 65 97 76 13 27 kji=11349一趟：13 38 65 97 76 49 27 i=22738二趟：13 27 65 97 76 49 38 三趟：13 27 38 97 76 49 65 四趟：13 27 38 49 76 97 65 五趟：13 27 3

13、8 49 65 97 76 六趟：13 27 38 49 65 76 97 kkkkjjjjjjjjjj6.1.5 选择排序选择排序 算法实例：算法实例：0 1 2 3 4 56.1.5 选择排序选择排序 算法实例：算法实例：0 1 2 3 4 5最小者最小者 25*无交换无交换最小者最小者 25无交换无交换各趟排序后的结果各趟排序后的结果6.1.5 选择排序选择排序 算法实例：算法实例：0 1 2 3 4 5i=2时选择排序的过程时选择排序的过程i k j i k j i k j 6.1.5 选择排序选择排序 算法实例：算法实例：0 1 2 3 4 5i k j 6.1.5 选择排序选择排序

14、 算法实现：算法实现：输入n 个数给a1 到 anfor i=1 to n-1for j=i+1 to najak真假k=j输出a1 到 ank=iaiaki!=k真假#include main()int a11,i,j,k,x;printf(Input 10 numbers:n);for(i=1;i11;i+)scanf(%d,&ai);printf(n);for(i=1;i10;i+)k=i;for(j=i+1;j=10;j+)if(ajak)k=j;if(i!=k)x=ai;ai=ak;ak=x;printf(The sorted numbers:n);for(i=1;i11;i+)pr

15、intf(%d,ai);阶段小节阶段小节 几种常见的排序算法 冒泡排序的特点 快速排序的特点，一趟排序的子过程本章总结本章总结数据构造与算法初步数据构造与算法初步常见的排序算法重点讲述冒泡排序和快速排序的特，同重点讲述冒泡排序和快速排序的特，同时大约了解直接插入排序，希尔排序和时大约了解直接插入排序，希尔排序和选择排序的根本思绪选择排序的根本思绪实验实验1标题标题：实现对数组265，301，751，129，937，863，742，694，076，438进展排序，用快速排序方法来实现。并列出每趟排序的结果实验目的调查快速排序算法的根本思绪 了解快速排序算法的每趟操作流程 实验分析建立一个数组，并初始化进展数据的第一趟快速排序 了解快速排序每趟操作结果，分析排序快速的最快数组类型和最慢数组类型