快速排序

双指针思想

无需开辟额外的空间
有两个指针i，j，分别在最左端和最右端
然后i，j两个指针往中间走
i往中间走，直到遇到第一个大于x的数，然后停下来（因为大于x的要放在右半边）【遇到小于x的数i就继续往下走】
j往中间走，直到遇到第一个小于x的数，然后停下来（小于x的数放在左半边）
此时将i所指的数与j指的数交换一下，那么i指的新的数就是小于x的数，j指的新的数就是大于x的数，归位了。
接着重复这个过程，i，j往中间走；
直到i，j相遇，就可以把区间一分为二【左边小于x,右边大于x】
会发现，任何时刻i左边的数都是小于x的，j右边的数都是大于x的
当两个指针相遇或是穿过之后，这两个指针左边的数就是大于等于x，右边的数就是大于等于x，完美的分成两个区间

【x 归位一次，就分好一次区间，不断递归左右两个区间，直到所有的x归位】

---

快排模板

c++版本

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[], int l, int r)
{
	if (l >= r) return ; // 如果数组一个数都没有或者只有一个数，就不用排序、
	
	//设置两个指针，以及分界点x 
	int x = q[l], i = l - 1, j = r + 1; //这里两个指针我们设置在数组外，这样我们可以不管，直接让二者都往里面走
	
	//开始循环
	while (i < j)
	{
		//只有两个指针没有碰到才可以继续走
		do ++i; while (q[i] < x); //当 q[i] < x就继续往下走
		do --j; while (q[j] > x); //当q[j] > x就继续往下走，直到j指针指到一个<=x的数，说明应该放在左边
		
		//判断i, j两个指针未碰到就可以交换
		if (i < j) swap(q[i], q[j]); 
	} 
	//一次循环结束后，分界点x归位，接着继续分别递归左右两边
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r); 
}
int main ()
{
	scanf ("%d",&n); // 输入有几个数
	for (int i = 0; i < n; ++i)
	{
		scanf ("%d",&q[i]); // 输入数组 
	} 
	
	// 快速排序
	quick_sort(q, 0, n - 1);//范围0 - n-1
	for (int i = 0; i < n; ++i) printf ("%d ",q[i]);
	printf ("\n");
	return 0; 
}

java版本

public static void quickSort(int[] arr,int l ,int r){
        if(l >= r) return;                  //递归结束条件
        int i = l - 1;                      //左边的指针
        int j = r + 1;                      //右边的指针
        int x = arr[l + ((r - l) >> 1)];    //选取数组中间的那个数作为分界点，把数组分成两部分
        while(i < j){
            do{
                i++;
            }while(arr[i] < x);             //在左边大于分界点的数停下
            do{
                j--;
            }while(arr[j] > x);             //在右边小于分界点的数停下
            if(i < j){                      //交换两个数
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        quickSort(arr,l,j);                 //递归处理左边
        quickSort(arr,j+1,r);               //递归处理右边
    }