欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

常用排序算法的实现(C语言版)-快速排序

程序员文章站 2024-01-09 20:37:58
...
快速排序:
/*
*将r位置中的位置移动到正确位置q上,并返回q,使得在a[p]..a[q-1] < a[q],
a[q+1]..a[r] > a[q]
*/
int partition(int a[], int p, int r);
void qSort(int a[], int p, int r);

void quickSort(int a[], int n) {
	qSort(a, 0, n - 1);
}

void qSort(int a[], int p, int r) {
	int  q;
	while (p < r) {
		q = partition(a, p, r);
		qSort(a, p, q - 1);
		p = q + 1;
	}
}

int partition(int a[], int p, int r) {
	int x, i, j;

	x = a[r];
	i = p - 1;
	for (j = p; j < r; j++) {
		if (a[j] <= x) {
			i++;
			swap(a, i, j);
		}
	}
	i++;
	swap(a, i, r);
	return i;
}