关于快速选择排序程序第一趟划分流程分析
<h1 id="关于快速选择排序程序第一趟划分流程分析">关于快速选择排序程序第一趟划分流程分析</h1><h2 id="问题128163212602572选择28作为基准第一趟划分分析">问题1：{28，16，32，12，60，2，5，72}选择28作为基准第一趟划分分析</h2>
<p>下面详细分析数组 <code>{28, 16, 32, 12, 60, 2, 5, 72}</code> 以 <code>28</code> 作为基准进行第一趟划分的过程。</p>
<h3 id="初始状态">初始状态</h3>
<pre><code class="language-plaintext">
</code></pre>
<ul>
<li>选择第一个元素 <code>28</code> 作为基准元素。</li>
<li>初始化指针：
<ul>
<li><code>left</code> 指针从 <code>low + 1</code> 即索引 <code>1</code> 开始，初始指向元素 <code>16</code>。</li>
<li><code>right</code> 指针从 <code>high</code> 即索引 <code>7</code> 开始，初始指向元素 <code>72</code>。</li>
</ul>
</li>
</ul>
<h3 id="指针移动与元素交换步骤">指针移动与元素交换步骤</h3>
<h4 id="第一轮移动与交换">第一轮移动与交换</h4>
<ul>
<li><strong><code>left</code> 指针移动</strong>：<code>left</code> 指向 <code>16</code>，因为 <code>16 < 28</code>，<code>left</code> 指针继续向右移动，指向 <code>32</code>。此时 <code>32 > 28</code>，<code>left</code> 指针停止移动。</li>
<li><strong><code>right</code> 指针移动</strong>：<code>right</code> 指向 <code>72</code>，因为 <code>72 > 28</code>，<code>right</code> 指针继续向左移动，指向 <code>5</code>。此时 <code>5 < 28</code>，<code>right</code> 指针停止移动。</li>
<li><strong>元素交换</strong>：此时 <code>left</code> 指向 <code>32</code>，<code>right</code> 指向 <code>5</code>，交换这两个元素，数组变为 <code></code>。</li>
</ul>
<h4 id="第二轮移动与交换">第二轮移动与交换</h4>
<ul>
<li><strong><code>left</code> 指针移动</strong>：<code>left</code> 继续右移，指向 <code>12</code>，因为 <code>12 < 28</code>，继续右移指向 <code>60</code>，<code>60 > 28</code>，<code>left</code> 指针停止移动。</li>
<li><strong><code>right</code> 指针移动</strong>：<code>right</code> 继续左移，指向 <code>2</code>，因为 <code>2 < 28</code>，<code>right</code> 指针停止移动。</li>
<li><strong>元素交换</strong>：此时 <code>left</code> 指向 <code>60</code>，<code>right</code> 指向 <code>2</code>，交换这两个元素，数组变为 <code></code>。</li>
</ul>
<h4 id="指针相遇">指针相遇</h4>
<ul>
<li><strong><code>left</code> 指针移动</strong>：<code>left</code> 继续右移。</li>
<li><strong><code>right</code> 指针移动</strong>：<code>right</code> 继续左移。当 <code>left > right</code> 时，指针相遇，此时 <code>right</code> 指向的元素是 <code>2</code>，<code>left</code> 指向的元素是 <code>60</code>，分区过程结束。</li>
</ul>
<h3 id="放置基准元素">放置基准元素</h3>
<p>将基准元素 <code>28</code> 与 <code>right</code> 指针所指的元素 <code>2</code> 交换位置，数组变为 <code></code>。</p>
<h3 id="结果分析">结果分析</h3>
<p>经过第一趟划分后，基准元素 <code>28</code> 已经处于其最终排序的位置，左边的子数组 <code></code> 中的所有元素都小于 <code>28</code>，右边的子数组 <code></code> 中的所有元素都大于 <code>28</code>。接下来就可以递归地对左右子数组分别进行快速排序，以完成整个数组的排序。</p>
<p>下面是用代码模拟上述第一趟划分过程的示例：</p>
<pre><code class="language-c">#include <stdio.h>
// 分区函数，用于将数组以基准元素为界分为两部分
int partition(int arr[], int low, int high) {
int pivot = arr;// 选择第一个元素作为基准
int left = low + 1;
int right = high;
int temp;
while (1) {
// 左指针右移，直到找到大于基准的元素
while (left <= right && arr <= pivot) {
left++;
}
// 右指针左移，直到找到小于基准的元素
while (left <= right && arr >= pivot) {
right--;
}
if (left > right) {
break;
}
// 交换左右指针所指的元素
temp = arr;
arr = arr;
arr = temp;
}
// 将基准元素放到正确的位置
temp = arr;
arr = arr;
arr = temp;
return right;
}
int main() {
int arr[] = {28, 16, 32, 12, 60, 2, 5, 72};
int n = sizeof(arr) / sizeof(arr);
int pivot_index = partition(arr, 0, n - 1);
printf("第一趟划分后的数组: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr);
}
printf("\n基准元素的最终位置索引: %d\n", pivot_index);
return 0;
}
</code></pre>
<h2 id="问题228163212602518选择18作为基准第一趟划分分析">问题2：{28，16，32，12，60，2，5，18}选择18作为基准第一趟划分分析</h2>
<p>下面详细分析这个过程：</p>
<h3 id="初始状态-1">初始状态</h3>
<ul>
<li>待排序数组：<code></code></li>
<li>基准元素 <code>pivot</code>：选择数组的最后一个元素 18。</li>
<li>初始化一个索引 <code>i</code> 为 <code>-1</code>，用于标记小于基准元素的元素的边界。</li>
</ul>
<h3 id="分区过程">分区过程</h3>
<h4 id="遍历数组元素">遍历数组元素</h4>
<p>从数组的第一个元素开始，依次与基准元素 18 进行比较，并根据比较结果进行相应操作。</p>
<ul>
<li>处理元素 28：
<ul>
<li>因为 <code>28 > 18</code>，不进行索引 <code>i</code> 的更新和元素交换操作。此时 <code>i</code> 仍为 <code>-1</code>。</li>
</ul>
</li>
<li>处理元素 16：
<ul>
<li>由于 <code>16 < 18</code>，将 <code>i</code> 加 1，此时 <code>i</code> 变为 <code>0</code>。</li>
<li>交换 <code>arr</code>（即 <code>arr</code>，值为 28）和 <code>arr</code>（即 <code>arr</code>，值为 16），数组变为 <code></code>。</li>
</ul>
</li>
<li>处理元素 32：
<ul>
<li>因为 <code>32 > 18</code>，不进行索引 <code>i</code> 的更新和元素交换操作。此时 <code>i</code> 仍为 <code>0</code>。</li>
</ul>
</li>
<li>处理元素 12：
<ul>
<li>由于 <code>12 < 18</code>，将 <code>i</code> 加 1，此时 <code>i</code> 变为 <code>1</code>。</li>
<li>交换 <code>arr</code>（即 <code>arr</code>，值为 28）和 <code>arr</code>（即 <code>arr</code>，值为 12），数组变为 <code></code>。</li>
</ul>
</li>
<li>处理元素 60：
<ul>
<li>因为 <code>60 > 18</code>，不进行索引 <code>i</code> 的更新和元素交换操作。此时 <code>i</code> 仍为 <code>1</code>。</li>
</ul>
</li>
<li>处理元素 2：
<ul>
<li>由于 <code>2 < 18</code>，将 <code>i</code> 加 1，此时 <code>i</code> 变为 <code>2</code>。</li>
<li>交换 <code>arr</code>（即 <code>arr</code>，值为 32）和 <code>arr</code>（即 <code>arr</code>，值为 2），数组变为 <code></code>。</li>
</ul>
</li>
<li>处理元素 5：
<ul>
<li>由于 <code>5 < 18</code>，将 <code>i</code> 加 1，此时 <code>i</code> 变为 <code>3</code>。</li>
<li>交换 <code>arr</code>（即 <code>arr</code>，值为 28）和 <code>arr</code>（即 <code>arr</code>，值为 5），数组变为 <code></code>。</li>
</ul>
</li>
</ul>
<h4 id="放置基准元素-1">放置基准元素</h4>
<p>遍历完除基准元素外的所有元素后，<code>i</code> 为 <code>3</code>。将基准元素 18 与 <code>arr</code>（即 <code>arr</code>，值为 60）交换位置，数组变为 <code></code>。</p>
<h3 id="划分结果">划分结果</h3>
<p>经过第一趟划分后，数组变为 <code></code>。基准元素 18 已经处于其最终排序的正确位置，左边子数组 <code></code> 中的所有元素都小于 18，右边子数组 <code></code> 中的所有元素都大于 18。后续可以递归地对左右子数组分别进行快速排序，以完成整个数组的排序。</p>
<p>下面是用代码模拟上述第一趟划分过程的示例：</p>
<pre><code class="language-c">#include <stdio.h>
// 分区函数，用于将数组以基准元素为界分为两部分
int partition(int arr[], int low, int high) {
int pivot = arr;// 选择最后一个元素作为基准
int i = (low - 1);// 初始化小于基准元素的元素的索引
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于基准元素
if (arr < pivot) {
i++;
// 交换 arr 和 arr
int temp = arr;
arr = arr;
arr = temp;
}
}
// 将基准元素放到正确的位置
int temp = arr;
arr = arr;
arr = temp;
return (i + 1);
}
int main() {
int arr[] = {28, 16, 32, 12, 60, 2, 5, 18};
int n = sizeof(arr) / sizeof(arr);
int pivot_index = partition(arr, 0, n - 1);
printf("第一趟划分后的数组: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr);
}
printf("\n基准元素的最终位置索引: %d\n", pivot_index);
return 0;
}
</code></pre><br><br>
来源：https://www.cnblogs.com/ice-cui/p/18836075
頁:
[1]