排序小结

数据结构 排序

一个排序算法（英语：Sorting algorithm）是一种能将一串数据依照特定排序方式进行排列的一种算法。初学排序，感觉内容繁杂，简单整理了下。

排序分类：

1. 插入排序

   • 直接插入排序
   • 折半插入排序
   • 希尔排序

2. 交换排序

   • 冒泡排序
   • 快速排序

3. 选择排序

   • 简单选择排序
   • 堆排序

4. 归并排序

   • 二路归并排序

5. 基数排序

   • 基数排序

相关概念：

稳定性、归位：

经过排序后相同元素的相对次序不发生改变，称为稳定排序（stable），反之为不稳定排序（unstable）。

eg:

排序前 B2 C1 A1 B1 A2 D1

排序后 A1 A2 B2 B1 C1 D1 稳定排序

A1 A2 B1 B2 C1 D1 不稳定排序

一个元素在整个排序结束前就放在了最终位置上称为归位（homing）。即一趟排序后，某个确定元素的位置不再发生改变。

eg:

排序前 B2 C1 A1 B1 A2 D1

一趟排序后 A1 C1 B2 B1 A2 D1

此后A1位置不再改变，归位

内、外排序：

排序时不涉及数据的内、外存交换，称为内排序（internal sort），反之为外排序（external sort）。

正、反序：

正序：待排序元素已经排好序，不需要移动。一般对应于 最好 的情况。

反序：待排序元素与所要顺序刚好完全相反，每个都需要移动。一般对应于 最坏 的情况。

时间复杂度：

较复杂的一个概念，可以先简单理解为算法的执行时间，越小越好。

一个算法的执行时间可以由其中原操作的执行次数来计量，它实际上是一种时间增长趋势分析。

eg:

for(int i = 0;j<n;i++){}//i++为基本操作，它执行了n次

时间复杂度

$$ T(n)=n=O(n) $$

另有

$$ O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!) $$

空间复杂度：

一个算法在运行过程中临时占用存储空间大小的量度

一般递归算法的空间复杂度较大。

本文由 ukuq 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jan 23, 2019 at 04:34 pm