—快速排序—
快速排序的名字起的是简单粗暴，快，而且效率高! 它是处理大数据最快的排序算法之一了。
算法描述
具体算法描述如下：
<1>.从数列中挑出一个元素，称为 “基准”（pivot/base）；
<2>.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
<3>.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码实现
int Quick_Sort(int a[], int left,int right)
{
int base = a[left]; // 将第一个元素定为基准值
while (left < right) // 当左游标大于右游标
{
while (left < right && base<= a[right] ) // 当左游标大于右游标 且右边元素大于基准值
right--; // 右游标向前移
a[left] = a[right]; //否则 左边空出来的位置赋值为 右边小于基准值的数
while (left < right && base>= a[left]) //同理
left++;
a[right] = a[left];
}
a[left] = base; // 将left 与 right 指向同一地方的空缺赋值
return left;
}
void QuickSort(int a[],int left,int right)
{
if (left< right) //在基准值的地方继续分为左右两部分
{
int base = Quick_Sort(a, left, right);
QuickSort(a, left, base-1);
QuickSort(a, base + 1, right);
}
}
算法分析
平均情况：T(n) = O(nlogn)
最佳情况：T(n) = O(nlogn)
最差情况：T(n) = O(n2)
稳定性
- 不稳定
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 351134995@qq.com
