C#算法之快速排序

        算法释义：朋友们，我们在上文中说到，归并算法是一种分治算法，同样的，快速排序也是一种分治算法。所谓分治算法，原理上来说，是将规模为N的问题分解为若干个规模为较小的M的问题，这些子问题相互独立，并且原理相同，我们把子问题的解都求解完毕，自然就把最初的问题解决掉了。

        再说快速排序，它的基本思想是选择一个元素作为“基准”（pivot），然后重新排列数组，使得所有比基准小的元素都在基准的左边，所有比基准大的元素都在基准的右边。这个过程称为分区。之后，递归地对基准左边和右边的子数组进行同样的操作。

        当然了，在实际应用中，根据具体的需求，进行分区，不一定是两个，可以是N个。好，我们一起来看代码：

    public static void Main()
    {
        int[] array = { 10, 7, 8, 9, 1, 5 };
        Console.WriteLine("Given Array");
        PrintArray(array);

        QuickSort(array, 0, array.Length - 1);
        
        Console.WriteLine("\nSorted array");
        PrintArray(array);
    }

    // 快速排序的主要函数
    public static void QuickSort(int[] array, int low, int high)
    {
        if (low < high)
        {
            // 分区并获取基准的索引
            int pivotIndex = Partition(array, low, high);

            // 递归地对基准左边和右边的子数组进行快速排序
            QuickSort(array, low, pivotIndex - 1);
            QuickSort(array, pivotIndex + 1, high);
        }
    }

    // 分区函数
    public static int Partition(int[] array, int low, int high)
    {
        // 选择最后一个元素作为基准
        int pivot = array[high];
        int i = low - 1;

        for (int j = low; j < high; j++)
        {
            // 如果当前元素小于或等于基准
            if (array[j] <= pivot)
            {
                i++;
                // 交换 array[i] 和 array[j]
                Swap(array, i, j);
            }
        }
        // 将基准元素放到正确的位置
        Swap(array, i + 1, high);
        return i + 1;
    }

    // 交换数组中的两个元素
    public static void Swap(int[] array, int i, int j)
    {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    // 打印数组的函数
    public static void PrintArray(int[] array)
    {
        foreach (int item in array)
        {
            Console.Write(item + " ");
        }
        Console.WriteLine();
    }