数据结构与算法-算法篇：排序—快速排序（六）

数据结构与算法系列文章：数据结构与算法目录

快速排序的核心思想也是分治法，分而治之。它的实现方式是每次从序列中选出一个基准值，其他数依次和基准值做比较，比基准值大的放右边，比基准值小的放左边（相同的数可以到任一边），然后再对左边和右边的两组数分别选出一个基准值，进行同样的比较移动，重复步骤，直到最后都变成单个元素，整个数组就成了有序的序列。

使用双边扫描：
随意抽取一个数作为基准值，然后从数组左右两边进行扫描，先从左往右找到一个大于基准值的元素，将下标指针记录下来，然后转到从右往左扫描，找到一个小于基准值的元素，交换这两个元素的位置，重复步骤，直到左右两个指针相遇，再将基准值与左侧最右边的元素交换。

实现：

/// <summary>
/// 快速排序
/// </summary>
/// <param name="arr"></param>
private void QuickSort(int[] arr)
{
    Sort(arr, 0, arr.Length - 1);
}

private void Sort(int[] arr, int startIndex, int endIndex)
{
    if (startIndex >= endIndex)
    {
        // 排序完毕
        return;
    }

    // 选个基准值，比基准值小的放左边，比基准值大的放右边
    int key = arr[startIndex];

    int left = startIndex;
    int right = endIndex;

    while (left < right)
    {
        // 从右往左找
        while (left < right && arr[right] >= key)
        {
            // 比基准值大，继续找
            right--;
        }
        // 找到比基准值小的，放左边
        arr[left] = arr[right];

        // 从左向右找
        while (left < right && arr[left] <= key)
        {
            // 比基准值小，继续找
            left++;
        }
        // 找到比基准值大的，放右边
        arr[right] = arr[left];
    }
    // 插入基准值
    arr[left] = key;

    // 从左向右依次排
    Sort(arr, startIndex, right - 1);
    // 从右向左依次排
    Sort(arr, left + 1, endIndex);
}