排序

快速排序

快速排序的平均时间复杂度是$O(nlogn)$（最好的情况下的时间复杂度是$O(nlongn)$），最坏的情况下，可退化成$O(n^2)$（少见）

空间复杂度是$O(nlogn)$​

void quicksort(int a[], int L, int R) // L und R bezeichnen die linke bzw. rechte
                                      // Grenze des zu sortierenden Teils von a
{ int i, j, w, x, k;
i = L; j = R; // i und j durchlaufen a von links bzw. rechts
k = (L+R) / 2; 
x = a[k]; // x wird Pivotelement genannt
	do{
	while (a[i] < x) i = i + 1;
	while (a[j] > x) j = j - 1;
		if (i <= j){
        w = a[i]; //
        a[i] = a[j]; // hier werden a[i] und a[j] getauscht
        a[j] = w; //
        i = i + 1; j = j - 1;
        }
    }
while (i <= j);
    if (L < j) quicksort(a, L, j);
	if (R > i) quicksort(a, i, R);
}