第九章 内部排序：内部排序、外部排序的定义，各种内部排序算法的描述，包括插入排序、选择排序、归并排序、基数排序、及各种内部排序方法的比较讨论等。9.1概述:排序、内部排序、外部排序的定义，内部排序的分类。[单选题] 1.设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4 的一趟希尔排序结束后前4条记录关键字为（ ）。
9.2插入排序:插入排序的定义，直接插入排序、折半插入排序、希尔排序的算法描述及示例。
9.3快速排序与选择排序:选择排序的定义，简单选择排序算法、堆排序的算法描述，堆排序包括建堆及筛选的过程
9.4归并排序:归并排序的定义及算法描述。
9.5基数排序:基数排序的定义，多关键字的排序方法及算法描述，链式基数排序的方法及算法描述。
9.6各种内部排序方法的比较讨论:对各种排序算法的稳定性、适合情况、优缺点进行总结和比较。
9.1概述:排序、内部排序、外部排序的定义，内部排序的分类。
9.2插入排序:插入排序的定义，直接插入排序、折半插入排序、希尔排序的算法描述及示例。
9.3快速排序与选择排序:选择排序的定义，简单选择排序算法、堆排序的算法描述，堆排序包括建堆及筛选的过程
9.4归并排序:归并排序的定义及算法描述。
9.5基数排序:基数排序的定义，多关键字的排序方法及算法描述，链式基数排序的方法及算法描述。
9.6各种内部排序方法的比较讨论:对各种排序算法的稳定性、适合情况、优缺点进行总结和比较。
选项:[15，40，60，20, 45，40，15，20, 40，50，20，95, 15，20，40，45]
[单选题] 2.快速排序方法在情况下最不利于发挥其长处。( )选项:[要排序的数据已基本有序, 要排序的数据中含有多个相同值 , 要排序的数据个数为奇数 , 要排序的数据量太大。 ]
[单选题] 一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始推为（ ）。选项:[84,79,56,46,40,38, 79,46,56,38,40,80, 84,79,56,38,40,46, 84,56,79,40,46,38]
[单选题] 设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。选项:[15，25，35，50，80，20，85，40，70，36, 15，25，35，50，20，40，80，85，36，70, 15，25，35，50，80，85，20，36，40，70, 15，25，35，50，80，20，36，40，70，85]
[单选题] 试以L.r[k+1]作为监视哨改写教科书10.2.1节中给出的直接插入排序算法。其中，L.r[1..k]为待排序记录且k<MAXSIZE。
void InsertionSort ( SqList &L ) {
// 对顺序表 L 作直接插入排序。
for ( i=k-1-1; i>=1; --i )
{ if (L.r[i+1].key < L.r[i].key)
{
L.r[k+1] = L.r[i]; // 复制为监视哨
for ( j=i+1; L.r[k+1].key > L.r[j].key; ++ j )
L.r[j-1] = L.r[j]; // 记录前移
}//end if
}//end for
} // InsertSort
选项:[A.L.r[j+1] = L.r[k+1]; , L.r[i] = L.r[k+1];, L.r[j] = L.r[k+1]; , L.r[j] = L.r[k];]
[单选题]1.编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：
(1)采用顺序存储结构，至多使用一个记录的辅助存储空间；
(2)算法的时间复杂度为O(n);
void Divide(int a[ ],int n)//把数组a中所有值为负的记录调到非负的记录之前{
low=0;high=n-1;
while( )
{
while(low<high&&a[high]>=0) high--; //以0作为虚拟的枢轴记录
a[low]<->a[high];
while(low<high&&a[low]<0) low++;
a[low]<->a[high];
}
}//Divide选项:[(low+1)< high, low< =(high+1), low< high , low!=high ]
[单选题]1.编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：
(1)采用顺序存储结构，至多使用一个记录的辅助存储空间；
(2)算法的时间复杂度为O(n);
void Divide(int a[ ],int n)//把数组a中所有值为负的记录调到非负的记录之前{
low=0;high=n-1;
while( )
{
while(low<high&&a[high]>=0) high--; //以0作为虚拟的枢轴记录
a[low]<->a[high];
while(low<high&&a[low]<0) low++;
a[low]<->a[high];
}
}//Divide选项:[(low+1)< high, low!=high , low< =(high+1), low< high ]
[单选题] 1.设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4 的一趟希尔排序结束后前4条记录关键字为（ ）。
选项:[15，40，60，20, 45，40，15，20, 15，20，40，45, 40，50，20，95]
[单选题] 试以L.r[k+1]作为监视哨改写教科书10.2.1节中给出的直接插入排序算法。其中，L.r[1..k]为待排序记录且k<MAXSIZE。
void InsertionSort ( SqList &L ) {
// 对顺序表 L 作直接插入排序。
for ( i=k-1-1; i>=1; --i )
{ if (L.r[i+1].key < L.r[i].key)
{
L.r[k+1] = L.r[i]; // 复制为监视哨
for ( j=i+1; L.r[k+1].key > L.r[j].key; ++ j )
L.r[j-1] = L.r[j]; // 记录前移
}//end if
}//end for
} // InsertSort
选项:[A.L.r[j+1] = L.r[k+1]; , L.r[j] = L.r[k];, L.r[j] = L.r[k+1]; , L.r[i] = L.r[k+1];]
[单选题] 一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始推为（ ）。选项:[84,79,56,46,40,38, 84,56,79,40,46,38, 79,46,56,38,40,80, 84,79,56,38,40,46]
[单选题] 设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。选项:[15，25，35，50，80，85，20，36，40，70, 15，25，35，50，20，40，80，85，36，70, 15，25，35，50，80，20，85，40，70，36, 15，25，35，50，80，20，36，40，70，85]
[单选题] 2.快速排序方法在情况下最不利于发挥其长处。( )选项:[要排序的数据量太大。 , 要排序的数据中含有多个相同值 , 要排序的数据已基本有序, 要排序的数据个数为奇数 ]
