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

《计算机软件技术编程基础 排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、694286原序列517316942861537176749298969关键字最大的安置到最后从后往前扫描，将第N-1个纪录和前一个关键字进行比较，将小的放在前面，大的放在后面，依次类推，直到第2个记录和第1个记录交换为止。15316742869682427131526关键字最小的安置到最前面15316742869115326746893525476711325646789464523对剩余的线性表重复操作对线性表的每次来回操作都将最大的沉到表底，最小的像气泡冒到表头。115326746891132564678

3、9112345667891531674286951731694286115326746891132564678911234566789012345678910voidbub(intp[],intn){intm,k,j,i;intd;k=0;m=n-1;//初始时子表表头k和表尾m位置while(kp[i+1]){d=p[i];p[i]=p[i+1];p[i+1]=d;m=i;}j=k+1;k=0;for(

4、i=m;i>=j;i--)if(p[i-1]>p[i]){d=p[i];p[i]=p[i-1];p[i-1]=d;k=i;}}return;}待排数组数组长度while(k扫描无交换，表尾置0for(i=k;i<=j;i++)//从->扫描，子表p[m+1]沉底if(p[i]>p[i+1]){d=p[i];p[i]=p[i+1];p[i+1]=d;m=i;}//m为该趟冒泡后子表表尾的位置j=k+1;k=0;//如果<-扫描无交换，表头置0f

5、or(i=m;i>=j;i--)//从<-扫描，子表p[k-1]冒泡if(p[i-1]>p[i]){d=p[i];p[i]=p[i-1];p[i-1]=d;k=i;}//k为该趟冒泡后子表表头的位置}算法分析：稳定时间代价：需要进行比较的次数为２快速排序1）从无序表中选取一个元素T，对线性表进行分割，大于T的元素放在前表中，小于T的元素放在后表中。此时，线性表分成前后两个子表；2）对分割的两个子表再进一步分割，直到所有的子表为空为止；无序线性表≤T≥TT分割分割分割i为表头位置；k为表中位置；j为表尾位置比较大

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

7、1)，(2)，直到找到所有记录的相应位置。快速排序是一个递归的过程。快速排序算法是不稳定排序，对于有相同关键字的记录，排序后有可能颠倒位置。51731694286012345678910i=0;j=10;k=5;1731694286217316948621316978621431t=59786i=2t=52746插入排序插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。也就是说，将待序列表分成左右两部分，左边为有序表（有序序列），右边为

8、无序表（无序序列）。整个排序过程就是将右边无序表中的记录逐个插入到左边的有序表中，构成新的有序序列。根据不同的插入方法，插入排序算法主要包括：直接插入排序、折半插入排序、表插入排序和希尔排序等。本章重点介绍简单插入排序、希尔排序。简单插入法：将一个记录插入到已排好序的有序表中基本思想：将待排序表看成左右两部分，左边为有序区，右边为无序区；整个排序过程就是将右边无序区的元素插入到左边有序