数据结构笔记10: 排序与查找

数据结构笔记10: 排序与查找 排序算法 归并排序

• 思想：分而治之

自然归并排序

• 如果局部序列天然有序，则不进行分解

快速排序 思想：分而治之

• 任意选取一个元素，排序后，所有比它小的都在它的前面，所有比它大的都在它的后面
• 用同样的方法，对该元素的前后子序列进行排序

Petition算法

• 选取一个元素，以序列头元素为例，作为中轴
• 序列头有一个从左向右扫描的指针i，序列尾有一个从右向左扫描的指针j
• 双向扫描，直到i遇到比中轴大的元素，j遇到比中轴小的元素，交换两个元素
• 继续扫描，直到 i > j ，把中轴与A[j]交换

缺陷

• 当序列本身有序时，性能会退化到
• 当子序列较短的时候，例如只有三个数，再使用快速排序，增加两个指针，过于麻烦

改进

• 增加选择的随机性，让中轴不至于一直是序列中最小或最大的数
• 当子序列已经比较短时，不继续使用快速排序，而是调用简单的排序算法

希尔排序

• 选取一定的间隔，如5，将第1、6、11，第2、7、12，......，每组元素分别排序
• 缩短间隔，按照同样的方法重新排序
• 当间隔较短时，使用插入排序即可

排序算法的分析与比较 查找算法