计算机软件技术编程基础 排序.ppt

《计算机软件技术编程基础 排序.ppt》由会员分享，可在线阅读，更多相关《计算机软件技术编程基础 排序.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基本排序技术基本排序技术排序是将一个无序序列整理成非递减顺序排列的有序序列。稳定排序：排序过程中，相同关键字的元素的相对次序不变。不稳定排序：排序过程中，相同关键字的元素的相对次序发生变化。例如：34，12，34，08，96 08，12，34，34，96 稳定 08，12，34，34，96 不稳定一一 交换排序交换排序比较两个待排序纪录的关键字，若为逆序则相互交换位置，否则，保持原来位置不变。冒泡排序、快速排序快速排序1 冒泡排序基本思想：从前往后扫描，逐个比较相邻的两个元素，发现倒序即交换直到将第N-1个纪录和第N个记录交换为止。51731694286原序列51 7316942861 53

2、7 1 7 6 74 92 9 8 9 6 9关键字最大的安置到最后从后往前扫描，将第N-1个纪录和前一个关键字进行比较，将小的放在前面，大的放在后面，依次类推，直到第2个记录和第1个记录交换为止。153167428696 82 42 71 31 52 6关键字最小的安置到最前面15316742869115326746893 5 2 54 7 6 7113256467894 64 52 3对剩余的线性表重复操作对线性表的每次来回操作都将最大的沉到表底，最小的像气泡冒到表头。1153267468911325646789112345667891531674286951731694286115326

3、746891132564678911234566789012345678910void bub(int p,int n)int m,k,j,i;int d;k=0;m=n-1;/初始时子表表头k和表尾m位置while(km)/子表未空，依次比较相邻纪录j=m-1;m=0;for(i=k;ipi+1)d=pi;pi=pi+1;pi+1=d;m=i;j=k+1;k=0;for(i=m;i=j;i-)if(pi-1pi)d=pi;pi=pi-1;pi-1=d;k=i;return;待排数组数组长度while(k扫描无交换，表尾置0for(i=k;i扫描，子表pm+1沉底 if(pipi+1)d=pi

4、;pi=pi+1;pi+1=d;m=i;/m为该趟冒泡后子表表尾的位置j=k+1;k=0;/如果=j;i-)/从pi)d=pi;pi=pi-1;pi-1=d;k=i;/k为该趟冒泡后子表表头的位置 算法分析：稳定时间代价：需要进行比较的次数为 快速排序快速排序1）从无序表中选取一个元素T，对线性表进行分割，大于T的元素放在前表中，小于T的元素放在后表中。此时，线性表分成前后两个子表；2）对分割的两个子表再进一步分割，直到所有的子表为空为止；无序线性表TTT分割分割分割i为表头位置；k 为表中位置；j为表尾位置比较大小，取中间值为分割元素t,该元素在表中的位置存放表头元素，将表头位置腾空；表尾位

5、置前移(j-)；该元素放入表头，表头位置后移(i+)；Pjt从前往后扫描，piPi=t表头位置后移(i+)；该元素放入表尾，表尾位置前移(j-)；读入表尾元素；在在一一趟趟快快速速排排序序中中，整整个个过过程程交交替替地地从从后后往往前前扫扫描描关关键键字字值值小小的的记记录录和和从从前前往往后后扫扫描描关关键键字字值值大大的的记记录录并并放放置置到到对对应应端端空空出出的的位位置置中中，又又空空出出新新的的位位置置。当当从从两两个个方方向向的的扫扫描描重重合合时，即时，即i=ji=j，就找到了基准记录的存放位置。就找到了基准记录的存放位置。按照快速排序的基本思想，在一趟快速排序之后，需要按照

6、快速排序的基本思想，在一趟快速排序之后，需要重复重复(1)(1)，(2)(2)，直到找到所有记录的相应位置。快速排序是，直到找到所有记录的相应位置。快速排序是一个递归的过程。一个递归的过程。快速排序算法是不稳定排序，对于有相同关键字的记录，排快速排序算法是不稳定排序，对于有相同关键字的记录，排序后有可能颠倒位置。序后有可能颠倒位置。51731694286012345678910i=0;j=10;k=5;1731694286217316948621316978621431t=5 9786i=2t=52746插入排序插入排序 插入排序的基本思想是：每次将一个待排序的记录，插入排序的基本思想是：每次

7、将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。也就是说，将待序列表置，直到全部记录插入完成为止。也就是说，将待序列表分成左右两部分，左边为有序表（有序序列），右边为无分成左右两部分，左边为有序表（有序序列），右边为无序表（无序序列）。整个排序过程就是将右边无序表中的序表（无序序列）。整个排序过程就是将右边无序表中的记录逐个插入到左边的有序表中，构成新的有序序列。根记录逐个插入到左边的有序表中，构成新的有序序列。根据不同的插入方法，插入排序算法主要包括：直接插入排据不同的插入方法，插入排序算法

8、主要包括：直接插入排序、折半插入排序、表插入排序和希尔排序等。本章重点序、折半插入排序、表插入排序和希尔排序等。本章重点介绍简单插入排序、希尔排序。介绍简单插入排序、希尔排序。简单插入法：将一个记录插入到已排好序的有序表中基本思想：将待排序表看成左右两部分，左边为有序区，右边为无序区；整个排序过程就是将右边无序区的元素插入到左边有序区中。（插入时，有序子表从最后一个元素开始，逐个向前与待插入元素比较）数据表a=12，5，4，9，5从小到大排序12549512495512551295412544512591294591251295void insort(T p,int n)int j,k;T t

9、;for(j=1;j=0)&(pkt)/如果有序子表的元素大于待排序元素pk+1=pk;/有序子表的元素后移k=k-1;/向前寻找有序子表的下一个比较元素pk+1=t;/待排序元素插入到有序子表 return;【例例】假假设设有有7个个待待排排序序的的记记录录，它它们们的的关关键键字字分分别别为为23，4，15，8，19，24，15，用直接插入法进行排序。，用直接插入法进行排序。【解解】简单插入排序过程如图所示。方括号简单插入排序过程如图所示。方括号 中为已排中为已排好序的记录的关键字，有两个记录的关键字都为好序的记录的关键字，有两个记录的关键字都为15，为表，为表示区别，将后一个示区别，将后

10、一个15加下划线。加下划线。简单插入排序简单插入排序 for(j=1;jn;j+)pi插入到有序表中后移、插入算法分析：由于该算法在搜索插入位置由于该算法在搜索插入位置时遇到关键字值相等的记录时就停止操时遇到关键字值相等的记录时就停止操作，不会把关键字值相等的两个数据交作，不会把关键字值相等的两个数据交换位置，所以该算法是稳定的。换位置，所以该算法是稳定的。特点：算法稳定当较小时，效果较好，但较大时，不宜采用。当原始序列越当原始序列越接近有序时，该算法的执行效率就越高。接近有序时，该算法的执行效率就越高。时间代价：需要进行比较的次数为简单插入排序的两个性质：1 在最好的情况下（序列本身已有序）

11、，时间代价为O(n)2 对于短序列，插入排序比较有效shell排序利用了插入排序的两个性质算法思想：n 先将序列转化为若干小序列，在这些小序列内进行插入排序n 逐渐扩大小序列的规模，而减少小序列个数，使得待排序序列逐渐处于更有序的状态n 最后对整个序列进行扫尾直接插入排序，从而完成排序希尔排序缩小增量排序基本步骤：取一个正整数h1=n/2,每隔步长h1取一个元素，放在一个组中，在各组中进行插入排序。71924133188218446352901234567891011h1=12/2782782191818192444244413631363315531829829h2=6/2=32 再取h2=

12、h1/2，分组排序71824135882194463312901234567891011713826371363821851931518193124844298242944h3=175813182463192982314401234567891011578131819242931446382算法分析：不稳定时间代价：与数据表的初始状态关系不大，需要循环log2n趟，每趟O(n)，时间复杂度为O(n log2n)三 选择排序算法思想:找出剩下的未排序记录中的最小记录，然后直接与数组中第i个记录交换，比冒泡排序减少了移动次数8921564885161947012345671621564885891

13、947i=1161956488589214716192148858956471619214785895648161921474889568516192147485689851619214748568589对于长度为n的序列，选择序列需要扫描n-1遍，每次扫描均从剩余的子表中找出最小的元素，然后将最小的元素与子表中的第一个元素进行交换。比较次数:(n-1)+(n-2)+2+1=n(n-1)/2交换次数：n-1时间复杂度O(n2)四 归并排序基本思想：将两个或两个以上的有序表合并成一个新的有序表。步骤：将整个表看成个有序子表，每个子表长度为；两两归并，得到长度为的个子表；再两两归并，一直得到长度为

14、的有序表为止；(19)(13)(05)(27)(01)(26)(31)(16)(13,19)(05,27)(01,26)(16,31)(05,13,19,27)(01,16,26,31)(05,13,19,27)(01,16,26,31)i=1j=5如果L(i)L(j),A(K)=L(j);j+1,k+1LAk如果i或j已指到子表子表的表尾,则将另一子表的剩余部分复制到A表中(05,13,19,27)(01,16,26,31)i=1j=5LAk1234567801i=1；j=5ki=1；j=60105i=2；j=6Ki=3；j=6010513Ki=3；j=7Ki=4；j=70105131601

15、05131619 K010513161926Ki=4；j=80105131619262701051316192627313.4 二叉排序树及其查找一 二叉排序树及其构造1 二叉排序树的定义 左子树结点值=根结点 左右子树也满足上述条件13111615273132568二叉排序树的构造一棵二叉排序树b中插入一个结点*s(1)若b为空树，则将*s作为根结点插入(2)(2)若b不为空树，则(3)s-data data =b的父结点的值，*s插入到b的右子树中80 82 85 75 82 68 71 77 8875828085826871778856783445854536918478构造二叉排序树3

16、4845685783645459178如何定义结点？如何定义结点？struct bsnodeint d;bsnode*lchild,*rchild;bsnode*insert_bs_tree(bsnode*bt,int x)二叉排序树的插入 insert_bs_tree()传入的形参：根结点，插入元素insert_bs_tree(bsnode*bt,int x)返回值：根结点bsnode*insert_bs_tree(bsnode*bt,int x)bsnode*p,*q;定义两个结点构造一个新结点p=new(bsnode);p-d=x;p-lchild=NULL;p-rchild=NULL;

17、建立一个搜索指针，从根结点开始搜索q=bt;如果二叉排序树为空，将新结点作为根结点if(bt=NULL)bt=p;如果二叉排序树不为空，将新结点插入到二叉树中elsewhile(q-lchild!=p)&(q-rchild!=p)判断新结点是否插入到二叉树中if(xd)if(q-lchild!=NULL)q=q-lchild;else q-lchild=p;如果插入值小于搜索结点q的值1搜索结点q的左子树的结点已存在2搜索结点q的左子树为空如果插入值大于搜索结点q的值1搜索结点q的右子树的结点已存在2搜索结点q的右子树为空else if(q-rchild!=NULL)q=q-rchild;else q-rchild=p;return bt;返回根结点二叉排序树的查找从二叉排序树的根结点开始与被查值进行比较，若等于根结点，则查找结束根结点，到右子树查找；void intrav(bsnode*bt)if(bt!=NULL)intrav(bt-lchild);coutdrchild);return;二叉排序树的查找效率接近对分查找