/// <summary>
/// 名称:快速排序
/// 原理:每一次排序找一个基准数K,将小于等于K的数全部放到K的左边,将大于等于K的数放到K的右边
/// 举例:10个数进行排序,先以第1个数为基准数K,"哨兵j"先从右往左找比K小的数,然后"哨兵i"从左往右找比K大的数,找到则进行交换,直至两边的"哨兵"相遇
/// 释疑:为什么"哨兵j"要先移动,如果"哨兵i"先移动,最后的结果会出现比基准数大的数会被移到左边
/// 时间复杂度: 快速排序不用相邻两数两两比较,所以比冒泡排序快,当然最坏情况下,仍然是相邻两数进行交换,最坏情况下是O(n的平方),平均时间复杂度为O(NlogN)
/// 优化:选择基准数有不同的策略,这里使用了固定中轴策略,以第一个数为基准数,这种情况下效率是比较糟糕的,最坏情况下为O(n的平方)
/// 其他策略:1.随机选取基准 使用rand()%(high-low)+low为基准位置
/// 2.三数取中 比较左边、右边和中心位置的三个元素,取中间的值作为基准数
/// </summary>
/// <param name="array"></param>
/// <param name="left"></param>
/// <param name="right"></param>
static void QuickSort(int[] array,int left,int right)
{
int low = left, high = right;
//避免数据越界
if (left > right)
return;
var k = array[left];
while (low != high)
{
//先从右边开始移动,找到比K小的数
while (array[high] >= k && low < high)
high--;
//再从左边移动,找到比K小的数
while (array[low] <= k && low < high)
low++;
//当两个哨兵还没有相遇,交换两个位置的数
if (low < high)
{
var t = array[low];
array[low] = array[high];
array[high] = t;
}
}
//当两个哨兵相遇 将哨兵i指向的数与基准数交换
array[left] = array[low];
array[low] = k;
QuickSort(array, left, low - 1);//继续排序左边的
QuickSort(array, low + 1, right);//继续排序右边的
}