数据结构与算法系列文章：数据结构与算法目录
快速排序的核心思想也是分治法，分而治之。它的实现方式是每次从序列中选出一个基准值，其他数依次和基准值做比较，比基准值大的放右边，比基准值小的放左边（相同的数可以到任一边），然后再对左边和右边的两组数分别选出一个基准值，进行同样的比较移动，重复步骤，直到最后都变成单个元素，整个数组就成了有序的序列。
使用双边扫描：
随意抽取一个数作为基准值，然后从数组左右两边进行扫描，先从左往右找到一个大于基准值的元素，将下标指针记录下来，然后转到从右往左扫描，找到一个小于基准值的元素，交换这两个元素的位置，重复步骤，直到左右两个指针相遇，再将基准值与左侧最右边的元素交换。
实现：
/// <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);
}
