c++快速排序的简洁方法

快速排序就相当于二叉树的前序遍历

void quicksort(int l, int r)//这里采用左闭右闭[l,r]写法
{
	if (r <=l)return;
	int i, j;
	for (i = l - 1, j = l; j < r; j++) //i设为i-1是为了满足当arr[l]<=arr[r]时不作改变
	{
		if (arr[j] <= arr[r])
		{
			i++;
			swap(arr[i], arr[j]);  //可以证明，i与j之间（如果存在数）一定是大于arr[r]的
		}
	}
	swap(arr[i + 1], arr[r]);  //最后j到达r-1，[0,i]小于等于arr[r]，[i+1,r-1]大于arr[r]
	quicksort(l, i);
	quicksort(i + 2, r);    //需要注意初始调用quicksort时参数为1,arr.size()
}

有图辅助理解