数组下标和赋值的奇特问题(洛谷快速排序模板题卡了)
先上代码比较程序代码:
#include<iostream> using namespace std; int arr[1000001],n; void quicksort(int left,int right) { int i=left; int j=right; int pivot=(left+right)/2; do { while(arr[i]<arr[pivot]) i++; while(arr[j]>arr[pivot]) j--; if(i<=j) { swap(arr[i],arr[j]); i++; j--; } }while(i<=j); if(left<j) quicksort(left,j); if(i<right) quicksort(i,right); } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>arr[i]; quicksort(1,n); for(int i=1;i<=n;i++) cout<<arr[i]<<" "; return 0; }
这是40分的,wa了三个点
程序代码:
#include<iostream> using namespace std; int arr[1000001],n; void quicksort(int left,int right) { int i=left; int j=right; int pivot=arr[(left+right)/2]; do { while(arr[i]<pivot) i++; while(arr[j]>pivot) j--; if(i<=j) { swap(arr[i],arr[j]); i++; j--; } }while(i<=j); if(left<j) quicksort(left,j); if(i<right) quicksort(i,right); } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>arr[i]; quicksort(1,n); for(int i=1;i<=n;i++) cout<<arr[i]<<" "; return 0; }
这是ac的代码
比较发现是直接int pivot=arr[(left+right)/2];
和
先int pivot=(left+right)/2;再while(arr[i]<arr[pivot]),也就是放数组中的区别。
麻烦帮我看一下为什么?谢谢