[理学]第九讲 排序.pptVIP

排序 Sort就是：我才应该站前面 What is Sort? 概述 排序（分类）——是数据处理领域中的一种重要运算，它的功能是将一个记录的无序序列，重新排列成一个按关键字有序的序列。排序的目的之一是方便查找。 有关排序的基本概念 排序码：是排序的依据，它是数据元素中的一个或多个字段；排序码可以是关键字段，也可以不是。 排序算法的稳定性：如果待排序的序列中，存在多个具有相同排序码的数据元素，若经过排序后，这些数据元素的相对次序保持不变，则称这种排序算法是稳定的，若相对次序发生改变，则称这种排序算法是不稳定的。 内部排序和外部排序 内部排序：指对数据元素序列的整个排序过程都是在计算机内存中进行的。 外部排序：是指待排序的数据元素太多，不能同时存放在内存中，所以，排序操作不仅要使用内存，而且还要使用外部存储器存储数据。 衡量内部排序和外部排序的算法效率 内部排序：时间的主要花在数据元素的比较和移动上，可以用算法执行时的比较次数来衡量。 外部排序：时间除了花在数据元素的比较和移动上，还花在不断的读、写外部存储器上，读、写外部存储器的速度很慢，因此，外部排序的时间代价主要是用读、写外部存储器的次数来衡量。 待排记录的三种存储方式 待排序记录存放在地址连续的一组存储单元上，类似于线性表的顺序存储。记录之间的次序由存储位置决定，实现排序必须移动记录。 一组待排序记录存放在链表中，记录之间的次序关系由指针表示，实现排序不需移动记录本身，仅需修改指针（链表排序）。 待排序记录本身存放在一组地址连续的存储单元内，同时另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中这些记录的“地址”，排序结束时在按照地址向量中的值调整记录的存储位置（地址排序）。 为了简便起见，下面算法采用第一种存储方式。 简单排序算法 1、简单插入排序 2、简单选择排序 3、冒泡排序 1、简单插入排序 算法原理：把n个数据元素的序列分为两部分，（R1,…,Ri-1）为已排好序的有序部分，（Ri,Ri+1,…,Rn）为未排好序的部分。这时，把未排序的部分的第1个元素Ri依次与R1,…,Ri-1比较，并插入到有序部分的合适位置上，使得（ R1,…,Ri-1 ）变为新的有序部分。 简单插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理，此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置，须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。 算法设计： 保留 list[0]不用，从第i（i=2）个数据开始，将list[i]放在list[0]，如果list[i]list[i-1]，则从j=i-1开始递减操作，只要list[j]list[0]，都将它们后移，最后将list[0]赋给list[j+1]。 21 25 49 25* 16 08 0 1 2 3 4 5 6 21 25 49 25* 16 08 0 1 2 3 4 5 6 0 1 2 3 4 5 6 21 25 i = 2 25 初始态 0 1 2 3 4 5 6 21 25 i = 3 25 49 49 21 25 49 25* 0 1 2 3 4 5 6 0 1 2 3 4 5 6 21 25 49 25* 16 i = 5 0 1 2 3 4 5 6 21 25 49 25* 16 08 i = 6 i = 4 16 08 25* 后移 插入 后移 后移 21 25 49 25* 16 08 0 1 2 3 4 5 6 完成态 08 从以上可以看出，排序前后25都在25*之前，其相对位置没有改变，故简单插入排序是稳定的。 简单插入排序算法动画演示 void insertsort(int x[ ],int n) { int i,j,a; for(i=0;in-1;i++) { a=x[i+1]; j=i; while(j-1 a x[j]) { x[j+1]=x[j]; j--;