关于快速选择排序程序第一趟划分流程分析

关于快速选择排序程序第一趟划分流程分析

题目1：{28，16，32，12，60，2，5，72}选择28作为基准第一趟划分分析

下面详细分析数组 {28, 16, 32, 12, 60, 2, 5, 72} 以 28 作为基准进行第一趟划分的过程。
初始状态

1. [28, 16, 32, 12, 60, 2, 5, 72]

复制代码

• 选择第一个元素 28 作为基准元素。
  
• 初始化指针：
  
  
  
  • left 指针从 low + 1 即索引 1 开始，初始指向元素 16。
    
  • right 指针从 high 即索引 7 开始，初始指向元素 72。
    
  
  

指针移动与元素交换步骤

第一轮移动与交换

• left 指针移动：left 指向 16，由于 16 < 28，left 指针继承向右移动，指向 32。此时 32 > 28，left 指针停止移动。
  
• right 指针移动：right 指向 72，由于 72 > 28，right 指针继承向左移动，指向 5。此时 5 < 28，right 指针停止移动。
  
• 元素交换：此时 left 指向 32，right 指向 5，交换这两个元素，数组变为 [28, 16, 5, 12, 60, 2, 32, 72]。
  

第二轮移动与交换

• left 指针移动：left 继承右移，指向 12，由于 12 < 28，继承右移指向 60，60 > 28，left 指针停止移动。
  
• right 指针移动：right 继承左移，指向 2，由于 2 < 28，right 指针停止移动。
  
• 元素交换：此时 left 指向 60，right 指向 2，交换这两个元素，数组变为 [28, 16, 5, 12, 2, 60, 32, 72]。
  

指针相遇

• left 指针移动：left 继承右移。
  
• right 指针移动：right 继承左移。当 left > right 时，指针相遇，此时 right 指向的元素是 2，left 指向的元素是 60，分区过程结束。
  

放置基准元素

将基准元素 28 与 right 指针所指的元素 2 交换位置，数组变为 [2, 16, 5, 12, 28, 60, 32, 72]。
结果分析

经过第一趟划分后，基准元素 28 已经处于其最终排序的位置，左边的子数组 [2, 16, 5, 12] 中的所有元素都小于 28，右边的子数组 [60, 32, 72] 中的所有元素都大于 28。接下来就可以递归地对左右子数组分别进行快速排序，以完成整个数组的排序。
下面是用代码模仿上述第一趟划分过程的示例：
[code]#include // 分区函数，用于将数组以基准元素为界分为两部门int partition(int arr[], int low, int high) {    int pivot = arr[low];  // 选择第一个元素作为基准    int left = low + 1;    int right = high;    int temp;    while (1) {        // 左指针右移，直到找到大于基准的元素        while (left  18，不进行索引 i 的更新和元素交换操作。此时 i 仍为 -1。</ul>处理元素 16：

• 由于 16 < 18，将 i 加 1，此时 i 变为 0。
  
• 交换 arr（即 arr[0]，值为 28）和 arr[j]（即 arr[1]，值为 16），数组变为 [16, 28, 32, 12, 60, 2, 5, 18]。
  

处理元素 32：

• 由于 32 > 18，不进行索引 i 的更新和元素交换操作。此时 i 仍为 0。
  

处理元素 12：

• 由于 12 < 18，将 i 加 1，此时 i 变为 1。
  
• 交换 arr（即 arr[1]，值为 28）和 arr[j]（即 arr[3]，值为 12），数组变为 [16, 12, 32, 28, 60, 2, 5, 18]。
  

处理元素 60：

• 由于 60 > 18，不进行索引 i 的更新和元素交换操作。此时 i 仍为 1。
  

处理元素 2：

• 由于 2 < 18，将 i 加 1，此时 i 变为 2。
  
• 交换 arr（即 arr[2]，值为 32）和 arr[j]（即 arr[5]，值为 2），数组变为 [16, 12, 2, 28, 60, 32, 5, 18]。
  

处理元素 5：

• 由于 5 < 18，将 i 加 1，此时 i 变为 3。
  
• 交换 arr（即 arr[3]，值为 28）和 arr[j]（即 arr[6]，值为 5），数组变为 [16, 12, 2, 5, 60, 32, 28, 18]。
  

</ul>放置基准元素

遍历完除基准元素外的所有元素后，i 为 3。将基准元素 18 与 arr[i + 1]（即 arr[4]，值为 60）交换位置，数组变为 [16, 12, 2, 5, 18, 32, 28, 60]。
划分结果

经过第一趟划分后，数组变为 [16, 12, 2, 5, 18, 32, 28, 60]。基准元素 18 已经处于其最终排序的正确位置，左边子数组 [16, 12, 2, 5] 中的所有元素都小于 18，右边子数组 [32, 28, 60] 中的所有元素都大于 18。后续可以递归地对左右子数组分别进行快速排序，以完成整个数组的排序。
下面是用代码模仿上述第一趟划分过程的示例：
[code]#include // 分区函数，用于将数组以基准元素为界分为两部门int partition(int arr[], int low, int high) {    int pivot = arr[high];  // 选择最后一个元素作为基准    int i = (low - 1);  // 初始化小于基准元素的元素的索引    for (int j = low; j