关于Quicksort

基本思想

1、先从数列中取出一个数作为基准数

2、分区，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
通过一个while循环实现。i=j的时候，归并完毕。

3、再对左右区间重复第二步，直到各区间只有一个数

快速排序为什么要从基准对面开始？

如果从基准一侧出发，这里我们说从左侧出发，i停留的位置对应的数字一定是比基准大。i，j相遇的时候，这不就把比基准小的换到基准左侧了。

好的，从右边再来一次。数组尾元素为基准，j从右往左移动，找到比基准小的数字，停下。i，j，改数字比基准小，却要放在基准后面了。

时间复杂度

平均 nlogn
最差 n^2
证明【只是内容的搬运工】：

image.png

手撕代码

踩雷的地方

• 递归的出口
• 循环的条件

void QuickSort(int* N, int low, int high)
{
if ( low>=high ) { return; }
int flag = N[low];//基准
int i = low,j=high;//i，j两个查找的“哨兵”
while(i != j)
 {
    while(N[j] >= flag && j>i)
         j--;
    while(N[i]<=flag && i<j)
        i++;

    if( i < j )//找到大于和小于flag的数，交换。换完继续找。一次while循环要找完
    {
        int tmp =N[i];
        N[i]=N[j];
        N[j]=N[i];
    }
}
//跳出循环，归并结束，把flag放在i/j的位置上。
N[low] = N[i];
N[i] = flag;

//对其余两个区间排序；
 QuickSort(N,low, i - 1);
 QuickSort(N,i + 1, high);
}