算法复杂度O(nlongn) 稳定排序（也就是不会两个数字相等却交换啦位置） 快速排序就会交换位置所以sort不是稳定排序 要想稳定的sort stl函数也有就是： stable sort捏个会多占用空间，其实这个就是以归并排序为基础的东西。 代码：以后自己看不懂啦会来加注释的，，，，（懒狗） 顺手先放个分割排序函数partition，自己写快排可以调用这个函数。
#include <iostream> #include <bits/stdc++.h> using namespace std; #define MAX 100000 int a[MAX], n; int partitionn(int p,int r){ int x, i, j; x=a[r]; i=p-1; for(j=p;j<r;j++){ if(a[j]<=x){ i++; swap(a[j],a[i]); } } swap(a[i+1],a[r]); return i+1; } int main() { int i,q; scanf("%d",&n); for(i=0;i<n;i++){ scanf("%d",&a[i]); } q=partitionn(0,n-1); for(i=0;i<n;i++) { if(i)printf(" "); if(i==q)printf("["); printf("%d",a[i]); if(i==q)printf("]"); } printf("\n"); return 0; }正角归并：
#include <iostream> using namespace std; #define MAX 500000 #define SENTINEL 2000000000 int l[MAX/2+2],r[MAX/2+2]; int cnt;//记录比较的次数;； void merge(int a[], int n, int left, int mid, int right) { int n1 =mid - left; int n2= right - mid; for( int i=0; i<n1; i++)l[i]=a[left+i]; for( int i=0; i<n2; i++)r[i]=a[mid+i]; l[n1]=r[n2]=SENTINEL; int i=0,j=0; for(int k=left; k<right; k++) { cnt++;//比较次数增加； if(l[i]<=r[j]) { a[k]=l[i++]; } else { a[k]=r[j++]; } } } void mergesort(int a[],int n, int left, int right){ if(left+1<right){ int mid=(left+right)/2; mergesort(a, n, left, mid); mergesort(a, n, mid, right); merge(a,n,left, mid, right); } } int main() { int a[MAX],n,i; cnt=0; cin >> n; for(i=0;i<n;i++) { cin >> a[i]; } mergesort(a, n, 0, n); for(i=0;i<n;i++){ if(i)cout << " "; cout << a[i]; } cout << endl; cout<< cnt<< endl;//输出比较次数； return 0; }