/* 合并排序 O(n*lgn)  */       #include <iostream>      using namespace std;          #define MAXN 100      int a[MAXN];         void Merge(int a[MAXN],int left,int mid,int right)    {           int i,j,k;         int n1=mid-left+1;           int n2=right-mid;           int L[MAXN],R[MAXN];           for(i=1;i<=n1;i++)               L[i]=a[left+i-1];           for(j=1;j<=n2;j++)               R[j]=a[mid+j];                    i=j=1;           for(k=left;k<=right;k++)           {               if(i==n1+1)//L中已经无元素，将R剩余元素复制到a中                {                 a[k]=R[j];                   j++;              }               else if(j==n2+1)//R中已经无元素，将L剩余元素复制到a中                {                   a[k]=L[i];                   i++;               }               else               {                   if(L[i]<R[j])                   {                       a[k]=L[i];                       i++;                   }                   else                   {                       a[k]=R[j];                      j++;                  }               }           }      }           void MergeSort(int a[MAXN],int left,int right)      {           int mid;           if(left<right)           {              mid=(left+right)/2;               MergeSort(a,left,mid);               MergeSort(a,mid+1,right);               Merge(a,left,mid,right);            }       }          int main()      {          int n,i;          cout<<"输入n:\n";        cin>>n;          for(i=0;i<n;i++)              cin>>a[i];                MergeSort(a,0,n-1);                 cout<<"分治法排序后:\n";        for(i=0;i<n;i++)              cout<<a[i]<<" ";                 cout<<endl;        return 0;      }   

/*快速排序*/#include<iostream>using namespace std;int AdjustArray(int s[],int left,int right) //返回调整后基准数的位置  {      int i=left,j=right+1;      int x=s[left]; //s[l]即s[i]就是第一个坑          while (i<j)      {          // 从右向左找小于x的数来填s[i]          while(i<j&&s[j]>=x)               j--;            if(i<j)           {              s[i]=s[j]; //将s[j]填到s[i]中，s[j]就形成了一个新的坑              i++;          }            // 从左向右找大于或等于x的数来填s[j]          while(i<j&&s[i]<x)              i++;            if(i<j)           {              s[j]=s[i]; //将s[i]填到s[j]中，s[i]就形成了一个新的坑              j--;          }      }      //退出时，i等于j。将x填到这个坑中。      s[i] = x;        return i;  }  void quick_sort1(int s[],int left,int right)  {     if (left<right)      {         int i=AdjustArray(s,left,right);//先成挖坑填数法调整s[]          quick_sort1(s,left,i-1); // 递归调用           quick_sort1(s,i+1,right);      }  }  //测试int main(){    int a[9]={22,44,11,89,99,45,43,22,66};    quick_sort1(a,0,8);    for(int i=0;i<9;i++)        cout<<a[i]<<" ";    cout<<endl;    return 0;}