快速排序
`static void quick_sort(int q[], int l, int r)
{
if (l >= r) return; //l==r也可以
int i = l - 1, j = r + 1; //i,j的初始化值是为了和do-while对应
int x = q[(l + r)/2]; //x不能只取下标,要是数组里的数,只取下标后面数值会发生改变
while (i < j) // 跳出循环后有两种情况,1、i == j; 2、i == j + 1;
{
//用do-while是为了防止相等时陷入死循环,每次交换完立即i+1,j-1
do i ++ ; while (q[i] < x); //不加等号可以理解为,要满足交换后>=x,加等号后只满足>x
do j -- ; while (q[j] > x);
//跳出循环时,j+1肯定>x,所以后面递归用j+1;同理i-1<x,所以用i递归时要用i-1
if (i < j) {
int t=q[i];
q[i]=q[j];
q[j]=t;
}
}
//用j递归时,x不能取右边界,如r、(l+r+1)/2
quick_sort(q, l, j);
quick_sort(q, j + 1, r); //
//用i递归也可以:quick_sort(q, l, i - 1);quick_sort(q, i, r); 但是x不能取左边界,如l,(l+r)/2
}`
归并排序
`static void merge_sort(int[] q, int l, int r){
if(l >= r) return;
int mid = l + r >> 1; //位右移,速度更快,相当于除2^1
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
//这里不用mid-1和mid是因为mid是向下取整,可能取到l,这样会陷入死循环,如果mid=(l+r+1)/2,则用mid-1
int i = l, j = mid + 1, k = 0;
int[] t=new int[r-l+1]; //t数组如果设置为r+1,直接从l开始,会超时
while (i <= mid && j <= r)
if(q[i] <= q[j]) t[k ++ ]=q[i ++ ]; //这里的<=保证了归并排序的稳定性
else t[k ++ ]=q[j ++ ];
//这里用两个while很巧妙
while (i <= mid) t[k ++ ] = q[i ++ ];
while (j <= r) t[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) //for循环同时用i和j,也很巧妙
q[i] = t[j];
}`