data structure

1. 排序的定义

排序,就是重新排列表中的元素,使表中的元素满足按关键字递增或递减的过程。为了查找方便,通常要求计算机中的表是按关键字有序的。

算法的稳定性。若待排序表中有两个元素 Ri 和 Rj ,其对应的关键字 keyi=keyj ,且在排序前 Ri 在 Rj 的前面,若使用某一排序算法排序后,Ri 仍然在 Rj 的前面,则称这个排序算法是稳定的,否则称排序算法是不稳定的。需要注意的是,算法是否具有稳定性并不能衡量一个算法的优劣,它主要是对算法的性质进行描述。

注意:对于不稳定的排序算法,只需举出一组关键字的实例,说明它的不稳定性即可。

在排序过程中,根据数据元素是否完全在内存中,可将排序算法分为两类:内部排序,是指排序期间元素全部存放在内存中的排序;外部排序,是指在排序期间元素无法全部同时存放在内存中,必须在排序的过程中根据要求不断地在内、外存之间移动的排序。

一般情况下,内部排序算法在执行过程中都要进行两种操作:比较和移动。通过比较两个关键字,确定对应元素的前后关系,然后通过移动元素以达到有序。当然,并非所有的内部排序算法都要基于比较咆哮,事实上,基数排序就不基于比较。

内部排序算法的性能取决于算法的时间复杂度和空间复杂度,而时间复杂度一般是由比较和移动的次数决定的。