排序小结

in 数据结构 with 1 comment

一个排序算法(英语: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!) $$

空间复杂度:

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

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

Responses
  1. study 一起学习 go

    Reply