第八章 排序

基本概念和排序方法

排序的基本概念

  1. 排序：从大到小或从小到大排序
  2. 排序的稳定性：
    • 稳定的：关键字相同的元素在排序之后相对位置不变
    • 不稳定：相反
  3. 排序算法的分类：
    • 内部排序：待排序记录全部放在计算机内存中*(关注算法时间、空间复杂度)*
    • 外部排序：数据过大，以至于内存中不能容纳全部的数据，在排序过程中，尚需对外存进行访问排序*(还要关注读取/写磁盘的次数更少)*

插入排序

算法思想︰每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

直接插入排序

是一种最简单的排序方法，其基本操作是将一条记录插入已经排好序的表，从而得到一条新的、记录数量增1的有序表

算法描述：

()

算法分析：

  • 时间复杂度：

    最好的情况：比较次数n-1次

    最坏的情况：$$O(n^2)$$

    平均时间复杂度：$$O(n^2)$$

  • 空间复杂度：$$O(1)$$

折半插入排序

时间复杂度依然是$O(n^2)$

注意：一直到low>high时才停止折半查找。当mid所指元素等于当前元素时，应继续令low=mid+1，以保证“稳定性”。最终应将当前元素插入到low所指位置(即high+1)

希尔排序

先追求表中元素部分有序，在逐渐逼近全局有序(部分有序->全局有序)

希尔排序︰先将待排序表分割成若干形如$$L[i,i + d, i + 2d…, i + kd]$$的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d(每次将d减少一半)，重复上述过程，直到d=1为止。

算法实现：

算法性能分析：

空间复杂度：$$O(1)$$

时间复杂度：$$O(n^{1.25})~O(1.6n^{1.25})$$

不稳定，仅适用于顺序表，不适用于链表

交换排序

基本思想：

两两比较待排序记录的关键字，一旦发现两个记录不满足次序要求时则进行交换，一直到整个序列全部满足要求为止

冒泡排序

算法实现：

算法性能分析：

空间复杂度：$$O(1)$$

时间复杂度：

最好：$$O(1)$$

最差：$$O(n^2)$$

快速排序

算法思想∶在待排序表$$L[1..n]$$中任取一个元素$$pivot$$作为枢轴(或基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分$$L[1…k-1]$$和$$LIk+1..n]$$，使得$$[1…k-1]$$中的所有元素小于$$pivot$$，$$L[k+1..n]$$中的所有元素大于等于$$pivot$$，则$$pivot$$放在了其最终位置$$L(k)$$上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

算法实现：

选择排序

选择排序：每一趟在待排序元素中选取关键字最小（或最大）的元素假如有序子序列

简单选择排序

空间复杂度：$$O(1)$$

时间复杂度：$$O(n^2)$$

树型选择排序

堆排序

堆的定义：n个元素的序列$${k_1,k_2,k_3,…,k_n}$$称之为堆，当且仅当满足以下条件时：

  • $$k_i>=k_2i$$且$$k_i>=k_{2i+1}$$
  • $$k_i<=k_{2i}$$且$$k_i<=k_P{2i+1}(1<=i<=\lfloor{n/2}\rfloor)$$

大根堆：根>=左右节点

小根堆：根<=左右节点

  1. 建立大根堆

归并排序

基数排序

外部排序