跳至主要內容

快速排序

黑静美原创...小于 1 分钟编程c数据结构

快速排序

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

空间复杂度是O(nlogn)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);
}
上次编辑于:
贡献者: Heijingmei
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v3.1.3