• 折半查找比顺序査找在时间复杂度上要好得多。
• 折半查找比顺序查找效率高,但折半查找要求被査找的数据有序。
• 为提高数据的査找速度,需要对数据排序

9.1排序的基本概念

• 和上一章相同,假定被排序的数据是由一组元素组成的表或文件,
• 元素则由若干个数据项组成,
• 有一项可用来标识一个元素,称关键字项,
  • 值称关键字。
• 关键字可用作排序运算的依据

1.什么是排序

• 本章仅讨论递增排序,默认排序均指递增
• 输入:m个元素,R、R1、…、R1,相应关键字为ん。、k、…、kn1。
• 输出:R,R,…,R,使得k。≤k≤…≤k

2.内排序和外排序

• 在排序过程中,若整个表都放在内存中处理,排序时不涉及数据的内、外存交换,则称为内排序;
• 反之,若排序过程中要进行数据的内、外存交换,则称为外排序。
• 内排序适用于元素个数不很多的小表,外排序则适用于元素个数很多,不能一次将其全部元素放入内存的大表。内排序是外排序的基础。本章只讨论内排序。

3 内排序的分类

• 插排、交换排序、选择排序和归并排序都是基于比较的排序算
  法;
• 而基数排序是不基于比较的排序算法

4.基于比较的排序算法的性能

何热

9.4选择排序

• 每一趟从待排序的元素中选出关键字最小的元素,顺序放在已排好序的子表的最后,直到全部元素排序完毕。
• 由于选择排序方法每一趟总是从无序区中选出全局最小(或最大)的关键字,所以适合从大量的元素中选择一部分排序元素。
• 从10000个元素中选择出关键字大小为前10位的元素,就适合采用选择排序方法
• 介绍两种选择排序方法:简单选择排序(或称直接选择排序)和堆排序

9.4.1简单选择排序

1.排序思路

• 第$i$i趟时,
  • 有序区和无序区为
  • $R[O...i-1]$R[O...i−1]和$R[i...n-1]$R[i...n−1]$(0≤i<n-1)$(0≤i<n−1)
• 从当前无序区中选出关键字最小的$R[k]$R[k]
  • 与无序区第1个元素R[i]交换
  • 使$R[O...i一1]$R[O...i一1]和$R[i...n-1]$R[i...n−1]变为新的有序区和新的无序区
  • 如图9.16。

 

• 每趟产生的有序区一定是全局有序区。
• 每趟产生的有序区中的所有元素都归位了。

 

2.排序算法

 

• 每趟选择出一个元素(带方框者)。

3.算法分析

• 无论初始数据序列的状态如何,在第图9.1710个元素进行简单选择排序的过程i趟排序中选出最小关键字的元素,内for循环需做nー1ー(i+1)+1=nーi-1次比较,因
  此,总的比较次数为:
  一2
  C(n)
  (n-i+1)

 

• 当初始顺序表为正序时,移动次数为0;
• 反序时,每趟排序均要执行交换,所以总的移动次数取最大值3(n-1)
• 无论元素的初始排列如何,关键字比较相同,均为
• 因此,算法最好情况、最坏情况和平均时间复杂度均为O(n2)。

 

• 只用4个辅助变量,
• 算空间复杂度为O(1)。
• 就地排序

 

• 不稳定的排序方法。
• {5,3,2,5,4,1,8,7},
• 第1趟排序时,选择出最小关键字1,
• 将其与第1个位置上的元素交换,从中看到两个5的相对位置发生了改变。