快速排序-算法报告.doc
需积分: 9 91 浏览量
2021-04-14
22:43:44
上传
评论 2
收藏 327KB DOC 举报
实验 4 快速排序
1.实验目的
(1)掌握快速排序随机算法的设计思想与方法。
(2)熟练使用高级编程语言实现不同的快速排序算法。
(3)利用实验测试给出不同快速排序算法的性能以理解其优缺点。
2.实验问题
快速排序是算法导论中的经典算法。在本实验中，给定一个长为 n 的整数
数组，要求将数组升序排序。
3.实验内容
3.1 快速排序
3.1.1 快速排序的基本思想：
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要
排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的
所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排
序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中
一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录
继续进行排序，以达到整个序列有序的目的。
3.1.2 快速排序的三个步骤：
(1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 "基
准"（pivot）
(2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此
时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大。
(3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。
3.1.3 速排序的特点及性能
快速排序是在冒泡排序的基础上改进而来的，冒泡排序每次只能交换相邻
的两个元素，而快速排序是跳跃式的交换，交换的距离很大，因此总的比较和
交换次数少了很多，速度也快了不少。
但是快速排序在最坏情况下的时间复杂度和冒泡排序一样，是 O(n2)，实
评论0
最新资源