快速排序

quick sort是非常常见的排序

写法也多种多样

核心是每次函数递归/迭代有两个状态, left和right

当left < right的时候才会继续分割, 否则return(left >= right)

pivot的选择一般是随机选择, 也会有人选最左边的, 或者最中间的, 这无所谓

因为范围实际上边界可以取, 所以是[left, right]而言, 对于pivot中间值的选择, 上取整下取整都是可以的

然后就进行一次排序

i和j分别从两侧往中间汇合

i++ 与 j--

这里判断的条件就显得很重要了

int pivot = arr[(left+right)/2];
int i = left;
int r = right;
while(i <= j){
	while(arr[i] < pivot){
		i++;
	}
	while(arr[j] < pivot){
		j--;
	}
	if(i <= j){
		swap[arr[i], arr[j]];
		i++;
		j--;
	}
}

现在有个问题是, 当pivot就是arr[i]或者arr[j]的时候, 一次操作那不就退化成了O(2n)的复杂度?
所以这才是随机选择pivot的意义所在?
我还看到一种写法

int pivot = first;
int i = first;
int j = last;
while(i < j){
	while(arr[i] <= arr[pivot] && i < last){
		i++;
	}
	while(arr[j] > arr[pivot]){
		j--;
	}
	if(i < j){
		swap(arr[i], arr[j]);
	}
}
swap(arr[j], arr[pivot]);

就这种写法而言, arr[pivot]是不需要经常swap的, 只有O(n)的复杂度
当然这里为了照顾边界条件的原因, 多走了一次i<last的判断
仁者见仁智者见智
个人觉得代码自己认为清晰易懂就是极好的