算法基础模版

算法 - 数学

排序

快速排序

	
void quick_sort(int q[], int l, int r) { //（优化基准值位置）
	if (l >= r) return;
	int i = l - 1, j = r + 1;
	int x = q[l + r >> 1];
	while (i < j) {
		do i++; while (q[i] < x);
		do j--; while (q[j] > x);
		if (i < j)
			swap(q[i], q[j]);
	}
	quick_sort(q, l, j);
	quick_sort(q, j+1, r);
}


void quick_sort(int[] a, int l, int r) {
	if (l >= r) return; 
	int i = l, j = r;
	int x = a[l]; // 左边为基准
	while (i < j) {
		while (i < j && a[j] >= x) j--; // 从右边开始
		a[i] = a[j]; 	// 将右边放置到左边 （空）
		while (i < j && a[i] >= x) i++;
		a[j] = a[i]		// 将左边放置到右边 （空）
	}
	a[i] = x;
    quickSort(a, l, i-1);
    quickSort(a, i+1, r);
}

void quickSort(int[] a, int l, int r) {
    if (l >= r) return ;
    int i = l, j = r;
    int x = a[r]; //  右边基准值
    while (i < j) {
        while (i < j && a[i] <= x) i++; // 左边开始
        a[j] = a[i];  
        while (i < j && a[j] >= x) j--;
        a[i] = a[j];
    }
    a[i] = x;
    quickSort(a, l, i-1);
    quickSort(a, i+1, r);
}