快速排序

直白的说，快速排序的主要思想是分治，将一个大数组，分成两个数组，然后对两个数组分别排序。对小数组排序的时候，同样按照这种思想，分成两个，再排序。直到不能再分，也就是长度为1，那么这个小数组就排好，当所有的小数组都排好了的时候，整个大数组也就排好了。

既然要分成两部分，那么就要选定一个基准，快速排序里面管这个叫做pivot，左边的都比pivot小，右边的都比pivot大。选取pivot的方式有多种，选最左侧的、选最右侧的、或者随机选一个位置当pivot。

一般选最左侧位置的就好。然后，就需要将剩下的数字分成两部分。使用两个指针，一个指向最左侧位置，另一个指向最右侧位置。左侧指针向右移动，右侧指针向左移动。

在左指针向右扫的过程中，如果遇到比pivot大的数字，就停下来；同样，当右指针向左扫的过程中，如果遇到比pivot小的数字，也停下来，此时将两个指针的数字交换，然后又可以继续扫，直到相遇。

左侧指针走过的数字，都比pivot小，右侧指针走做的数字，都比pivot大，两个指针相遇则停止，这个时候以相遇位置为分界线，数组就分成了两部分，将pivot和相遇点交换即可。

然后将左侧是数组和右侧的数组分别重复这个过程，等到都完成时，也就排序完成了。

public class Solution
{
    public int[] SortArray(int[] nums)
    {
        return QuickSort(nums, 0, nums.Length - 1);
    }

    private int[] QuickSort(int[] nums, int left, int right)
    {
        if (left >= right) return nums;

        int l = left;

        int r = right;

        int pivot = nums[l];

        while (left < right)
        {
            while (nums[right] > pivot && right > left)
            {
                right -= 1;
            }

            while (nums[left] <= pivot && left < right)
            {
                left += 1;
            }

            if (left != right)
            {
                (nums[left], nums[right]) = (nums[right], nums[left]);
            }
        }

        if (l != left)
        {
            (nums[l], nums[left]) = (nums[left], nums[l]);
        }

        QuickSort(nums, l, left - 1);

        QuickSort(nums, left + 1, r);

        return nums;
    }
}