快速排序算法原理解析与C#代码实现

快速排序算法思想

快速排序（Quick Sort）由 C.R.A. Hoare 于 1962 年提出，它基于分治策略（Divide-and-Conquer Method）。该方法的基本步骤如下：

1. 选择基准：从数列中取出一个数作为基准数（通常取第一个或最后一个）。
2. 分区操作：重新排列数列，将所有比基准数小的数放在其左边，比基准数大的数放在其右边。经过这一步骤，基准数就处于其最终排序后的正确位置。
3. 递归排序：递归地将基准数左边的子数列和右边的子数列进行快速排序，直到各子区间只剩下一个元素，排序完成。

图解：挖坑填数法步骤

虽然称为分治法，但为了更直观地理解数据移动过程，常采用“挖坑填数”的方式进行模拟。以下将以一组具体数据为例，演示单轮划分的全过程。

第1步：初始化并选定基准数

假设初始数组为：[72, 6, 57, 88, 60, 42, 83, 73, 48, 85]。
我们将区间左侧第一个数 a[0] = 72 选为基准数 X，并将 a[0] 的值保存到变量 X 中。此时，a[0] 位置上相当于形成了一个“坑”，可以填入其他数据。

此时状态：
- i = 0（指向左侧）
- j = 9（指向右侧）
- X = 72

第2步：从右向左查找小于基准数的元素

首先从右端（索引 j=9）开始向前扫描，寻找第一个比 X (72) 小或等于 X 的元素。
当 j=8 时，发现 a[8] = 48，符合条件。将 a[8] 的值填入刚才形成的 a[0] 这个坑中，即执行 a[0] = a[8]。
此时，原来的 a[0] 被填满，但 a[8] 变成了一个“新坑”。接着将左指针 i 向后移一位（i++），此时 i=1。

第3步：从左向右查找大于基准数的元素

现在需要填补 a[8] 这个坑。从左端（当前 i=1）开始向后扫描，寻找第一个比 X (72) 大或等于 X 的元素。
- i=1, a[1]=6，小于 72，继续。
- i=2, a[2]=57，小于 72，继续。
- i=3, a[3]=88，大于 72，符合条件。

将 a[3] 的值填入 a[8] 这个坑中，即执行 a[8] = a[3]。
此时，a[8] 被填满，而 a[3] 变成了新的“坑”。接着将右指针 j 向前移一位（j--），此时 j=7。

第4步：重复交替查找直到相遇

当前状态：
- 基准数 X = 72
- 左指针 i = 3
- 右指针 j = 7

再次进入循环：

1. 从右向左找：从 j=7 开始向前找。找到 j=5 时，a[5]=42 小于 72，符合条件。将 a[5] 填入 a[3]（即上一个坑），执行 a[3] = a[5]。然后左指针 i 后移，变为 i=4。
2. 从左向右找：从 i=4 开始向后找。当 i 移动到 5 时，发现 i == j，即左右指针相遇。此时循环终止。

第5步：填入基准数完成一轮划分

当 i == j == 5 时，将之前保存的基准数 X (72) 填入当前位置 a[5]。
此时数组变为：[48, 6, 57, 42, 72, 88, 83, 73, 85, 60]（注：此处仅为示意中间过程，实际数值位置随填充变动）。

经过这一轮操作，我们可以观察到：
- a[5] 左侧的所有数字都小于 72；
- a[5] 右侧的所有数字都大于 72。

至此，a[5] 已经排好序。接下来只需对 a[0...4] 和 a[6...9] 这两个子区间递归地执行上述步骤即可。

C#实现示例

下面提供基于 .NET 环境的 C# 实现代码。代码包含两个核心方法：Division 负责分区操作，QuickSort 负责递归调用。

using System;
using System.Collections.Generic;

namespace QuickSort
{
    public class QuickSortClass
    {
        /// 

        /// 分区操作：确定基准数的最终位置
        /// 
        public int Division(List<int> list, int left, int right)
        {
            // 首先挑选一个基准元素（这里选择区间的第一个元素）
            int baseNum = list[left];
            
            while (left < right)
            {
                // 1. 从数组的右端开始向前找，找到比base小的数字为止
                while (left < right && list[right] >= baseNum)
                    right = right - 1;
                // 将找到的较小元素放到左端（填补之前的坑）
                list[left] = list[right];
                
                // 2. 从数组的左端开始向后找，找到比base大的数字为止
                while (left < right && list[left] <= baseNum)
                    left = left + 1;
                // 将找到的较大元素放到右端（填补之前的坑）
                list[right] = list[left];
            }
            
            // 最后把baseNum放到该left的位置（此时left==right）
            list[left] = baseNum;
            
            // 返回基准数的最终索引位置
            return left;
        }

        /// 

        /// 快速排序主函数：递归分割数组
        /// 
        public void QuickSort(List<int> list, int left, int right)
        {
            // 如果左下标小于右下标，说明还有数据未排序
            if (left < right)
            {
                // 对数组进行分割，获取基准数的位置
                int i = Division(list, left, right);

                // 递归处理基准数左侧的子区间
                QuickSort(list, left, i - 1);

                // 递归处理基准数右侧的子区间
                QuickSort(list, i + 1, right);
            }
        }
    }
}

以上就是快速排序算法原理及C#实现内容的详细讲解，更多关于编程算法的资料请关注本站其它相关文章！