|
时间复杂度：O（nlogn）
空间复杂度：O（logn）
思路：
任意选取一个数作为基准数，从数组两端同时遍历，左边寻找比基准数大的，右边寻找比基准数小的，将这两个数交换位置，当左右两端符合上面条件的数都交换完后再将基准数放在中间，基准数此时所在的位置就是数组排序后应该在的位置。一轮结束后再通过递归将左半边和右半边的基准数分别归位。
具体实现如下
void quicksort(int* a, int left, int right) {
if(left>=right)//判断是否为空数组
return;
/*
i从左边寻找 j从右边寻找
t为交换两个变量时的临时变量
temp为存储基准数的变量
*/
int i,j,t,temp;
temp = a[left];//temp为基准数
i = left;
j = right;
//把所有比基准数小的放左边，大的放右边
while(i!=j) {
while(a[j]>=temp && i<j)//从右边开始找比基准数小的
j--;
while(a[i]<=temp && i<j)//从左边开始找比基准数大的
i++;
if(i<j) {
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
/*将最后找到的比基准数小的那个和基准数交换位置*/
a[left] = a[i];//a[i]和a[j] 都可以 i==j
a[i] = temp;
//此时成功的将一个数放到它该在的位置了
quicksort(a,left,i-1);//再处理左边
quicksort(a,i+1,right);//处理右边
}
细节实现：
目标是让左半边全为小于等于基准数的，右半边全为大于等于基准数的
让i和j哨兵分别从左右两端开始
j找比基准数小的值 大于等于的一律不是，所以 while条件为 a[j]>=temp 继续循环去找
i找比基准数大的值 符合条件的保留，不符合条件的交换
与基准数相同的放在原位即可，一轮只找一个数，只要左边的没基准数大，右边的都没基准数小就找对了
找到后交换位置
当最后一轮找到的数为此情况时
6 8 2
交换后： 6 2 8
此时该轮已全部交换完成 i = x ；j = x+1
i!=j 循环继续
就不用再找与基准数比较的数了，需要将2和6的位置交换，故需要从右边先找，j先寻找
此时i和j相遇，且都为2的下标，就不用再循环了，故循环条件里需加上 i < j
如果情况为
6 2 8 8
i j
6 2 3 8
i j
j都会找到那个比基准数小的，最差也是找到i的位置上
如果基准数为最右边的值，这里需要从左边开始找
|