【4月第四周学习记录】数据结构与算法王卓-第八章排序-交换排序（冒泡排序，快速排序）

目录

0. 交换排序是什么？

​1. 冒泡排序

伪代码

改进后的冒泡排序-伪代码

性能分析

2. 快速排序

伪代码

性能分析

3. 总结 

---

0. 交换排序是什么？

思路如下：

1. 冒泡排序

例：

设有n个元素，可见循环执行m = n-1次，每次交换 n-m 次.

伪代码

改进思路

改进后的冒泡排序-伪代码

性能分析

2. 快速排序

例：

伪代码

找中间点的函数Partition 

有关性能

需要注意，快速排序需要栈，（系统栈），不用递归也需要使用用户栈，所以空间复杂度与之前学习的算法相比较高。

 

 

性能分析

• 时间复杂度为O(nlogn)，空间复杂度为O(nlogn)，使用系统栈（递归）或用户栈（非递归）。
• 希尔排序属于非自然排序，且原序列越乱越好。因为当原始序列有序性较高时，自然排序反而退化到了原始的冒泡排序；
• 希尔排序属于不稳定排序。

3. 总结表