第十章1.排序

第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)

第十章 排序

一、单项选择题

1.有一组序列48,36,68,99,75,24,58,52进行快速排序，要求结果按从小到大排序，则进行一次划分之后结果为_____。

A. (24 28 36) 48 (52 68 75 99) B. (28 36 24) 48 (75 99 68 52)

C. (36 68 99) 48 (75 24 28 52) D. (28 36 24) 48 (99 75 68 52)

2.已知两个有序表，若要将它们组合成一个新的有序表，最好的方法是_____。

A. 希尔排序 B. 二分插入排序

C. 合并排序 D. 冒泡排序

3.排序译意风稳定的和不稳定的之分，下列四个说法中，只有______是正确的。

A. 快速排序是稳定的排序方法 B. 堆排序是不稳定的排序方法

C. 希尔排序是稳定的排序方法 D. 冒泡排序是不稳定的排序方法

4. 下列排序方法中，____方法是不稳定的。

A. 冒泡排序 B. 希尔排序 C. 冒泡排序 D. 直接插入排序

5. 下列排序方法中，在待排序的数据已经有序时，花费时间反而最多的是______。

A.快速排序 B. 希尔排序 C. 冒泡排序 D. 堆排序

6. 快速排序方法在最好情况下的时间复杂度为______。

A. O(n) B. O(n2) C. O(nlog2n) D.(log2n)

7. 下列排序方法中，时间复杂度不受数据初始状态影响，恒为O(n2)的是_______。

A. 堆排序 B.冒泡排序 C. 直接选择排序 D. 快速排序

8. 依次将待排序序列中的元素和有序子序列合并为一个新的有序子序列的排序方法是____。

A. 快速排序 B.插入排序 C. 冒泡排序 D. 堆排序

目录

第10章排序 ...................

10.2插入排序 ............

10.2.1直接插入排序

10.2.2折半插入排序

1023希尔排序…….

10.3交换排序 ............

10.3.1 冒泡排序........

10.3.2 快速排序........

10.4选择排序 ............

10.4.1简单选择排序

1Q.4.2堆排序 .......

10.5归并排序 ............

10・8实例 ............... 1081插入一值保持有序不变

10・8・2最小的K个数 ......... 2

2

2

2

3

3

3

4

4

4

5

6

7

7

第10章排序

10.2插入排序

插入排序将无序子序列中的一个或几个记录插入到有序序列中，从而减少无序子序列， 增加记录的有序子序列的长度。插入排序又可细分为直接插入排序、折半插入排序和希尔排 序。

10・2・1直接插入排序

【宜接插入排序代码】

def insert_sort(alisl):

fori in ranged Jen(alist)): for j in range(i.O.-l): if alist[j]

li=t59J 2・77・64・72,69・46・8931.9]

prinK^bcfore: Mi)

insert_sort(li)

prinK'aftcr: Ji)

【程序运行结果】

before: [59. 12. 77. 64.72、69.46. 89. 31. 9]

after: [9. 12,31.46. 59. 64.69. 72, 77. 89]

10.2.2折半插入排序

【折半插入排序代码】

def binary_sort(a):

for i in range(0. lcn(a)): index = a[i] low = 0 hight = i -1 while low <= hight: mid =

第10章 内部排序

10.1 概述

排序（Sort）：将数据元素的任意序列，重新排列成一个按关键字有序的序列。

稳定的排序方法：指如果一个待排序序列中有两个或多个关键字相同的元素，如果排序后，他们的顺序与原来的先后顺序一致，称该方法是稳定的。反之，就是不稳定的。如有序列：49、53、27、49、34中，有两个49，如果经过排序后，原来在前面的49依然在前面，称为稳定的：27、34、49、49、53.

内部排序：如果待排序的所有数据均放在内存中，则该种排序方法称为内部排序。

外部排序：如果待排序的数据只有一部分放在内存中，而别的数据都存放在外内上（如通常的硬盘上），那么这样的排序方法称为外部排序。

显然，内部排序由于所有的数据均在内存中，从而速度快，而内存的容量有限，所以一般数据量不能太大；外部排序中可以将数据放在外存上，只是将其中的一部分数据放到内存中，从而数据量可以极大（海量的），而速度显然要慢。

内部排序的方法很多，可以进行分类：

1、如果按排序的工作量区分，可以分为三类：

（1）简单的排序方法，其时间复杂度为O(n2)；

（2）先进的排序方法：时间复杂度为O(nlogn)；

（3）基数排序：时间复杂度为O(d*n)

2、如果按排序的工作原理分，可以分为：插入排序、交换排序、选择排序、归并排序和计数排序

本书约定待排序序列的数据结构如下：

#define MAXSIZE 20

typedef int KeyType; //定义关键字类型

typedef struct{

KeyType r[MAXSIZE+1]; //存放数据的数组

int length; //该数组中已经存放了多少个数据

}SqList;

SqList L; //变量L，其中已经有若干个数据

10.2 插入排序

r

length=10 L

0

49 1

53 2

27 3

36 4

74 5

49 6