下载文档原格式
第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.希尔排序希尔排序，也称为递减增量排序算法,是插⼊排序的⼀种⾼效的改进版本。
