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路归并的外排序算法;
具有在不同的应用需求下,能够根据各种排序算法特点选择合适排序算法的能力。