关于快速排序的问题
poj1002.
我调用自己写的快排就超时了。
快排程序如下:
void sort(int l,int r)
{int i=l,j=r,x=a[i];
if (l>=r) return ;
while (i<j)
{while (i<j&&a[j]>=x) --j;a[i]=a[j];
while (i<j&&a[i]<=x) ++i;a[j]=a[i];
}
a[i]=x;
sort(l,i-1);
sort(i+1,r);
}
然后百度了发现别人都是用库函数快排
qsort(a,n,sizeof(int),comp);
我也用了就没超时ac了。
是我快排写的不好,还有优化的地方吗???以前一直用的那个当模板的结果这次超时了伤心(Y-Y)
有没有能把我写的快排优化的或者解释下超时的原因。。
[解决办法]
void sort(int* a,int l,int r)//参数少了一个{int i=l,j=r,x=a[i]; if (l>=r) return ; while (i<j) {while (i<j&&a[j]>=x) --j;if(i<j) a[i++]=a[j];//这里 while (i<j&&a[i]<=x) ++i;if(i<j) a[j--]=a[i];//这里 } a[i]=x; sort(a,l,i-1); sort(a,i+1,r);}
[解决办法]
先
http://www.microsoft.com/visualstudio/en-us/products/2010-editions/visual-cpp-express
右边Visual C++ 2010 Express下面的Select language...下拉选‘简体中文’,再按Install Now按钮
再参考
C:\Program Files\Microsoft Visual Studio 10.0\VC\crt\src\qsort.c
[解决办法]
void QuickSort(int *data, int left, int right){ int tmp = data[left]; int p = left; int i = left, j = right; while (i <= j) { while (j >= p && data[j] >= temp) j--; if (j >= p) { data[p] = data[j]; p = j; } while (i <= p && data[i] <= temp) i++; if (i <= p) { data[p] = data[i]; p = i; } } data[p] = temp; if (p - left > 1) QuickSort(data, left, p - 1); if (right - p > 1) QuickSort(data, p + 1, right);}