快速排序（C语言实现）

时间复杂度：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的位置上
                           
如果基准数为最右边的值，这里需要从左边开始找

快速排序（C语言实现）

原文：https://www.cnblogs.com/haiziche/p/15359132.html