数据结构-基于C++语言（微课版） 课件 1-2 快速排序

快速排序的概念；快速排序的基本思想；本节目录：本节内容：快速排序快速排序快速排序的算法描述；交换排序冒泡排序快速排序概念任意选取一个关键字，以该关键字为基准值，将待排序关键字分割成独立的两个部分。其中前一部分关键字的关键值都不大于基准值，后一部分的关键字值都大于或等于基准值；这就是一趟快速排序。快速排序结果1：

223442456678结果2：342242786645例

422245346678

关键字：

123456给定如下6个关键字，以首关键字42为基准值，一趟快速排序分割的结果。快速排序过程从序列的两端交替扫描各个关键字，找到一大一小两个关键字，交换两个关键字。快速排序关键字：45236080504023

3055

12345768

91、从右向左扫描：查找到一个小于基准值的关键字（小关键字）；2、从左向右扫描：查找到一个不小于基准值的关键字（大关键字）；0基准值大关键字小关键字快速排序过程从序列的两端交替扫描各个关键字，找到一大一小两个关键字，交换两个关键字。快速排序关键字：236080504023

3055

12345768

91、从右向左扫描：查找到一个小于基准值的关键字（小关键字）；2、从左向右扫描：查找到一个不小于基准值的关键字（大关键字）；0基准值大关键字小关键字45快速排序过程从序列的两端交替扫描各个关键字，找到一大一小两个关键字，交换两个关键字。快速排序关键字：236080504023

3055

12345768

91、从右向左扫描：查找到一个小于基准值的关键字（小关键字）；2、从左向右扫描：查找到一个不小于基准值的关键字（大关键字）；0基准值大关键字小关键字45快速排序过程从序列的两端交替扫描各个关键字，找到一大一小两个关键字，交换两个关键字。快速排序关键字：23608050402355

12345768

91、从右向左扫描：查找到一个小于基准值的关键字（小关键字）；2、从左向右扫描：查找到一个不小于基准值的关键字（大关键字）；0基准值大关键字小关键字4530快速排序过程从序列的两端交替扫描各个关键字，找到一大一小两个关键字，交换两个关键字。快速排序关键字：23608050402355

12345768

91、从右向左扫描：查找到一个小于基准值的关键字（小关键字）；2、从左向右扫描：查找到一个不小于基准值的关键字（大关键字）；0基准值大关键字小关键字4530快速排序过程从序列的两端交替扫描各个关键字，找到一大一小两个关键字，交换两个关键字。快速排序关键字：238050402355

12345768

91、从右向左扫描：查找到一个小于基准值的关键字（小关键字）；2、从左向右扫描：查找到一个不小于基准值的关键字（大关键字）；0基准值大关键字小关键字453060快速排序过程从序列的两端交替扫描各个关键字，找到一大一小两个关键字，交换两个关键字。快速排序关键字：2380405055

12345768

91、从右向左扫描：查找到一个小于基准值的关键字（小关键字）；2、从左向右扫描：查找到一个不小于基准值的关键字（大关键字）；0基准值大关键字小关键字45306023快速排序过程从序列的两端交替扫描各个关键字，找到一大一小两个关键字，交换两个关键字。快速排序关键字：23405055

12345768

91、从右向左扫描：查找到一个小于基准值的关键字（小关键字）；2、从左向右扫描：查找到一个不小于基准值的关键字（大关键字）；0基准值大关键字小关键字4530602380快速排序过程从序列的两端交替扫描各个关键字，找到一大一小两个关键字，交换两个关键字。快速排序关键字：234050

55

12345768

91、从右向左扫描：查找到一个小于基准值的关键字（小关键字）；2、从左向右扫描：查找到一个不小于基准值的关键字（大关键字）；0基准值大关键字小关键字4530602380快速排序过程从序列的两端交替扫描各个关键字，找到一大一小两个关键字，交换两个关键字。快速排序关键字：2350

55

12345768

91、从右向左扫描：查找到一个小于基准值的关键字（小关键字）；2、从左向右扫描：查找到一个不小于基准值的关键字（大关键字）；0基准值大关键字小关键字453060238040快速排序过程从序列的两端交替扫描各个关键字，找到一大一小两个关键字，交换两个关键字。快速排序关键字：2350

55

12345768

91、从右向左扫描：查找到一个小于基准值的关键字（小关键字）；2、从左向右扫描：查找到一个不小于基准值的关键字（大关键字）；0基准值大关键字小关键字453060238040快速排序算法描述1、设两个变量i,j,初始时i=low=1，j=high=n，以a[low]为基准元素，将a[low]零时保存在a[0]中。快速排序2、比较和交换从j所指位置向前搜索：将a[j]与a[0]进行比较：从i所指位置起向后搜索：将a[0]与a[i]进行比较：3、重复1、2步骤，直到i=j为止，同