下面给定序列上演示快速分类算法的执行步骤， 并简要说明。(17，16，18，13，15，17，12)

快速排序算法的执行步骤如下：

1. 选择一个基准元素，一般选择第一个元素。

2. 将序列中比基准元素小的元素移动到基准元素的左边，比基准元素大的元素移动到基准元素的右边。

3. 对基准元素左边和右边的子序列重复步骤 1 和步骤 2，直到每个子序列只有一个元素。

对于给定序列 (17，16，18，13，15，17，12) ，执行快速排序的过程如下：

1. 选择基准元素为 17。

2. 比 17 小的元素移到左边，比 17 大的元素移到右边，得到序列 (16，13，15，12，17，18，17)。

3. 对左侧序列 (16，13，15，12) 执行快速排序，选择基准元素为 16，得到序列 (12，13，15，16)。

4. 对右侧序列 (18，17，17) 执行快速排序，选择基准元素为 18，得到序列 (17，17，18)。

5. 左侧序列 (12，13，15，16) 和右侧序列 (17，17，18) 合并，得到最终序列 (12，13，15，16，17，17，18)。

因此，给定序列的快速排序结果为 (12，13，15，16，17，17，18)。

相关问题

、Partition 算法的作用是使用划分元素对序列进行划分，如果将算法中的语句 if i<p 改为 if i ≤p 程序的执行有何不同，分析优缺点。在下面给定序列上演示快速分类算法的执行步骤， 并简要说明。(17，16，18，13，15，17，12)

如果将算法中的语句 if i<p 改为 if i ≤p，那么划分元素在序列中的重复值也会被划分到左边的子序列中，可能会导致左右两个子序列的长度不平衡，从而影响快速排序算法的效率。

快速排序算法步骤示例：

1. 选择划分元素，本例中选择第一个元素 17。
2. 从序列左端开始，找到第一个大于划分元素的元素 16，从序列右端开始，找到第一个小于划分元素的元素 12，将它们交换位置。
3. 继续从左右两端分别寻找需要交换的元素，直到左右指针相遇，将划分元素与相遇位置的元素交换位置，完成第一轮划分。
4. 对左右两个子序列分别重复以上步骤，直到子序列长度为 1 或 0，完成排序。

划分过程示例：

1. 选择划分元素 17。
2. 左指针 i 从左端开始扫描，遇到第一个大于 17 的元素 16，停止扫描。
3. 右指针 j 从右端开始扫描，遇到第一个小于 17 的元素 12，停止扫描。
4. 交换左右指针位置的元素 16 和 12。
5. 左指针 i 继续扫描，遇到第一个大于划分元素的元素 18，停止扫描。
6. 右指针 j 继续扫描，遇到第一个小于划分元素的元素 13，停止扫描。
7. 交换左右指针位置的元素 18 和 13。
8. 左指针 i 继续扫描，遇到第一个大于划分元素的元素 15，停止扫描。
9. 右指针 j 继续扫描，遇到第一个小于划分元素的元素 17，停止扫描。
10. 左右指针相遇，将划分元素 17 与相遇位置的元素 13 交换位置，完成第一轮划分。此时序列变为：(13, 16, 12, 15, 17, 17, 18)。

1.给定关键字序列(12，13，14，15，16，17，18，19，20，21，22)，叙述采用折半查找关键字 12、28的过程，并计算平均查找长度。

好的，我来回答你的问题。

首先，折半查找也叫二分查找，它是一种高效的查找算法。在使用折半查找之前，需要先将待查找的序列按照关键字递增（或递减）的顺序排列。

对于给定的关键字序列(12，13，14，15，16，17，18，19，20，21，22)，如果我们要查找关键字12和28，具体过程如下：

1. 初始化查找范围的左右端点left和right，分别指向序列的第一个和最后一个元素。
初始时，left=0，right=10。
2. 计算中间位置mid，mid=(left+right)/2，即mid=5。
3. 比较待查找的关键字12和序列中间位置的关键字17，由于12<17，所以应该在序列的左半部分继续查找。
4. 更新右端点right，right=mid-1，此时right=4。
5. 重新计算中间位置mid，mid=(left+right)/2，即mid=2。
6. 比较待查找的关键字12和序列中间位置的关键字14，由于12>14，所以应该在序列的左半部分继续查找。
7. 更新右端点right，right=mid-1，此时right=1。
8. 重新计算中间位置mid，mid=(left+right)/2，即mid=0。
9. 比较待查找的关键字12和序列中间位置的关键字12，由于二者相等，查找成功，返回元素下标0。

对于关键字28，在第6步比较待查找的关键字12和序列中间位置的关键字14时，由于12<14，所以应该在序列的右半部分查找。更新左端点left，left=mid+1，此时left=3；重新计算中间位置mid，mid=(left+right)/2，即mid=6。在第9步比较待查找的关键字28和序列中间位置的关键字18时，由于28>18，应该在序列的右半部分继续查找。更新左端点left，left=mid+1，此时left=7；重新计算中间位置mid，mid=(left+right)/2，即mid=8。在第9步比较待查找的关键字28和序列中间位置的关键字20时，由于28<20，应该在序列的左半部分继续查找。更新右端点right，right=mid-1，此时right=7；重新计算中间位置mid，mid=(left+right)/2，即mid=7。在第9步比较待查找的关键字28和序列中间位置的关键字19时，由于28>19，应该在序列的右半部分继续查找。更新左端点left，left=mid+1，此时left=8；重新计算中间位置mid，mid=(left+right)/2，即mid=9。在第9步比较待查找的关键字28和序列中间位置的关键字21时，由于28<21，应该在序列的左半部分继续查找。更新右端点right，right=mid-1，此时right=8；重新计算中间位置mid，mid=(left+right)/2，即mid=8。此时left=right=8，查找失败。

平均查找长度ASL是指平均查找一个元素所需的比较次数，公式为ASL=(log2n+1)/2，其中n为序列长度。对于本题中的序列，n=11，所以ASL=(log2(11)+1)/2≈1.5。