快速排序
原创...小于 1 分钟
快速排序
快速排序的平均时间复杂度是(最好的情况下的时间复杂度是),最坏的情况下,可退化成(少见)
空间复杂度是
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);
}
Powered by Waline v3.1.3