- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- void quicksort(vector<int>& a,int l,int r){
- // 递归出口
- if(l>= r)return;
- // 根据左右边界定义两个指针, 在 i 指针左面的 <=target , 在 j 指针右面的 >= target
- int i = l - 1, j = r + 1;
- //target 为在当前的区间 [l,r] 中任意一个数, 一般选 l, r, l+r>>2, random 位置的值
- int target = a[l+r>>1];
- // 这里实现 i 指针左面 <=target,j 指针右面 >=target, 终止条件是连个指针没有相遇
- while(i <j){
- // 只要连个指针遇见不满足条件的数, 就停在那个数的位置上, 否则继续走
- do ++i; while(a[i] < target);
- do --j; while(a[j]> target);
- // 这里实现交换, 因为 i 位置的数一定满足 >=target, 同理 j 位置也一样, 所以他俩相互交换, 使得分别得到自己想要的数
- if(i <j)swap(a[i],a[j]);
- }
- // 递归的去排序已经排好的两个区间
- quicksort(a,l,j);
- quicksort(a,j+1,r);
- }
- int main(){
- int n;
- cin>> n;
- vector<int> a(n,0);
- for(int i = 0;i <a.size();++i)cin>>a[i];
- quicksort(a,0,a.size()-1);
- for(int i = 0;i <a.size();++i)cout << a[i] << " ";
- return 0;
- }
- #include <iostream>
- #include <algorithm>
- #include <vector>
- using namespace std;
- int n;
- vector<int> arr(1e6+10,0);
- vector<int> help(1e6+10,0);// 辅助数组
- void unionsort(vector<int>& arr,int l,int r){
- // 递归出口
- if(l>= r)return;
- // 递归地把左边一半和右边一半分别排好序
- int mid = l + r>> 1;
- unionsort(arr,l,mid);
- unionsort(arr,mid+1,r);
- // 合并已经排好序的两部分
- int i = l, j = mid + 1, k = 0;
- while(i <= mid && j <= r){
- if(arr[i] <= arr[j]) help[k++] = arr[i++];
- else help[k++] = arr[j++];
- }
- // 将剩下的部分合并
- while(i <= mid)help[k++] = arr[i++];
- while(j <= r)help[k++] = arr[j++];
- // 此时辅助数组已经排好序, 复制回原数组
- for(int i = l,j = 0;i <= r;++i,++j)arr[i] = help[j];
- }
- int main(){
- cin>> n;
- for(int i = 0;i <n;++i)cin>>arr[i];
- unionsort(arr,0,n-1);
- for(int i = 0;i < n;++i)cout << arr[i] << " ";
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3338301.html