第八章 排序算法

 

1.排序的定义,包括内排序和外排序

  (1)排序定义:排序,就是重新排列表中的元素,使表中的元素满足按关键字排序的过程。

  (2)内排序:是指在排序期间元素全部存放在内存中的排序。

  (3)外排序:是指在排序期间元素无法全部同时存放在内存中,必须在排序的过程中根据要求不断地在内、外存之间移动的排序。

2.排序的稳定性定义

  算法的稳定性:若待排序表中有两个元素Ri和Rj,其对应的关键字相同即keyi = keyj,且在排序前Ri在Rj前面,若使用某一种排序算法后,Ri仍在Rj前面,则称这个算法是稳定的,否则称这个算法是不稳定的。

3.插入排序

  (1)直接插入排序

 

  (2)Shell排序

 

4.交换排序

  (1)冒泡排序

 

  (2)快速排序

 

5.选择排序

  (1)简单选择排序

 

  (2)堆排序

 

6.归并排序

 

7.基数排序

 

8.K路归并排序的排序过程

 

考试要求

理解内排序和外排序的区别;

掌握排序的稳定性;

对直接插入排序、冒泡排序、简单选择排序、Shell排序、快速排序、堆排序、归并排序、基数排序这些算法,掌握其在时间复杂度、空间复杂度以及是否稳定等方面的特点;

了解K路归并的外排序算法;

具有在不同的应用需求下,能够根据各种排序算法特点选择合适排序算法的能力。

上一篇:虚函数求面积


下一篇:租房项目 获取地区信息服务