快速排序算法设计一

快速排序算法设计

（1）选择基准元素：在待排序数组中选择一个元素作为基准值(pivot)，通常选择第一个、最后一个或中间元素

（2）分区操作：重新排列数组，使得比基准值小的元素放在左侧，比基准值大的元素放在右侧

    a. 设置两个指针：左指针left从数组起始位置开始，右指针right从数组末尾开始

    b. 移动指针：

        - 左指针向右移动，直到找到大于等于基准值的元素

        - 右指针向左移动，直到找到小于等于基准值的元素

    c. 交换元素：如果左指针仍在右指针左侧，则交换这两个元素

    d. 重复步骤b-c，直到左指针超过右指针

    e. 将基准值与右指针指向的元素交换，此时基准值位于正确排序位置

（3）递归排序：对基准值左右两个子数组分别重复执行步骤（1）（2），直到子数组大小为1或0时停止

using System; // 引入系统命名空间，提供基本的系统功能

class Program // 定义程序主类
{
    static void Main(string[] args) // 程序入口点
    {
        int[] arr = { 12, 7, 15, 6, 3, 8, 2, 9, 1, 11 }; // 初始化一个整数数组
        Console.WriteLine("排序前:"); // 输出提示信息"排序前:"
        PrintArray(arr); // 调用PrintArray方法打印排序前的数组
        QuickSort(arr, 0, arr.Length - 1); // 调用QuickSort方法对数组进行快速排序，参数为数组、起始索引和结束索引
        Console.WriteLine("排序后:"); // 输出提示信息"排序后:"
        PrintArray(arr); // 调用PrintArray方法打印排序后的数组
    }

    static void QuickSort(int[] arr, int low, int high) // 快速排序方法，参数为待排序数组、低位索引和高位索引
    {
        if (low < high) // 如果低位索引小于高位索引，继续排序
        {
            int pivotIndex = Partition(arr, low, high); // 调用Partition方法获取分区点索引
            QuickSort(arr, low, pivotIndex - 1); // 递归排序分区点左侧的子数组
            QuickSort(arr, pivotIndex + 1, high); // 递归排序分区点右侧的子数组
        }
    }
   
    static int Partition(int[] arr, int low, int high) // 分区方法，将数组分为两部分，左边小于基准值，右边大于基准值
    {
        int key = arr[low]; // 选择第一个元素作为基准值(pivot)
        int i = low + 1; // 左指针，从基准值后一个位置开始
        int j = high; // 右指针，从数组末尾开始

        while (i <= j) // 当左指针不超过右指针时继续循环
        {
            if (arr[i] < key) // 如果左指针指向的元素小于基准值
            {
                i++; // 左指针向右移动
            }else{ // 如果左指针指向的元素大于等于基准值
                Swap(arr, i, j); // 交换左右指针指向的元素
                j--; // 右指针向左移动
            }
        }

       
        Swap(arr, low, i - 1); // 将基准值与正确位置的元素交换
        return i - 1; // 返回分区点索引
    }
   
    static void Swap(int[] arr, int i, int j) // 交换数组中两个元素的位置
    {
        int temp = arr[i]; // 将第i个元素暂存到临时变量
        arr[i] = arr[j]; // 将第j个元素赋值给第i个位置
        arr[j] = temp; // 将临时变量中的原第i个元素赋值给第j个位置
    }
   
    static void PrintArray(int[] arr) // 打印数组元素的方法
    {
        foreach (int item in arr) // 遍历数组中的每个元素
        {
            Console.Write(item + " "); // 输出当前元素及一个空格
        }
        Console.WriteLine(); // 换行
    }
}