算法分析

时间复杂度

平均计算时间是O(nlog_2 n)。

• Qsort(): O(log_2 n)
• Partition(): O(n)

实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。

空间复杂度

快速排序不是原地排序

由于程序中使用了递归，需要递归调用栈的支持，而栈的长度取决于递归调用的深度。（即使不用递归，也需要用用户栈）

• 在平均情况下：需要**O(logn)**的栈空间
• 最坏情况下：栈空间可达O(n)。

稳定性

快速排序是一种不稳定的排序方法

自然性

快速排序不适于对原本有序或基本有序的记录序列进行排序。

划分元素的选取是影响时间性能的关键

输入数据次序越乱，所选划分元素值的随机性越好，排序速度越快，快速排序不是自然排序方法

改变划分元素的选取方法，至多只能改变算法平均情况下的时间性能，无法改变最坏情况下的时间性能。即最坏情况下，快速排序的时间复杂性总是O(n^2)

选择排序

简单选择排序

**基本思想：**在待排序的数据中选出最大（小）的元素放在其最终的位置。

基本操作：

1. 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换
2. 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换
3. 重复上述操作，共进行n-1趟排序后，排序结束

void SelectSort(SqList &K){for(i=1;ik=i;for(j=i+1;j<=L.length;j++)if(L.r[j].keyL.r[k];//交换}
}

时间复杂度

• 记录移动次数

  • 最好情况：0
  • 最坏情况：3(n-1)

• 比较次数：无论待排序列处于什么状态，选择排序所需进行的“比较”次数都相同
  ∑i=1n−1(n−i)=n2(n−1)\sum_{i=1}^{n-1}(n-i)=\frac{n}{2}(n-1) i=1∑n−1​(n−i)=2n​(n−1)

稳定性

• 简单选择排序是不稳定排序

堆排序

堆的定义：
若n个元素的序列{a1,a2,...,an}满足{ai≤a2iai≤a2i+1或{ai≥a2iai≥a2i+1则分别称该序列{a1,a2,...,an}为小根堆和大根堆若n个元素的序列\{a_1,a_2,...,a_n\}满足\\ \begin{cases} a_i≤a_{2i} \\ a_i≤a_{2i+1} \end{cases} \quad 或 \begin{cases} a_i≥a_{2i} \\ a_i≥a_{2i+1} \end{cases}\\ 则分别称该序列\{a_1,a_2,...,a_n\}为小根堆和大根堆 若n个元素的序列{a1​,a2​,...,an​}满足{ai​≤a2i​ai​≤a2i+1​​或{ai​≥a2i​ai​≥a2i+1​​则分别称该序列{a1​,a2​,...,an​}为小根堆和大根堆
从堆的定义可以看出，堆实质是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于（大于）它的孩子结点

若在输出堆顶的最小值（最大值）后，使得剩余n-1个元素的序列重新建成一个堆，则得到n个元素的次小值（次大值）…如此反复，便能得到一个有序序列，这个过程称之为堆排序。

堆的调整

小根堆：

1. 输出堆顶元素之后，以堆中最后一个元素替代之；
2. 然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；
3. 重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”

void HeapAdjust(elem R[],int s,int m){/*已知R[s...m]中记录的关键字除R[s]之外均满足堆的定义，本函数调整R[s]的关键字，使R[s...m]成为一个大根堆*/rc=R[s];for(j=2*s;j<=m;j*=2){//沿key较大的孩子结点向下筛选if(j=R[j])break;R[s]=R[j];	s=j;//rc应插入在位置s上}R[s]=rc;//插入
}

堆的建立

单结点的二叉树是堆；

在完全二叉树中所有以叶子结点（序号i>n/2）为根的子树是堆。

这样，我们只需依次将以序号为n/2,n/2-1,…,1的结点为根的子树均调整为堆即可。

将初始无序的R[1]到R[n]建成一个小根堆，可用以下语句实现：

for(i=n/2;i>=1;i--)HeapAdjust(R,i,n);

由以上分析知：

若对一个无序序列减建堆，然后输出根；重复该过程就可以由一个无序序列输出有序序列。

实质上，堆排序就是利用完全二叉树中父结点与孩子结点之间的内在关系来排序的。

void HeapSort(elem R[]){int i;for(i=n/2;i>=1;i--)HeapAdjust(R,i,n);//建初始堆for(i=n;i>1;i--){//进行n-1趟排序Swap(R[1],R[i]);//根与最后一个元素交换HeapAdjust(R,1,i-1);//对R[1]到R[i-1]重新建堆}
}

算法性能分析

• 初始堆化所需时间不超过O(n)
• 排序阶段（不含初始堆化）
  • 一次重新堆化所需时间不超过O(logn)
  • n-1次循环所需时间不超过O(nlogn)

Tw(n)=O(n)+O(nlogn)=O(nlogn)

堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复筛选上。堆排序在最坏情况下，其时间复杂度也为O(nlog_2 n)，这是堆排序的最大优点。无论待排序列中的记录是正序还是逆序排列，都不会使堆排序处于”最好“或”最坏“的状态。

另外，堆排序仅需一个记录大小供交换用的辅助存储空间。

然而堆排序是一种不稳定的排序方法，它不适用于待排序记录个数n较少的情况，但对于n较大的文件还是很有效的。

归并排序

基本思想：将两个或两个以上的有序子序列”归并“为一个有序序列。

在内部排序中，通常采用的是2-路归并排序。

即：将两个位置相邻的有序子序列R[l…m]和R[m+1…n]归并为一个有序序列R[l…n]

算法分析

• 时间效率：O(nlog2n)

• 空间效率：O(n)

  因为需要一个与原始序列同样大小的辅助序列（R1）。这正是此算法的缺点。

• 稳定性：稳定

基数排序

基本思想：分配+收集

也叫桶排序或箱排序：设置若干个箱子，将关键字为k的记录放入第k个箱子，然后在按序号将非空的连接。

基数排序：数字是有范围的，均由0-9这十个数字组成，则只需设置十个箱子，相继按个、十、百…进行排序。

算法分析

• 时间效率：O(k * (n+m))

  k：关键字个数，

  m：关键字取值范围为m个值

• 空间效率：O(n+m)

• 稳定性：稳定

各种排序方法的综合比较

1. 时间性能

   1. 按平均的时间性能来分，有三类排序方法：

      • 时间复杂度为O(nlogn)的方法有：

        快速排序、堆排序和归并排序，其中以快速排序为最好；

      • 时间复杂度为O(n^2)的方法有：

        直接插入排序、冒泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此；

      • 时间复杂度为O(n)的方法只有：基数排序。

   2. 当待排记录序列按关键字顺序有序时，直接插入排序和冒泡排序能达到O(n)的时间复杂度；而对于快速排序而言，这是最不好的情况，此时的时间性能退化为O(n^2)，因此是应该尽量避免的情况。

   3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。

2. 空间性能

   指的是排序过程中所需的辅助空间大小

   1. 所有的简单排序方法（包括：直接插入、冒泡和简单选择）和堆排序的空间复杂度为O(1)
   2. 快速排序为O(logn)，为栈所需的辅助空间
   3. 归并排序所需辅助空间最多，其空间复杂度为O(n)
   4. 链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)

3. 排序方法的稳定性能

   • 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。
   • 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。
   • 对于不稳定的排序方法，只要能举出一个实例说明即可。
   • 快速排序和堆排序是不稳定的排序方法。

4. 关于“排序方法的时间复杂度的下限”

   • 除基数排序外，其它方法都是基于”比较关键字“进行排序的排序方法，可以证明，这类排序法可能达到的最快时间复杂度为O(nlogn)。

     （基数排序不是基于”比较关键字“的排序方法，所以它不受这个限制）。

   • 可以用一棵判定树来描述这类基于”比较关键字“进行排序的排序方法。