排序:(一)排序算法

一、 排序算法规则

1. 内部排序与外部排序

对适合放在内存中的文件排序称为内部排序; 对磁带或磁盘上的文件排序称为外部排序; 内部排序和外部排序的区别就是内部排序很容易实现随机访问,而外部排序必须顺序访问元素;

2. 时间性与空间性

算法的时间性。 基本排序算法一般执行时间与N^2成正比。 对于复杂排序算法,很多可以达到与NLogN成正比。 但对于小规模的N或在某种特殊情况下,复杂排序算法通常比不上基本排序算法。

算法的空间性。 1.原地排序算法,不需要额外内存空间; 2.使用链表表示或指针、数组索引来引用数据,因此需要额外的内存空间存储N个指针或索引; 3.需要足够的额外空间来存储要排序的数组的副本;

3. 稳定

稳定:排序后相同关键字的相对位置保持不变,那么这个排序算法就是稳定的。 如果稳定性是必须的,我们可以通过在排序前为各关键字添加小索引或使用其它方法加长关键字,以此强制排序方法稳定。

4. 适应性

自适应排序是指排序过程依赖序列中元素之间的顺序。 而非适应性排序是指排序过程独立于序列中数据的顺序,因此排序过程只会使用比较-交换操作。 非适应性排序适合于硬件实现,但我们考虑大多数算法都是自适应的。

二、 基本排序算法

  1. 选择排序
  2. 插入排序
  3. 冒泡排序

三、 复杂排序算法

以下排序算法着重分析:

  1. Heap Sort 堆排序
  2. Quick Sort 快速排序
  3. Merge Sort 归并排序
  4. Shell Sort 希尔排序
  5. Padix Sort 基数排序

发表评论