没想到再次回顾快排发现自己对于快排的理解还不是很深入。
快排的时间复杂度为O(nlogn) ~ O(n^2);
若用《数据结构(C语言版)》中的算法:
void Quick_Sort(int *arr, int begin, int end){ if(begin > end) return; int tmp = arr[begin]; int i = begin; int j = end; while(i != j){ while(arr[j] >= tmp && j > i) j--; while(arr[i] <= tmp && j > i) i++; if(j > i){ int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } } arr[begin] = arr[i]; arr[i] = tmp; Quick_Sort(arr, begin, i-1); Quick_Sort(arr, i+1, end); }
每次以第一个数据为参照数,则在数组为逆序时的时间复杂度为O(n^2),递归次数为n-1,而最好的时候(平均递归),递归次数为logn,每次遍历次数都为n。
但是这样子写,在Acwing会被卡,所以有了优化代码:
void quick_sort(int f[],int l, int r) { if(l >= r) return; int i = l - 1, j = r + 1, x = f[l + r >> 1]; while(i < j) { do i ++; while (f[i] < x); do j --; while (f[j] > x); if(i < j) swap(f[i],f[j]); } quick_sort(f , l, j); quick_sort(f , j + 1, r); }
这里面的参照数是随机选取的(取的数组中心值),所以在最坏情况下的时间复杂度要小于O(n2)。
标签:arr,end,int,复杂度,begin,while,排序,快速 From: https://www.cnblogs.com/Geniw/p/17519515.html