下载文档原格式
第10章排序10.1 知识点分析1．排序基本概念：（1）排序将数据元素的任意序列，重新排列成一个按关键字有序（递增或递减）的序列的过程称为排序。
（2）排序方法的稳定和不稳定若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对原先具有相同键值元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳定的。
（3）内排序整个排序过程都在内存进行的排序称为内排序，本书仅讨论内排序。
（4）外排序待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。
2．直接插入排序直接插入排序法是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。
3．二分插入排序二分插入排序法是用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入的排序方法。
4．希尔排序希尔排序的基本思想是：先选取一个小于n的整数d1作为第一个增量，把待排序的数据分成d1个组，所有距离为d1的倍数的记录放在同一个组内，在各组内进行直接插入排序，每一趟排序会使数据更接近于有序。
然后，取第二个增量d2，d2< d1，重复进行上述分组和排序，直至所取的增量d i=1（其中d i< d i-1 < ……< d2< d1），即所有记录在同一组进行直接插入排序后为止。
5．冒泡排序冒泡法是指每相邻两个记录关键字比大小，大的记录往下沉（也可以小的往上浮）。
每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束。
6．快速排序快速排序法是通过一趟排序，将待排序的记录组分割成独立的两部分，其中前一部分记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比枢轴记录的关键字大，枢轴记录得到了它在整个序列中的最终位置并被存放好。
第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且它们又分别分割出独立的两个子序列……。
第10章排序一、选择题1．某内排序方法的稳定性是指( D )。
【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法 D．以上都不对2．下面给出的四种排序法中( D )排序法是不稳定性排序法。
【北京航空航天大学 1999 一、10 （2分）】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积3．下列排序算法中，其中（D ）是稳定的。
【福州大学 1998 一、3 (2分)】A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序4．稳定的排序方法是（ B ）【北方交通大学 2000 二、3（2分）】A．直接插入排序和快速排序 B．折半插入排序和起泡排序C．简单选择排序和四路归并排序 D．树形选择排序和shell排序5．下列排序方法中，哪一个是稳定的排序方法？（ B ）【北方交通大学 2001 一、8（2分）】A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6. 快速排序方法在（ D ）情况下最不利于发挥其长处。
【燕山大学 2001 一、3 （2分）】A. 要排序的数据量太大B. 要排序的数据中含有多个相同值C. 要排序的数据个数为奇数D. 要排序的数据已基本有序7. 以下序列不是堆的是( D )。
【西安电子科技大学 2001应用一、5 （2分）】A. (100,85,98,77,80,60,82,40,20,10,66)B. (100,98,85,82,80,77,66,60,40,20,10)C. (10,20,40,60,66,77,80,82,85,98,100)D. (100,85,40,77,80,60,66,98,82,10,20)8．下列四个序列中，哪一个是堆（ C ）。
【北京工商大学 2001 一、8 （3分）】A. 75,65,30,15,25,45,20,10B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10D. 75,45,65,10,25,30,20,159．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。
c++⼏种基本的插⼊排序（图⽂）1.插⼊排序插⼊排序（Insertion Sort）是⼀种简单直观的排序算法。
它的⼯作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插⼊。
插⼊排序在实现上，通常采⽤in-place排序（即只需⽤到O(1)的额外空间的排序），因⽽在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插⼊空间。
时间复杂度:O(n^2);算法描述：1.从第⼀个元素开始，该元素可以认为已经被排序2.取出下⼀个元素，在已经排序的元素序列中从后向前扫描3.如果该元素（已排序）⼤于新元素，将该元素移到下⼀位置4.重复步骤3，直到找到已排序的元素⼩于或者等于新元素的位置5.将新元素插⼊到该位置后6.重复步骤2~5动画演⽰：作者：Swfung8算法演⽰：/***直接插⼊排序*/void InsertSort(int a[], int len){int i, j, key;for(i = 1; i < len; ++i){key = a[i];for(j = i-1; j >=0; --j){if(a[j] > key)a[j+1] = a[j];elsebreak;}a[j+1] = key;}}2.折半插⼊排序折半插⼊排序（binary insertion sort）是对插⼊排序算法的⼀种改进，所谓排序算法过程，就是不断的依次将元素插⼊前⾯已排好序的序列中。
时间复杂度O(n^2);算法描述：在将⼀个新元素插⼊已排好序的数组的过程中，寻找插⼊点时，将待插⼊区域的⾸元素设置为a[low]，末元素设置为a[high]，则轮⽐较时将待插⼊元素与a[m]，其中m=(low+high)/2相⽐较,如果⽐参考元素⼤，则选择a[low]到a[m-1]为新的插⼊区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插⼊区域（即low=m+1），如此直⾄low<=high不成⽴，即将此位置之后所有元素后移⼀位，并将新元素插⼊a[high+1]算法演⽰：/***折半插⼊排序*/void BinsertSort(int a[], int len){int i, j;int low, high, mid;int key;for(i = 1; i < len; i++){key = a[i];low = 1; high = i-1;while (low <= high){mid = (low+high)/2;if(key < a[mid])high = mid-1;elselow = mid+1;}for(j = i-1; j >=high+1; --j)a[j+1] = a[j];a[high+1] = key;}}3.希尔排序希尔排序，也称为递减增量排序算法,是插⼊排序的⼀种⾼效的改进版本。
第10章内部排序一、选择题（每小题1分，共10分）1.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后放在已排序序列的合适位置，该排序方法称为（ A ）排序法。
A.插入排序B.选择排序C.希尔排序D.二路归并排序2.下列排序算法中( C )排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A.选择B.冒泡C.归并D.堆3.若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。
A. 38, 40, 46, 56, 79, 84B. 40, 38, 46, 79, 56, 84C. 40, 38，46, 56, 79, 84D. 40, 38, 46, 84, 56, 794.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ C ）。
A.希尔排序B.冒泡排序C.插入排序D.选择排序5.为实现快速排序算法，待排序序列宜采用的存储方式是（ A ）。
A. 顺序存储B. 散列存储C. 链式存储D. 索引存储6.若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为（ B ）。
A. 79, 46, 56, 38, 40, 84B. 84, 79, 56, 38, 40, 46C. 84, 79, 56, 46, 40, 38D. 84, 56, 79, 40, 46, 387．排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ C ）。
A．希尔排序B．冒泡排序C．插入排序D．选择排序8．在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ D ）。
A．希尔排序B．冒泡排序C．直接插入排序D．直接选择排序9．堆是一种有用的数据结构。
折半插入排序
折半插入排序法，又称四舍五入排序法。
是按照折半法和插入法交替进行逐步排除错误的一种方法，也叫“舍弃小的，保留大的”或“用全排出去，用缺补上来”排序法.它适合于成对象形的数据，也就是说要求将某些对象先看作一组，然后再把它们每一对当作两个来排列，这样容易产生正确的结果。
常见的排序问题，通常包含多对对象，而且要求所选择的对象都必须有相同的特征值。
由于相邻的两个单元可能互为相反数，故在实际操作过程中往往需要将两者按互为倒数来处理，这就引申出一系列简便计算，即求整数部分的个位数字，因此排序也是很容易解决的。
下面举例说明其思路和方法。
例如有10名学生参加考试，前8人平均成绩为80分，最后2人平均成绩为90分，则求出平均成绩为81分的2人平均成绩的值。
应用该方法时要注意以下几点：1、运算符号、公式及各种运算之间不能混淆；2、在用这种方法时还需进一步分析原来顺序中有无矛盾，是否具备等价性（平均成绩相等），排除非同质的现象（比如全为80分，或全为90分）；3、用该方法解决的问题，只要求得到最终结果，不要求知道开始时的情况，但要求知道结束时的情况。
在用这种方法时还需进一步分析原来顺序中有无矛盾，是否具备等价性（平均成绩相等），排除非同质的现象（比如全为80分，或全为90分）。
3、使用了这种方法后，若遇到不能直接利用上述方法解决的问
题，可采取折半插入排序法。
例如，已知某班男女生人数分别为20人和21人，求男生人数占总人数的百分比。
4、用该方法解决的问题，只要求得到最终结果，不要求知道开始时的情况，但要求知道结束时的情况。
详解排序算法（⼀）之3种插⼊排序（直接插⼊、折半插⼊、希尔）直接插⼊排序打过牌的⼈都知道，当我们拿到⼀张新牌时，因为之前的牌已经经过排序，因此，我们只需将当前这张牌插⼊到合适的位置即可。
⽽直接插⼊排序，正是秉承这⼀思想，将待插⼊元素与之前元素⼀⼀⽐较，从⽽找到合适的插⼊位置。
那么使⽤直接插⼊排序，具体是怎样操作的呢？我们取 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 来进⾏⽰范。
（1）第1轮排序，3之前⽆可⽐较值，因此我们从44开始操作，取44和3⽐较，⼤于3，顺序保持不变。
得数据3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48（2）第2轮排序，取38和44⽐较，38 < 44，再将38与3⽐较，38 > 3，故将38放于第2位，得数据3, 38, 44, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48（3）第3轮排序，取5与44⽐较，5 < 44，再将5与38⽐较，5 < 38，再将5与3⽐较，5 > 3, 置于第2位，得数据3, 5, 38, 44, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48（4）如此经过14轮排序后，得到最终结果2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50动态图javascript实现function directInsertSort (arr) {let compare, // 对⽐元素下标current // 待插⼊元素值for (let i = 1; i < arr.length; i++) {current = arr[i]compare = i - 1while (current < arr[compare] && compare >= 0) {arr[compare + 1] = arr[compare]compare--}arr[compare + 1] = current}return arr}折半插⼊排序细⼼的同学可能已经注意到，当我们要将⼀个元素插⼊合适的位置时，其之前的元素是有序的，因此，我们可以⽤折半查找的⽅式来⽐对并插⼊元素，也就是所谓的折半插⼊排序。
